ترتیب اهمیت ندارد: هنر انتخاب مجموعهها در شمارش
چرا گاهی ترتیب انتخاب بیاهمیت است؟ مقایسهٔ ترکیب و جایگشت
تصور کنید میخواهید یک تیم ۳ نفره از میان ۵ داوطلب انتخاب کنید. برای شما مهم نیست که نفر اول، دوم یا سوم کیست؛ فقط اعضای نهایی تیم اهمیت دارد. اینجا پای ترکیب به میان میآید. اما اگر قرار باشد در یک مسابقه، نفرات اول، دوم و سوم را مشخص کنید، آنگاه ترتیب انتخاب کاملاً مهم میشود و باید از جایگشت1 استفاده کرد.
تفاوت کلیدی این دو مفهوم در این است که در ترکیب، مجموعهٔ نهایی بدون ترتیب مدنظر است، درحالی که در جایگشت، ترتیب قرار گرفتن عناصر نیز محاسبه میشود.
| ویژگی | ترکیب (ترتیب بیاهمیت) | جایگشت (ترتیب مهم) |
|---|---|---|
| تعداد انتخاب ۲ عنصر از ۳ عنصر \{A,B,C\} | $\{A,B\}, \{A,C\}, \{B,C\}$ → ۳ حالت | $(A,B), (B,A), (A,C), (C,A), (B,C), (C,B)$ → ۶ حالت |
| فرمول اصلی | $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ | $P(n,k) = \frac{n!}{(n-k)!}$ |
گامبهگام با فرمول ترکیب و نمادگذاری دوجملهای
فرمول محاسبهٔ تعداد ترکیبهای $k$ عنصر از $n$ عنصر متمایز به صورت زیر است:
در این فرمول، $n!$ (بخوانید «فاکتوریل ان») حاصلضرب تمام اعداد طبیعی از $1$ تا $n$ است. برای نمونه، $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. همچنین در محاسبه ترکیب داریم: $\binom{n}{k} = \binom{n}{n-k}$ که یک ویژگی متقارن جالب است.
مثال عددی گامبهگام: فرض کنید از میان ۴ نوع میوه (سیب، پرتقال، موز، کیوی) میخواهیم ۲ نوع را برای تهیهٔ یک سبد میوه انتخاب کنیم (ترتیب قرار گرفتن میوهها در سبد مهم نیست). طبق فرمول ترکیب:
این ۶ ترکیب عبارتند از: (سیب،پرتقال)، (سیب،موز)، (سیب،کیوی)، (پرتقال،موز)، (پرتقال،کیوی)، (موز،کیوی).
کاربرد عملی: انتخاب اعضای یک کمیته یا تهیهٔ غذای رستوران
فرض کنید یک رستوران به مشتریان خود اجازه میدهد از میان ۷ نوع پیشغذا، ۳ نوع را بدون توجه به ترتیب سرو، برای بشقاب مخصوص انتخاب کنند. تعداد روشهای ممکن برابر است با:
همچنین در یک مدرسه، برای انتخاب یک کمیتهٔ ۴ نفره از بین ۱۰ دانشآموز، تعداد حالتهای ممکن (بدون در نظر گرفتن نقش رئیس یا منشی) برابر $\binom{10}{4} = 210$ خواهد بود. این محاسبات در آمار، احتمال و حتی در طراحی آزمایشها کاربرد گستردهای دارند.
چالشهای مفهومی در تشخیص ترکیب از جایگشت
پاسخ: اگر تنها مجموعه لباسهایی که در طول هفته میپوشید مهم باشد (نه اینکه کدام لبس در کدام روز پوشیده شود)، آنگاه مسئله از نوع ترکیب است. اما اگر برنامهٔ روزانهٔ پوشش اهمیت داشته باشد، به جایگشت تبدیل میشود. پس «ترتیب زمانی» کلید تشخیص است.
پاسخ: چون در جایگشت، هر انتخاب $k$ عنصر به تعداد $k!$ حالت مختلف چیده میشود. از آنجا که در ترکیب همهٔ این $k!$ ترتیب معادل یک حالت محسوب میشوند، حاصل را بر $k!$ تقسیم میکنیم تا حالتهای تکراری حذف شوند.
پاسخ: بله، مگر اینکه $k=0$ یا $k=1$ باشد که در این صورت هر دو برابر میشوند. برای $k \ge 2$ همواره $\binom{n}{k} = \frac{P(n,k)}{k!} \lt P(n,k)$.
پاورقیها
1 جایگشت (Permutation): حالتی از شمارش که در آن ترتیب قرار گرفتن عناصر تأثیر دارد و از فرمول $P(n,k)=\frac{n!}{(n-k)!}$ استفاده میشود.
2 فاکتوریل (Factorial): حاصلضرب تمام اعداد طبیعی از $1$ تا $n$ که با نماد $n!$ نمایش داده میشود. به طور قراردادی $0! = 1$ است.
3 نماد دوجملهای (Binomial Coefficient): همان $\binom{n}{k}$ است که در بسط دوجملهای $(a+b)^n$ نیز ظاهر میشود.