متمم در شمارش: روش حل با شمردن حالات نامطلوب
در بسیاری از مسائل شمارش، محاسبهٔ مستقیم تعداد حالتهای مطلوب دشوار است. روش «متمم» یا «حالتهای نامطلوب» راهکاری ساده و کارآمد ارائه میدهد: ابتدا تعداد کل حالتهای ممکن را میشماریم، سپس تعداد حالتهای نامطلوب (حالتهایی که شرط مسئله را نقض میکنند) را محاسبه کرده و از کل کم میکنیم. این روش در شمارش با قیدهای «حداقل»، «حداکثر» و «حداقل یک بار» کاربرد گستردهای دارد. در این مقاله با مثالهای متنوع و گامهای گویا، کاربرد اصل متمم را در ترکیبیات[1] میآموزید.
۱. اصل پایهٔ متمم: از کل به مطلوب
در بسیاری از مسائل شمارش، پیدا کردن مستقیم تعداد حالتهایی که شرط مورد نظر را برآورده میکنند، پیچیده و زمانبر است. اصل متمم میگوید: اگر فضای نمونه[2] محدودی داشته باشیم، تعداد حالتهای مطلوب برابر است با تعداد کل حالتها منهای تعداد حالتهای نامطلوب. به عبارت دیگر:
در این رابطه، $N$ نشاندهندهٔ تعداد حالتهاست. این روش زمانی بسیار مفید است که شمارش حالتهای نامطلوب سادهتر از شمارش مستقیم حالتهای مطلوب باشد.
۲. کاربرد در مسائل «حداقل» و «حداکثر»
یکی از رایجترین کاربردهای روش متمم، مسائلی هستند که عبارت «حداقل یک بار» یا «حداقل یکی از...» در آنها دیده میشود. در این موارد، حالت نامطلوب یعنی «هیچ کدام» یا «صفر بار». بیایید با یک مثال گامبهگام پیش برویم.
مثال ۱: از بین اعداد $1$ تا $20$، چند عدد بر $3$ یا $5$ بخشپذیرند؟
حل مستقیم: باید اعداد بخشپذیر بر $3$ یا $5$ را بشماریم. این کار با اصل شمول و طرد[3] انجام میشود که گاهی پیچیده است.
حل با روش متمم:
- تعداد کل اعداد: $20$.
- حالت نامطلوب: اعدادی که نه بر $3$ بخشپذیرند و نه بر $5$. شمارش مستقیم این اعداد آسانتر است: از $1$ تا $20$، اعداد بخشپذیر بر $3$ یا $5$ را حذف میکنیم. تعداد بخشپذیران بر $3$ برابر $ \lfloor \frac{20}{3} \rfloor = 6 $، بر $5$ برابر $4$ و بر $15$ برابر $1$ است. پس تعداد بخشپذیران بر $3$ یا $5$ میشود $6+4-1=9$. بنابراین حالت نامطلوب: $20-9=11$ عدد.
- تعداد مطلوب = $20 - 11 = 9$.
همانطور که میبینید، ابتدا حالت نامطلوب (اعدادی که شرط را نقض میکنند) شمرده شد.
۳. کاربرد در مسائل جایگشت با قید «دستکم یک بار»
یکی از رایجترین کاربردهای روش متمم در مسائل جایگشت[4] و ترکیب[5] با تکرار است. فرض کنید میخواهیم تعداد رشتههای $n$ حرفی از حروف الفبای $m$ تایی را پیدا کنیم که در آنها حداقل یک بار حرف خاصی آمده باشد.
مثال ۲: با حروف $ \{A,B,C\} $، چند کلمهٔ $4$ حرفی (با تکرار مجاز) میتوان ساخت که حداقل یک $A$ داشته باشد؟
حل گامبهگام:
- کل حالات: برای هر $4$ جایگاه، $3$ انتخاب داریم: $3^4 = 81$.
- حالات نامطلوب: کلماتی که هیچ $A$ ندارند. در این صورت فقط از $ \{B,C\} $ استفاده میشود: $2^4 = 16$.
- حالات مطلوب:$81 - 16 = 65$.
۴. جدول مقایسهٔ روش مستقیم و روش متمم
| نوع مسئله | روش مستقیم | روش متمم (حالات نامطلوب) |
|---|---|---|
| حداقل یک حرف خاص در رشتهٔ $n$ تایی | جمع چند جمله (توزیع دوجملهای) | کل - حالت بدون آن حرف |
| حداقل یک زوج در انتخاب اعداد | حذف حالتهای بدون زوج دشوار | کل - حالتهای کاملاً فرد |
| اعداد بخشپذیر بر حداقل یکی از چند عدد | استفاده از اصل شمول و طرد (پرتکرار) | کمتر کاربرد دارد |
۵. کاربرد عملی: رمزهای عبور با حداقل یک رقم
فرض کنید میخواهیم تعداد رمزهای عبور $4$ رقمی (هر رقم از $0$ تا $9$) را پیدا کنیم که حداقل یک رقم فرد داشته باشند. با روش متمم:
- کل رمزها: $10^4 = 10000$.
- حالت نامطلوب (هیچ رقم فردی وجود نداشته باشد یعنی همهٔ ارقام زوج): ارقام زوج $\{0,2,4,6,8\}$ تعداد $5$ تا. بنابراین $5^4 = 625$ رمز.
- تعداد مطلوب: $10000 - 625 = 9375$.
این مثال نشان میدهد که چگونه روش متمم در مسائل روزمره مانند امنیت رمزهای عبور کاربرد مستقیم دارد.
۶. چالشهای مفهومی
چالش ۱: چه زمانی استفاده از روش متمم اشتباه است؟
وقتی که شمارش حالتهای نامطلوب به اندازهٔ حالتهای مطلوب دشوار باشد یا زمانی که فضای نمونه به سادگی قابل تعریف نباشد. همچنین اگر «متمم» خود شامل چندین زیرحالت پیچیده باشد، روش مستقیم ممکن است بهتر باشد.
چالش ۲: چگونه بفهمیم مسئله «حداقل یک بار» با متمم حل میشود؟
هرگاه در مسئله عبارت «دستکم یک»، «حداقل یک» یا «حداقل یکی از» دیده شود، حالت نامطلوب «هیچ کدام» یا «صفر بار» خواهد بود که معمولاً شمارش آن ساده است. بنابراین میتوانید با اطمینان از روش متمم استفاده کنید.
چالش ۳: در مسائل ترکیب با محدودیت «حداکثر» چه کنیم؟
برای «حداکثر $k$» بار، حالت نامطلوب «بیش از $k$» بار است که خود شامل حالتهای $k+1$ و $k+2$ و ... میشود. در این موارد گاهی روش مستقیم بهتر عمل میکند، مگر اینکه تعداد کل حالتها محدود باشد.
۷. روش گامبهگام برای حل با متمم
برای حل هر مسئلهٔ شمارش با روش متمم، میتوانید از چهار گام زیر پیروی کنید:
- شناسایی شرط مطلوب: دقیقاً مشخص کنید چه حالتهایی «مطلوب» هستند.
- تعریف حالت نامطلوب: حالت نامطلوب، نقیض[6] شرط مطلوب است. یعنی حالتهایی که شرط را برآورده نمیکنند.
- شمارش کل حالتها: تعداد کل اعضای فضای نمونه را بدون هیچ قید اضافی محاسبه کنید.
- شمارش حالتهای نامطلوب: با استفاده از روشهای سادهتر (اغلب ضرب، جایگشت یا ترکیب) تعداد حالتهای نامطلوب را پیدا کنید.
- محاسبهٔ مطلوب:$N(مطلوب) = N(کل) - N(نامطلوب)$.
۸. مثال ترکیبی: انتخاب تیم با حداقل یک نفر از یک گروه
از میان $5$ پسر و $4$ دختر، میخواهیم یک تیم $3$ نفره انتخاب کنیم به طوری که حداقل یک پسر در تیم باشد. با روش متمم:
- کل حالات انتخاب $3$ نفر از $9$ نفر: $ \binom{9}{3} = 84 $.
- حالت نامطلوب (هیچ پسری، یعنی همه دختر): انتخاب $3$ نفر از $4$ دختر: $ \binom{4}{3} = 4 $.
- تعداد مطلوب: $84 - 4 = 80$.
اگر مستقیماً میخواستیم محاسبه کنیم، باید موارد «دقیقاً یک پسر»، «دقیقاً دو پسر» و «سه پسر» را جداگانه محاسبه و جمع میکردیم که زمانبرتر است.
پاورقیها
1ترکیبیات (Combinatorics): شاخهای از ریاضیات که به مطالعهٔ روشهای شمارش، چیدمان و ترکیب اشیاء میپردازد.
2فضای نمونه (Sample Space): مجموعهٔ همهٔ نتایج ممکن یک آزمایش تصادفی یا یک انتخاب مشخص.
3اصل شمول و طرد (Inclusion-Exclusion Principle): روشی برای شمارش اجتماع چند مجموعه که اشتراکهای آنها را نیز در نظر میگیرد.
4جایگشت (Permutation): چیدمان مرتب تعدادی شیء، که در آن ترتیب قرار گرفتن اهمیت دارد.
5ترکیب (Combination): انتخاب تعدادی شیء بدون در نظر گرفتن ترتیب.
6نقیض (Complement): در نظریهٔ مجموعهها، مجموعهٔ همهٔ اعضای جهانِ مورد بحث که در مجموعهٔ اصلی عضو نیستند.