زیرمجموعههای r عضوی: انتخاب بدون ترتیب از یک مجموعه n عضوی
مفهوم اصلی: چه زمانی ترتیب اهمیت ندارد؟
تصور کنید یک کیسه شامل 3 توپ رنگی قرمز، آبی و سبز داریم. میخواهیم 2 توپ از آن خارج کنیم. اگر ترتیب خارج شدن توپها برای ما مهم باشد (مثلاً اول قرمز بعد آبی با اول آبی بعد قرمز دو حالت متفاوت باشند)، به آن «جایگشت» میگوییم. اما اگر فقط به این فکر کنیم که کدام دو توپ انتخاب شدهاند (مجموعه {قرمز، آبی} با {آبی، قرمز} یکی است)، آنگاه با مفهوم «ترکیب» یا «زیرمجموعههای r عضوی» سر و کار داریم.
ترکیب r از n جسم، یک انتخاب بدونترتیب از r جسم از میان n جسم متمایز است. به عبارت دیگر، زیرمجموعهای با اندازه r از یک مجموعه n عضوی.
برای نمونه، از مجموعه {a,b,c}، زیرمجموعههای 2 عضوی عبارتند از: {a,b}, {a,c}, {b,c}. تعداد این زیرمجموعهها 3 است. همانطور که میبینید، مجموعههای {a,b} و {b,a} یکسان هستند.
فرمول بنیادین و نمادگذاری
تعداد زیرمجموعههای r عضوی از یک مجموعه n عضوی را با نماد C(n,r)، _nC_r یا \binom{n}{r} نمایش میدهند1. فرمول محاسبه آن به صورت زیر است:
$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$در این فرمول، $n!$ (خوانده میشود n فاکتوریل) حاصلضرب تمام اعداد طبیعی از 1 تا n است2. به عنوان مثال:
$\binom{5}{2} = \frac{5!}{2! \times 3!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(2 \times 1) \times (3 \times 2 \times 1)} = \frac{120}{2 \times 6} = \frac{120}{12} = 10$یعنی از یک مجموعه 5 عضوی، میتوان 10 زیرمجموعه 2 عضوی انتخاب کرد.
| مفهوم | ترتیب اهمیت دارد؟ | فرمول | مثال (انتخاب 2 نفر از 3 نفر) |
|---|---|---|---|
| جایگشت (P(n,r)) | خیر | $\frac{n!}{(n-r)!}$ | نفر اول و دوم با نفر دوم و اول متفاوت است (6 حالت) |
| ترکیب (C(n,r)) | بله | $\frac{n!}{r!(n-r)!}$ | انتخاب دو نفر به عنوان یک تیم (3 حالت) |
مثلث خیام-پاسکال: نمایش زیبای ترکیبات
ضرایب دوجملهای را میتوان به صورت یک آرایه مثلثی به نام مثلث خیام3 یا مثلث پاسکال نمایش داد. در این مثلث، هر سطر متناظر با یک n و هر ستون متناظر با یک r است. مقدار هر خانه حاصل جمع دو خانه بالای آن است:
$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$n=1: 1 \quad 1$
$n=2: 1 \quad 2 \quad 1$
$n=3: 1 \quad 3 \quad 3 \quad 1$
$n=4: 1 \quad 4 \quad 6 \quad 4 \quad 1$
$n=5: 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1$
برای نمونه، عدد 10 در سطر پنجم (مربوط به n=5) و ستون سوم (مربوط به r=2 یا r=3)، همان تعداد زیرمجموعههای 2 عضوی از یک مجموعه 5 عضوی است که پیشتر محاسبه کردیم.
کاربردهای عملی در انتخاب و تصمیمگیری
مفهوم زیرمجموعه r عضوی کاربردهای فراوانی در زندگی روزمره و علوم مختلف دارد. در ادامه به چند مثال عینی اشاره میکنیم:
- انتخاب تیم پروژه: فرض کنید در یک کلاس 10 نفره، معلم میخواهد یک تیم 4 نفره برای مسابقه علمی انتخاب کند. تعداد تیمهای ممکن برابر است با $C(10,4) = 210$ تیم مختلف.
- برگزاری کمیته: میخواهیم از بین 7 عضو یک انجمن، یک کمیته 3 نفره تشکیل دهیم. اگر تمام اعضا توانایی یکسانی داشته باشند، تعداد حالتها $C(7,3)=35$ است.
- بازیهای کارتی: در یک دست بازی استاندارد 52 کارتی، تعداد راههای انتخاب یک دست 5 کارتی (در بازی پوکر) برابر است با $C(52,5) = 2,598,960$ حالت مختلف. این عدد نشاندهنده تنوع بالای دستهاست.
- خرید میوه: اگر یک فروشنده 6 نوع میوه داشته باشد و شما بخواهید 3 نوع مختلف از آنها را برای مهمانی بخرید، به $C(6,3)=20$ طریق میتوانید انتخاب کنید.
چالشهای مفهومی و رفع ابهام
❓ چالش اول: آیا $C(n,0)$ و $C(n,n)$ معنای مشخصی دارند؟
بله. $C(n,0)$ تعداد راههای انتخاب صفر عضو از یک مجموعه است. این کار فقط به یک روش انجام میشود: هیچ عضوی را انتخاب نکنیم. پس $C(n,0)=1$. همچنین $C(n,n)$ تعداد راههای انتخاب همه n عضو است که آن هم فقط یک روش دارد. طبق فرمول هم داریم $C(n,0)=C(n,n)=1$.
❓ چالش دوم: چرا $C(n,r) = C(n, n-r)$ است؟
این یک ویژگی مهم ترکیبات است. انتخاب r عضو از n عضو، درست معادل با کنار گذاشتن n-r عضو است. به بیان دیگر، با مشخص کردن اعضای انتخابشده، اعضای انتخابنشده نیز مشخص میشوند. بنابراین تعداد حالتهای انتخاب r عضو با انتخاب n-r عضو برابر است. برای نمونه، $C(5,2)=C(5,3)=10$.
❓ چالش سوم: اگر اشیاء غیرمتمایز باشند چه؟
فرمول ترکیبی که معرفی شد، برای حالتهایی است که اشیاء با یکدیگر متمایز هستند. اگر اشیاء یکسان باشند (مثلاً 10 توپ سفید یکسان)، آنگاه انتخاب r عضو تنها یک راه دارد، زیرا همه اشیاء شبیه هم هستند. برای اشیاء غیرمتمایز، بحث «ترکیب با تکرار» مطرح میشود که فرمول متفاوتی دارد.
مثال ترکیبی: انتخاب منو و شانس
رستورانی 8 نوع پیشغذا و 6 نوع غذای اصلی دارد. اگر یک مشتری بخواهد یک پیشغذا و یک غذای اصلی انتخاب کند، کاربرد اصل ضرب است ($8 \times 6 = 48$ حالت). اما اگر بخواهد برای یک مهمانی 3 نوع پیشغذا (از بین 8 نوع) و 2 نوع غذای اصلی (از بین 6 نوع) انتخاب کند و ترتیب سرو برایش مهم نباشد، آنگاه تعداد حالتها به صورت ضرب دو ترکیب محاسبه میشود:
$C(8,3) \times C(6,2) = 56 \times 15 = 840$این یعنی مشتری میتواند از میان 840 منوی مختلف، انتخاب داشته باشد.
ارتباط با بسط دوجملهای
یکی از مهمترین کاربردهای ترکیبات در ریاضیات، در بسط دوجملهای $(x+y)^n$ است. ضرایب هر جمله در این بسط، دقیقاً اعداد ترکیبی هستند:
$(x+y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y^r$برای مثال:
$(x+y)^3 = \binom{3}{0}x^3 + \binom{3}{1}x^2 y + \binom{3}{2}x y^2 + \binom{3}{3}y^3 = x^3 + 3x^2y + 3xy^2 + y^3$پاورقی
1ترکیب (Combination): انتخاب تعدادی از اعضای یک مجموعه بدون توجه به ترتیب.
2فاکتوریل (Factorial): حاصلضرب اعداد طبیعی متوالی از 1 تا n. تعریف $0! = 1$ است.
3خیام (Khayyam): اشاره به عمر خیام، ریاضیدان و اخترشناس ایرانی که در سدههای پنجم و ششم هجری، مطالعات پیشگامانهای در زمینه ضرایب دوجملهای داشته است. در غرب این مثلث به نام پاسکال (Blaise Pascal) ریاضیدان فرانسوی قرن هفدهم شناخته میشود.
