انتخاب با شرط: هنر شمارش هوشمندانه
دقیقاً k عضو: بنیادیترین شرط
رایجترین حالت انتخاب با شرط، انتخاب «دقیقاً» تعداد مشخصی عضو از یک مجموعه است. اگر مجموعهای با n عضو داشته باشیم و بخواهیم دقیقاً k عضو از آن را بدون در نظر گرفتن ترتیب انتخاب کنیم، از ترکیب (n, k) استفاده میکنیم. فرمول آن به صورت زیر است:
$C(n, k) = \frac{n!}{k!(n-k)!}$مثال: فرض کنید یک کتابخانه 10 کتاب مختلف دارد. تعداد روشهای انتخاب دقیقاً 3 کتاب از این مجموعه برابر است با:
$C(10, 3) = \frac{10!}{3!7!} = 120$یعنی ما میتوانیم به 120 روش مختلف، 3 کتاب را برای مطالعه انتخاب کنیم. این همان ضریب دوجملهای است که در بسیاری از مسائل کاربرد دارد.
حداقل و حداکثر: از کرانها تا انتخاب نهایی
گاهی اوقات شرایط ما به صورت «حداقل» یا «حداکثر» یک تعداد مشخص مطرح میشود. مثلاً میگوییم: "میخواهیم حداقل 2 کتاب ریاضی انتخاب کنیم." در این حالت، باید مجموع حالتهای انتخاب دقیقاً 2 کتاب، دقیقاً 3 کتاب و ... را حساب کنیم. روش محاسبه به این صورت است:
$ \text{حالتهای حداقل k عضو} = \sum_{i=k}^{n} C(n, i) $برای روشنتر شدن موضوع، به مثال زیر توجه کنید. یک کیسه شامل 5 توپ رنگی (قرمز، آبی، سبز، زرد، بنفش) است. به چند روش میتوان حداقل 2 توپ انتخاب کرد؟
- حالتهای انتخاب دقیقاً 2 توپ: $C(5,2) = 10$
- حالتهای انتخاب دقیقاً 3 توپ: $C(5,3) = 10$
- حالتهای انتخاب دقیقاً 4 توپ: $C(5,4) = 5$
- حالتهای انتخاب دقیقاً 5 توپ: $C(5,5) = 1$
بنابراین تعداد کل روشهای انتخاب حداقل 2 توپ برابر است با:
$10 + 10 + 5 + 1 = 26$توجه کنید که در این روش، تمام حالتهای ممکن از k تا n را پوشش میدهیم. برای شرط «حداکثر» نیز به طریق مشابه عمل میکنیم، اما جمع را از صفر تا k ادامه میدهیم.
انتخاب از هر گروه: وقتی دستهبندی داریم
در بسیاری از مسائل، اعضای ما در گروههای مختلفی طبقهبندی میشوند. مثلاً در یک کلاس دانشآموزان در گروههای علمی، ورزشی و هنری عضو هستند. شرط انتخاب ممکن است این باشد: "از هر گروه حداقل یک نفر" یا "از هر گروه دقیقاً یک نفر". در این موارد، باید انتخابهای هر گروه را بهطور جداگانه محاسبه کرده و سپس در هم ضرب کنیم. این قانون به اصل ضرب معروف است.
مثال: یک گردش علمی برای دانشآموزان یک مدرسه ترتیب داده شده است. از هر پایه تحصیلی (هفتم، هشتم، نهم) قرار است دقیقاً 2 نفر انتخاب شوند. اگر پایه هفتم 120 نفر، پایه هشتم 110 نفر و پایه نهم 95 نفر دانشآموز داشته باشند، تعداد روشهای انتخاب این گروه به چند طریق ممکن است؟
برای پایه هفتم: $C(120, 2)$، پایه هشتم: $C(110, 2)$ و پایه نهم: $C(95, 2)$ حالت داریم. طبق اصل ضرب، تعداد کل روشها برابر است با:
$C(120, 2) \times C(110, 2) \times C(95, 2)$کاربرد عملی: انتخاب کمیته و تیمهای پروژه
فرض کنید میخواهیم یک تیم 5 نفره از میان 8 برنامهنویس و 6 طراح گرافتشکیل دهیم، به شرطی که حداقل 2 برنامهنویس در تیم حضور داشته باشند. این مسئله ترکیبی از شرط «حداقل» و انتخاب «از هر گروه» است. برای حل، باید حالتهای مختلف را جداگانه حساب کنیم:
- حالت اول: دقیقاً 2 برنامهنویس و 3 طراح: $C(8,2) \times C(6,3)$
- حالت دوم: دقیقاً 3 برنامهنویس و 2 طراح: $C(8,3) \times C(6,2)$
- حالت سوم: دقیقاً 4 برنامهنویس و 1 طراح: $C(8,4) \times C(6,1)$
- حالت چهارم: دقیقاً 5 برنامهنویس و 0 طراح: $C(8,5) \times C(6,0)$
حال کافی است این چهار عدد را با هم جمع کنیم تا پاسخ نهایی بهدست آید.
چالشهای مفهومی
پاسخ: دقیقاً! تعداد کل زیرمجموعههای یک مجموعه n عضوی، $2^n$ است که شامل زیرمجموعهی تهی (بدون عضو) هم میشود. با کم کردن این یک حالت، تعداد انتخابهای حداقل یک عضو برابر $2^n - 1$ میشود. این روش بسیار سریعتر از جمع زدن تکتک حالتهاست.
پاسخ: «دقیقاً ۲ عضو» تنها یک حالت خاص را شامل میشود: انتخاب درست 2 عضو. اما «حداقل ۲ عضو» شامل تمام حالتهایی است که تعداد اعضای انتخابشده 2، 3، ... تا n عضو باشد. پس دامنهی وسیعتری را پوشش میدهد.
پاسخ: در این حالت، دیگر نمیتوانیم به سادگی از اصل ضرب استفاده کنیم، زیرا انتخابها مستقل از یکدیگر نیستند. برای حل این مسائل باید از اصل شمول و عدم شمول[۲] استفاده کنیم تا حالتهای تکراری را حذف کنیم.
پاورقی
[۱] ترکیبیات (Combinatorics): شاخهای از ریاضیات که به مطالعه روشهای شمارش، ترکیب و چیدمان اعضای مجموعههای گسسته میپردازد.
[۲] اصل شمول و عدم شمول (Inclusion-Exclusion Principle): قاعدهای در ترکیبیات که برای شمارش تعداد اعضای اجتماع چند مجموعه، با در نظر گرفتن اشتراکهای بین آنها به کار میرود.
