انتخاب بدون ترتیب: از نظریه تا کاربرد
مفهوم ترکیب و نمادگذاری
ترکیب (ترکیب) یک انتخاب ساده از اعضای یک مجموعه است؛ بدون آنکه به چیدمان و ترتیب آنها توجه کنیم. برای نمونه، اگر بخواهیم از میان سه کتاب ریاضی، فیزیک و شیمی دو کتاب را برای مطالعه انتخاب کنیم، حالتهای ممکن عبارتند از: {ریاضی، فیزیک}، {ریاضی، شیمی} و {فیزیک، شیمی}. در اینجا انتخاب {ریاضی، فیزیک} با {فیزیک، ریاضی} تفاوتی ندارد. نماد استاندارد برای تعداد ترکیبهای r عنصر از n عنصر متمایز، $C(n, r)$ یا $\binom{n}{r}$ است و آن را «n انتخاب r» میخوانند.
در این فرمول، $n!$ (خوانده میشود n فاکتوریل) حاصلضرب تمام اعداد طبیعی از 1 تا n است. به عنوان نمونه، $4! = 4 \times 3 \times 2 \times 1 = 24$. دلیل وجود فاکتوریل در مخرج این است که با تقسیم بر $r!$، اثر ترتیبهای مختلف برای r عنصر انتخابشده را از بین میبریم، و $(n-r)!$ نیز برای حذف ترتیب عناصر باقیمانده است.
تفاوت کلیدی: ترکیب در برابر جایگشت
مهمترین نکته در تشخیص ترکیب از جایگشت (جایگشت)1، توجه به اهمیت ترتیب است. در جایگشتها، هر چیدمان متفاوت یک حالت جداگانه محسوب میشود. برای درک بهتر، جدول زیر را ببینید:
| مفهوم | آیا ترتیب مهم است؟ | فرمول | مثال با سه حرف A, B, C و انتخاب دو تایی |
|---|---|---|---|
| ترکیب | خیر | $C(n, r)$ | {A,B}، {A,C}، {B,C} (3 حالت) |
| جایگشت | بله | $P(n, r) = \frac{n!}{(n-r)!}$ | (A,B)، (B,A)، (A,C)، (C,A)، (B,C)، (C,B) (6 حالت) |
همانطور که میبینید، در ترکیب بر خلاف جایگشت، جفتهایی مانند (A,B) و (B,A) یکسان در نظر گرفته شدهاند.
محاسبه گامبهگام: انتخاب تیم بسکتبال
فرض کنید یک مربی میخواهد از میان 5 بازیکن (با نامهای A، B، C، D، E)، یک تیم 2 نفره برای یک مسابقه انتخاب کند. از آنجا که پستها مشخص نیست و صرفاً قرار است دو نفر به زمین بروند، ترتیب انتخاب اهمیتی ندارد. پس با ترکیب روبروییم:
$C(5, 2) = \frac{5!}{2! \times (5-2)!} = \frac{5 \times 4 \times 3!}{2 \times 1 \times 3!} = \frac{20}{2} = 10$
بنابراین مربی میتواند از بین 10 تیم متفاوت، یکی را انتخاب کند. میتوانیم این حالتها را فهرست کنیم: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE. (توجه کنید که AB با BA یکی است.)
کاربرد در دنیای واقعی: دستهای پوکر و کمیتهها
ترکیبها در بسیاری از زمینهها کاربرد دارند. یکی از رایجترین مثالها، دستهای پوکر است. یک دست پوکر شامل 5 کارت از یک دسته 52 کارتی است. ترتیب قرار گرفتن کارتها در دست مهم نیست، بنابراین تعداد کل دستهای پوکر برابر است با:
$C(52, 5) = \frac{52!}{5! \times 47!} = 2,598,960$
مثال دیگر، تشکیل کمیتههای دانشآموزی است. اگر قرار باشد از میان 12 نامزد، یک کمیتهٔ 4 نفره تشکیل دهیم، تعداد حالتهای ممکن $C(12, 4) = 495$ است. در اینجا نیز ریاست یا سمت خاصی مطرح نیست و صرفاً عضویت در کمیته مد نظر است.
ویژگیهای جالب ترکیبها
چند ویژگی مهم در مورد ترکیبها وجود دارد که محاسبات را سادهتر میکند:
- ترکیبهای مکمل:$C(n, r) = C(n, n-r)$. انتخاب r عضو برای حضور، با انتخاب n-r عضو برای عدم حضور کاملاً معادل است. برای نمونه، انتخاب 3 کتاب از 7 کتاب با انتخاب 4 کتاب برای جاگذاشتن، یکسان است.
- حالتهای خاص:$C(n, 0) = C(n, n) = 1$. تنها یک راه برای انتخاب هیچکدام یا انتخاب همهٔ اعضا وجود دارد.
- مثلث خیام-پاسکال: ضرایب بسط دوجملهای (دوجملهای)2 همان مقادیر ترکیب هستند. رابطهٔ $(x+y)^n = \sum_{r=0}^{n} C(n, r) x^{n-r} y^r$.
چالشهای مفهومی
❓ آیا انتخاب اعضای تیم با تعیین نقشها (کاپیتان، گلر) یک ترکیب است؟
پاسخ: خیر. اگر نقشها متفاوت باشند، ترتیب اهمیت پیدا میکند و مسئله به یک جایگشت تبدیل میشود. برای مثال، انتخاب یک کاپیتان و یک کمککاپیتان از میان 5 نفر، $P(5, 2)=20$ حالت دارد، نه 10 حالت.
❓ چرا $C(n, r)$ همیشه یک عدد صحیح است؟
پاسخ: چون این عدد در حقیقت شمارش تعداد زیرمجموعههای r عضوی یک مجموعهٔ n عضوی است و تعداد زیرمجموعهها همواره یک عدد طبیعی است. هرچند فرمول شامل تقسیم فاکتوریلهاست، اما نتیجه همیشه به یک عدد صحیح بخشپذیر ختم میشود.
❓ آیا در انتخاب اعضای یک گروه که ممکن است اعضا تکراری داشته باشیم (مثلاً انتخاب چند نوع میوه با این شرط که میتوان یک نوع را چندبار برداشت)، باز هم از ترکیب استفاده میکنیم؟
پاسخ: خیر. وقتی اشیاء یکسان باشند یا امکان تکرار وجود داشته باشد، وارد مبحث «ترکیب با تکرار»3 میشویم که فرمول متفاوتی دارد و در این مقاله به آن نپرداختهایم. اینجا فرض ما بر روی اشیاء متمایز و بدون تکرار است.
پاورقیها
1جایگشت (Permutation): به هر ترتیببندی از عناصر یک مجموعه، جایگشت گفته میشود. در جایگشت، ترتیب قرار گرفتن عناصر اهمیت دارد.
2دوجملهای (Binomial): به عبارتی شامل دو جمله که با علامت جمع یا تفریق به هم متصل شدهاند، مانند (x+y)، دوجملهای میگویند. بسط دوجملهای به کمک ضرایب ترکیبی انجام میشود.
3ترکیب با تکرار (Combination with Repetition): حالتی از انتخاب است که در آن، برخلاف ترکیب ساده، اشیاء میتوانند بیش از یک بار انتخاب شوند. فرمول آن $C(n+r-1, r)$ است.
