انتخاب با شرط: از «دقیقاً» تا «حداقل» در مسائل ترکیبیات
مفاهیم پایه: اصلهای جمع و ضرب در انتخابهای مقید
پیش از ورود به بحث اصلی، باید با دو ابزار قدرتمند شمارش آشنا شویم: اصل جمع و اصل ضرب . این اصول به ما میگویند که چگونه تعداد حالتهای ممکن برای انجام یک کار را بدون شمردن تکتک آنها محاسبه کنیم. اگر کاری را بتوان به دو روش مجزا (روش اول m حالت و روش دوم n حالت) انجام داد و این دو روش با هم تداخل نداشته باشند، کل حالتها برابر m+n است (اصل جمع). اما اگر انجام یک کار نیازمند انجام پشت سر هم دو مرحله باشد (مرحله اول m حالت و مرحله دوم n حالت)، آنگاه کل حالتها برابر m×n خواهد بود (اصل ضرب) .
برای مثال، فرض کنید میخواهید یک پیراهن و یک شلوار از کمد خود انتخاب کنید. اگر 3 پیراهن و 4 شلوار داشته باشید، به کمک اصل ضرب، تعداد حالتهای انتخاب یک دست لباس برابر است با 3×4=12 حالت. حالا اگر قرار باشد فقط یک تکه لباس (یا پیراهن یا شلوار) از کمد بیرون بیاورید، تعداد حالتها طبق اصل جمع برابر 3+4=7 حالت خواهد بود.
انتخاب با قید «دقیقاً»: استفاده از ترکیبات (Combinations)
یکی از رایجترین انواع شرط، انتخاب «دقیقاً» تعدادی عضو از یک مجموعه است. در این حالت، ترتیب اهمیتی ندارد و فقط گروه نهایی برای ما مهم است. برای محاسبه تعداد حالتها از ترکیب استفاده میکنیم. فرمول انتخاب k عضو از n عضو متمایز به صورت $C(n,k) = \frac{n!}{k!(n-k)!}$ است .
مثال عینی فرض کنید در یک کتابخانه 10 کتاب ریاضی و 15 کتاب فیزیک داریم. میخواهیم دقیقاً3 کتاب ریاضی و 2 کتاب فیزیک را برای امانت انتخاب کنیم. برای حل این مسئله، دو انتخاب مستقل داریم: انتخاب کتابهای ریاضی و انتخاب کتابهای فیزیک. طبق اصل ضرب، تعداد حالتها برابر است با حاصلضرب تعداد حالتهای انتخاب 3 کتاب ریاضی از 10 کتاب ($C(10,3)$) در تعداد حالتهای انتخاب 2 کتاب فیزیک از 15 کتاب ($C(15,2)$). بنابراین جواب میشود $C(10,3) \times C(15,2) = 120 \times 105 = 12600$ حالت.
انتخاب با قید «حداقل» و «حداکثر»: تکنیک مکمل و حالتبندی
شرایط «حداقل» (دستکم) و «حداکثر» (حداکثر) پیچیدهتر از «دقیقاً» هستند. برای حل این مسائل، معمولاً مسئله را به چند حالت «دقیقاً» افراز کرده و سپس از اصل جمع استفاده میکنیم . گاهی نیز از روش مکمل استفاده میکنیم؛ یعنی تعداد کل حالتها (بدون شرط) را منهای حالتهای نامطلوب (مثلاً حالتهایی که شرط حداقل را نقض میکنند) میکنیم.
| شرط انتخاب (از ۵ مرد و ۷ زن) | روش حل | محاسبه (فرمول) | تعداد حالتها |
|---|---|---|---|
| انتخاب یک تیم ۴ نفره با حداقل ۲ زن | حالتبندی: ۲ زن و ۲ مرد، ۳ زن و ۱ مرد، ۴ زن و ۰ مرد | $C(7,2)C(5,2) + C(7,3)C(5,1) + C(7,4)C(5,0)$ | 210 + 175 + 35 = 420 |
| انتخاب یک تیم ۴ نفره با حداکثر ۲ مرد | حالتبندی: ۰ مرد، ۱ مرد، ۲ مرد | $C(5,0)C(7,4) + C(5,1)C(7,3) + C(5,2)C(7,2)$ | 35 + 175 + 210 = 420 |
نکته توجه کنید که دو شرط «حداقل ۲ زن» و «حداکثر ۲ مرد» در یک جمعیت ۵ مرد و ۷ زن، معادل یکدیگر هستند، چون اگر تیمی حداقل ۲ زن داشته باشد، حداکثر ۲ مرد خواهد داشت. به همین دلیل جواب هر دو یکسان (420) شد. این همان مفهوم مکمل است.
انتخاب با قید «از هر گروه»: اصل ضرب و انتخابهای اجباری
گاهی شرط میکند که حتماً باید از هر دسته یا گروه مشخصی، تعدادی (معمولاً حداقل یک نفر) انتخاب شوند. در این گونه موارد، ابتدا انتخابهای اجباری را انجام میدهیم و سپس مابقی انتخابها را با توجه به شرایط انجام میدهیم. این قبیل مسائل معمولاً با ترکیب مفاهیم اصل ضرب و ترکیب حل میشوند.
مثال عینی یک باشگاه ورزشی دارای 8 مربی بدنسازی، 5 مربی ورزشی و 3 مربی تغذیه است. میخواهیم یک کمیته 5 نفره تشکیل دهیم که از هر گروه حداقل یک نفر در آن حضور داشته باشد. برای حل، ابتدا به هر گروه یک سهمیه اجباری میدهیم (1 نفر از بدنسازی، 1 نفر از ورزشی، 1 نفر از تغذیه). حالا 2 نفر باقیمانده را باید از مجموع 5+8+3=16 نفر انتخاب کنیم، اما با این تفاوت که حالا دیگر محدودیتی نداریم و میتوانیم از هر گروهی (حتی همان گروههای قبلی) انتخاب کنیم. پس تعداد حالتها برابر است با تعداد انتخاب 2 نفر از 16 نفر، یعنی $C(16,2)=120$ حالت.
اصل لانه کبوتری: تضمین وجود یک شرط
دستهای از مسائل انتخاب با شرط به ما میگویند «حداقل چند عضو انتخاب کنیم تا مطمئن شویم که ...». این مسائل با اصل لانه کبوتری (Pigeonhole Principle) حل میشوند . این اصل ساده میگوید: اگر n کبوتر را در k لانه قرار دهیم و n \gt k، آنگاه حداقل یک لانه شامل حداقل دو کبوتر است.
پاسخ: بدترین حالت ممکن این است که از هر موضوع حداکثر 3 کتاب برداریم (3+3+3=9 کتاب). با برداشتن دهمین کتاب، دیگر مجبوریم یک کتاب را از یکی از موضوعات برداریم و آن موضوع صاحب 4 کتاب خواهد شد. پس حداقل باید 10 کتاب برداریم.
کاربرد عملی: طراحی نظرسنجی و تشکیل کمیته
فرض کنید مدیر یک شرکت قصد دارد یک تیم پروژه 5 نفره از بین 8 برنامهنویس و 6 تحلیلگر تشکیل دهد. او میخواهد اکثریت تیم با برنامهنویسان باشد (یعنی حداقل 3 برنامهنویس). برای محاسبه تعداد تیمهای ممکن، حالتهای 3 برنامهنویس و 2 تحلیلگر، 4 برنامهنویس و 1 تحلیلگر، و 5 برنامهنویس و 0 تحلیلگر را محاسبه کرده و با هم جمع میکنیم. این یک کاربرد واقعی از انتخاب با شرط «حداقل» در مدیریت منابع انسانی است.
چالشهای مفهومی
❓ چالش ۱: تفاوت «حداقل یک» با «دقیقاً یک» چیست؟
در شرط «دقیقاً یک»، فقط حالتهایی مجاز هستند که تعداد اعضای مورد نظر برابر با یک باشد. اما در شرط «حداقل یک»، حالتهایی که تعداد اعضا یک، دو، سه و ... باشد نیز مجاز هستند. به عبارت دیگر، «حداقل یک» متمم حالت «صفر» است، در حالی که «دقیقاً یک» فقط یک حالت خاص از «حداقل یک» میباشد.
❓ چالش ۲: چگونه تشخیص دهیم مسئله از اصل ضرب استفاده میکند یا جمع؟
کلمات کلیدی راهنما هستند. اگر مراحل انتخاب به صورت پشت سر هم و وابسته به هم باشند (مثلاً اول یک کتاب و سپس یک مجله)، از اصل ضرب استفاده میکنیم. اگر چند حالت مجزا و غیرهمزمان داشته باشیم (مثلاً یا این کتاب یا آن مجله)، از اصل جمع استفاده میکنیم .
❓ چالش ۳: آیا در مسائل «حداقل»، همیشه باید همه حالتها را جداگانه نوشت؟
خیر. گاهی اوقات محاسبه مکمل (تعداد کل حالتها منهای حالتهای نامطلوب) بسیار سریعتر است. مثلاً برای محاسبه «حداقل یک کتاب ریاضی» از بین چند کتاب، میتوانیم تعداد کل انتخابها را منهای حالتهایی که هیچ کتاب ریاضی ندارند (صفر کتاب ریاضی) کنیم.
پاورقی
1ترکیب (Combination): به تعداد روشهای انتخاب چند عضو از یک مجموعه، بدون در نظر گرفتن ترتیب آنها گفته میشود.
2اصل لانه کبوتری (Pigeonhole Principle): اصلی در ریاضیات که میگوید اگر تعداد اشیاء بیشتر از تعداد خانهها باشد، حداقل یک خانه شامل بیش از یک شیء است.
3فاکتوریل (Factorial): حاصلضرب همه اعداد طبیعی از 1 تا n را فاکتوریل n میگویند و با نماد n! نمایش میدهند.
