نمودار درختی: نمایش شاخه‌ایِ انتخاب‌های مرحله‌به‌مرحله برای شمارش حالت‌ها

نمودار درختی: نقشه راهی برای شمارش بدون خطا

شمارش گام به گام: از ریشه تا برگ‌ها

نمودار درختی برای شمارش تعداد کل حالت‌ها، از یک نقطهٔ شروع به نام ریشه آغاز می‌شود. از ریشه، به تعداد گزینه‌های اولین انتخاب، شاخه خارج می‌شود. در انتهای هر شاخه، دومین انتخاب انجام می‌شود و به همین ترتیب، این روند تا آخرین مرحله ادامه می‌یابد. هر مسیر از ریشه تا یک برگ (انتهای یک شاخه) نمایانگر یک حالت منحصربه‌فرد است. تعداد کل حالت‌ها برابر است با تعداد برگ‌ها یا حاصل‌ضرب تعداد انتخاب‌ها در هر مرحله. برای درک بهتر، فرض کنید می‌خواهید یک بستنی با سه طعم (وانیل، شکلات، توت‌فرنگی) و دو نوع تزئین (ترافل ریز، چیپس شکلات) انتخاب کنید. انتخاب طعم (۳ گزینه) مرحلهٔ اول و انتخاب تزئین (۲ گزینه) مرحلهٔ دوم است. تعداد کل حالت‌ها برابر است با: $3 \times 2 = 6$

سناریوی عملی: منوی یک رستوران

فرض کنید برای صرف ناهار به رستورانی رفته‌اید که منوی آن به شکل زیر است:

• پیش‌غذا: سوپ (س) یا سالاد (ص) (2 گزینه)
• غذای اصلی: مرغ (م)، ماهی (م‌ی) یا استیک (ا) (3 گزینه)
• نوشیدنی: آب معدنی (آ)، نوشابه (ن) یا دوغ (د) (3 گزینه)

اگر بخواهید یک وعدهٔ کامل شامل یک پیش‌غذا، یک غذای اصلی و یک نوشیدنی انتخاب کنید، چند نوع وعدهٔ غذایی می‌توانید داشته باشید؟ نمودار درختی این مسئله را اینگونه نشان می‌دهد:

• از ریشه، دو شاخه برای پیش‌غذا (س، ص) رسم می‌کنیم.
• در انتهای هر کدام از این شاخه‌ها، برای غذای اصلی سه شاخه (م، م‌ی، ا) رسم می‌کنیم. تا اینجا $2 \times 3 = 6$ مسیر داریم.
• در انتهای هر کدام از این $6$ مسیر، سه شاخه برای نوشیدنی (آ، ن، د) رسم می‌کنیم.

با این حساب، تعداد کل برگ‌ها (وعده‌های غذایی ممکن) برابر است با: $2 \times 3 \times 3 = 18$ بدون رسم درخت، به‌سادگی می‌توان دریافت که با ضرب تعداد انتخاب‌های هر مرحله، به جواب می‌رسیم.

کاربرد در محاسبهٔ احتمالات

نمودار درختی فقط برای شمارش ساده نیست، بلکه ابزاری کلیدی در محاسبهٔ احتمالات نیز هست. با نوشتن احتمال روی هر شاخه، می‌توان احتمال وقوع هر مسیر (برگ) را با ضرب احتمال‌های طول مسیر به دست آورد. به عنوان مثال، فرض کنید یک کیسه شامل ۳ مهرهٔ قرمز (ق) و ۲ مهرهٔ آبی (آ) است. دو مهره را به‌طور متوالی و بدون جای‌گذاری[3] از کیسه خارج می‌کنیم. می‌خواهیم احتمال این که هر دو مهره قرمز باشند را حساب کنیم.

• مرحله اول: احتمال قرمز بودن مهرهٔ اول $\frac{3}{5}$ و احتمال آبی بودن $\frac{2}{5}$ است.
• مرحله دوم (بسته به نتیجهٔ مرحله اول):
  • اگر مهره اول قرمز باشد ($\frac{3}{5}$)، حالا $2$ مهره قرمز و $2$ مهره آبی باقی می‌ماند. احتمال قرمز بودن دوم $\frac{2}{4} = \frac{1}{2}$ است.
  • اگر مهره اول آبی باشد ($\frac{2}{5}$)، $3$ مهره قرمز و $1$ مهره آبی باقی می‌ماند. احتمال قرمز بودن دوم $\frac{3}{4}$ است.

احتمال این که هر دو مهره قرمز باشند (مسیر قرمز-قرمز) برابر است با حاصل‌ضرب احتمال‌های دو شاخه: $\frac{3}{5} \times \frac{1}{2} = \frac{3}{10}$ در اینجا، نمودار درختی به ما کمک می‌کند تا وابستگی رویدادها را به‌صورت بصری درک کنیم.

چالش‌های مفهومی و پاسخ به آنها

مثال ترکیبی: پرتاب سکه و تاس

برای تثبیت مفهوم، یک مثال کلاسیک دیگر را بررسی می‌کنیم. یک سکه و یک تاس را با هم پرتاب می‌کنیم. نمودار درختی نتایج ممکن را نشان می‌دهد.

• مرحله اول (پرتاب سکه): دو حالت، شیر (Sh) یا خط (Kh).
• مرحله دوم (پرتاب تاس): شش حالت، اعداد $1$ تا $6$.

تعداد کل حالت‌ها $2 \times 6 = 12$ حالت است. احتمال به دست آوردن شیر و عدد فرد به این صورت محاسبه می‌شود:

• احتمال شیر: $\frac{1}{2}$
• با فرض شیر، احتمال آمدن عدد فرد ($1, 3, 5$) برابر $\frac{3}{6} = \frac{1}{2}$ است.
• احتمال مورد نظر: $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$

پاورقی

• ¹ اصل شمارش (Counting Principle): اصلی بنیادی در ترکیبیات که بیان می‌کند اگر کاری به m طریق و کار دیگری به n طریق انجام شود، آن دو کار پشت سر هم به m × n طریق قابل انجام هستند.
• ² احتمال (Probability): شاخه‌ای از ریاضیات که به بررسی احتمال وقوع رویدادهای تصادفی می‌پردازد.
• ³ بدون جای‌گذاری (Without Replacement): به موقعیتی گفته می‌شود که آیتم انتخاب شده به مجموعه اولیه بازگردانده نشود، بنابراین احتمال انتخاب‌های بعدی تغییر می‌کند.
• ⁴ ترکیبیات (Combinatorics): شاخه‌ای از ریاضیات که به مطالعهٔ روش‌های شمارش، ترکیب و جایگشت اشیا می‌پردازد.
• ⁵ جایگشت (Permutation): به تعداد حالات چیدن اشیا در کنار یکدیگر وقتی ترتیب اهمیت دارد، گفته می‌شود.
• ⁶ ترکیب (Combination): به تعداد حالات انتخاب تعدادی اشیا از یک مجموعه وقتی ترتیب اهمیت ندارد، گفته می‌شود.