نقطهٔ شروع: چرا گاهی شمردن مستقیم سخت است؟
در بسیاری از مسائل شمارش، ما به دنبال تعداد حالتهایی هستیم که یک شرط خاص را برآورده میکنند (حالت مطلوب). اما گاهی تعداد حالتهای مطلوب مستقیم قابل محاسبه نیست زیرا شرط، پیچیده یا شامل چندین «و» و «یا» منطقی است. در چنین شرایطی، روش هوشمندانه این است که ابتدا تعداد کل حالتهای ممکن را بدون هیچ شرط محدودکنندهای به دست آوریم و سپس تعداد حالتهایی را که شرط را نقض میکنند (حالتهای نامطلوب) بشماریم. در نهایت:
این روش را «شمارش به کمک اصل مکمل» یا «روش مخالف شرط» مینامند. برای نمونه، اگر بخواهیم تعداد اعداد دو رقمی که حداقل یک رقم آن $ 5 $ است را پیدا کنیم، شمردن مستقیم (اعداد شامل یک رقم $ 5 $ یا بیش از یک رقم $ 5 $) طولانی است. اما حالت مخالف یعنی «هیچ رقم $ 5 $ نباشد» بسیار سادهتر است.
گام اول: شناسایی وضعیتهای کلی، مطلوب و نامطلوب
هر مسئلهٔ شمارشی از سه بخش تشکیل میشود: کل فضای نمونه (همهٔ حالتهای ممکن)، زیرمجموعهٔ حالتهای مطلوب (آنچه میخواهیم)، و زیرمجموعهٔ حالتهای نامطلوب (بقیهٔ حالتها). راهبرد اصلی این است که اگر حالت مطلوب به صورت «حداقل یک بار» یا «حداقل یکی از ویژگیها» تعریف شده باشد، معمولاً حالت نامطلوب به «هیچکدام» یا «هیچ ویژگی» تبدیل میشود.
مثال: از بین $ 10 $ دانشآموز (شامل $ 6 $ پسر و $ 4 $ دختر) میخواهیم یک گروه $ 3 $ نفری انتخاب کنیم که حداقل یک پسر داشته باشد. حالت مطلوب یعنی: گروههایی که شامل یک یا دو یا سه پسر هستند. حالت نامطلوب: گروهی که هیچ پسری ندارد (یعنی هر $ 3 $ نفر دختر باشند).
مقایسهٔ دو روش:
- روش مستقیم: شمارش گروههای با $ 1 $ پسر حالتهای زیاد و پرخطا
- روش مکمل: $ \text{کل گروههای ۳ نفره} - \text{گروههای بدون پسر} $
گام دوم: محاسبهٔ تعداد کل حالتها و تعداد حالتهای نامطلوب
برای مثال بالا، تعداد کل انتخاب $ 3 $ نفر از $ 10 $ برابر است با:
تعداد حالتهای نامطلوب (بدون پسر) یعنی انتخاب $ 3 $ نفر از $ 4 $ دختر:
بنابراین تعداد گروههای مطلوب (حداقل یک پسر) برابر است با:
این روش در مسائلی مانند «تعداد اعداد بین $ 1 $ و $ 1000 $ که بر $ 2 $ یا $ 3 $ بخشپذیرند»، «تعداد رمزهای عبور با حداقل یک حرف بزرگ» یا «تعداد دستکم یک جفت در پرتاب تاس» هم کاربرد دارد.
مثال عینی: شمارش رمزهای عبور با حداقل یک رقم
فرض کنید میخواهیم تعداد رمزهای عبور $ 4 $ کاراکتری از حروف کوچک انگلیسی (۲۶ حرف) را پیدا کنیم که حداقل یک رقم ($ 0 $ تا $ 9 $) داشته باشند. حالت مطلوب شامل رمزهایی با یک، دو، سه یا چهار رقم است که شمارش مستقیم آن پیچیده و شامل حالتهای مختلف است. اما حالت نامطلوب یعنی «هیچ رقمی وجود نداشته باشد» که یعنی رمز تنها از حروف ساخته شده است.
- تعداد کل رمزهای ممکن: هر کاراکتر میتواند $ 26+10 = 36 $ حالت داشته باشد. بنابراین $ 36^{4} $
- تعداد رمزهای بدون رقم (تنها حروف): $ 26^{4} $
- تعداد رمزهای مطلوب: $ 36^{4} - 26^{4} $
| معیار مقایسه | روش مستقیم (شمارش حالتهای مطلوب) | روش مکمل (تفریق حالتهای نامطلوب) |
|---|---|---|
| تعداد حالتها برای مثال رمز $ 4 $ کاراکتری با حداقل یک رقم | باید جمع حالتهای ۱ رقم، ۲ رقم، ۳ رقم و ۴ رقم محاسبه شود (۴ جمله) | فقط $ 36^{4} - 26^{4} $ (تفریق دو جمله) |
| احتمال خطا در محاسبه | بالا | پایین |
| مناسب برای شرط «حداقل یک بار» | نیازمند استفاده از اصل شمول و عدم شمول | بسیار ساده و سریع |
کاربرد عملی در مسائل احتمال و ترکیبیات دبیرستانی
در مسائل احتمال، روش حالتهای نامطلوب مستقیم به محاسبهٔ احتمال مطلوب از راه $ P(\text{مطلوب}) = 1 - P(\text{نامطلوب}) $ منجر میشود. برای نمونه، اگر دو تاس را همزمان بیندازیم، احتمال اینکه حاصل جمع حداقل $ 4 $ باشد، به سادگی از راه محاسبهٔ احتمال جمعهای $ 2 $ و $ 3 $ به دست میآید.
مسئلهٔ کلاسیک دیگر: «تعداد توابع1 از یک مجموعه $ n $ عضوی به مجموعه $ m $ عضوی که پوشا نیستند2» را میتوان با کمک حالتهای نامطلوب (توابعی که لااقل یک عضو از مجموعهٔ مقصد را پوشش نمیدهند) محاسبه کرد، اما این مسئله نیاز به اصل شمول و عدم شمول دارد که خود از همین ایدهٔ شمارش حالتهای نامطلوب الهام گرفته است.
چالشهای مفهومی
❓ چالش ۱: آیا همیشه میتوانیم حالت نامطلوب را سادهتر از حالت مطلوب پیدا کنیم؟
خیر. روش مکمل زمانی مؤثر است که شرط مطلوب شامل عبارتی مانند «حداقل یک»، «حداقل یکی از ویژگیها» یا «نه همه» باشد. در این حالت، شرط نامطلوب به «هیچکدام» یا «همه خلاف» تبدیل میشود که معمولاً شمارش آن سادهتر است. اگر شرط مطلوب از ابتدا ساده باشد (مثلاً «همه زوج باشند») روش مستقیم کارآمدتر است.
❓ چالش ۲: چه زمانی باید از اصل شمول و عدم شمول به جای تفریق ساده استفاده کنیم؟
وقتی بیش از یک شرط نامطلوب داریم و این شروط با هم همپوشانی دارند (مانند «حداقل یکی از چند ویژگی نداشته باشد») باید از اصل شمول و عدم شمول3 استفاده کنیم. در این حالت، تعداد حالتهای نامطلوب برابر اجتماع چند مجموعه است و نمیتوان به سادگی یک عبارت را از کل کم کرد.
❓ چالش ۳: آیا روش حالتهای نامطلوب فقط در ترکیبیات کاربرد دارد؟
خیر. این روش در نظریهٔ احتمال، جبر، نظریه اعداد (مثلاً شمارش اعداد همنهشت با یک عدد به پیمانهٔ معین)، علوم کامپیوتر (تعداد رشتههای باینری فاقد الگو) و حتی آمار (محاسبهٔ توان آزمون با استفاده از خطای نوع دوم) کاربرد گسترده دارد. هرجا که فضای حالتها قابل شمارش باشد و مکمل شرط خوشرفتارتر به نظر برسد، میتوان از این روش استفاده کرد.
جمعبندی
روش شمارش حالتهای نامطلوب (یا اصل مکمل) یک راهبرد پایهای در ترکیبیات است که به جای شمردن مستقیم حالتهای مطلوب، تعداد کل حالتها را منهای حالتهای مخالف شرط میکند. این روش زمانی ایدهآل است که شرط مطلوب شامل عبارت «حداقل یک بار» یا «حداقل یکی از ویژگیها» باشد و شرط نامطلوب به «هیچکدام» تبدیل شود. با استفاده از این تکنیک، بسیاری از مسائل دبیرستانی شامل انتخاب افراد، رمزگذاری، پرتاب تاس، و شمارش اعداد به سرعت و با کمترین خطا حل میشوند. درک این روش، پایهٔ یادگیری اصل شمول و عدم شمول و بسیاری از مباحث پیشرفتهتر احتمال است.
پاورقی
1 تابع (Function): رابطهای که هر عضو دامنه را به دقیقاً یک عضو همدامنه نسبت میدهد.
2 پوشا بودن (Surjectivity): تابعی که همهٔ اعضای مجموعهٔ مقصد، تصویر حداقل یک عضو از دامنه هستند.
3 اصل شمول و عدم شمول (Inclusion-Exclusion Principle): قاعدهای برای محاسبهٔ اندازهٔ اجتماع چند مجموعه با جمع اندازهٔ مجموعهها و تفریق اندازهٔ اشتراکهای دوتایی و افزودن اشتراکهای سهتایی و ...