متمم در شمارش: هنر شمارش از راه نرفتن
با روش مکمل، مسائل پیچیده شمارش را با شمردن حالات نامطلوب و کسر از کل حالات سادهتر حل کنید.
در شمارشهای ترکیبیاتی، گاهی مستقیماً شمردن حالتهای مطلوب دشوار است. روش متمم (مکمل) با محاسبهٔ «کل حالات» و کسر «حالات نامطلوب» راهحلی هوشمندانه ارائه میدهد. این مقاله با زبانی ساده و مثالهای ملموس، کاربرد اصل متمم را در مسائل متنوع شمارش شامل جایگشت، ترکیب، و قوانین جمع و ضرب توضیح میدهد.
۱. تعریف و منطق روش متمم
روش متمم1 بر پایهٔ یک ایدهٔ ساده بنا شده است: گاهی اوقات شمردن مستقیم چیزهایی که میخواهیم سخت است، اما شمردن چیزهایی که نمیخواهیم آسان است. در این مواقع، میتوانیم همهٔ حالتهای ممکن را بشماریم، حالتهای نامطلوب را از آن کم کنیم، و به جواب برسیم.
فرمول کلی روش متمم:$\text{تعداد حالات مطلوب} = \text{تعداد کل حالات} - \text{تعداد حالات نامطلوب}$
این روش در واقع از اصل متمم مجموعهها در ریاضیات الهام گرفته شده است. اگر مجموعهٔ $U$ را جهانی و مجموعهٔ $A$ را حالتهای مطلوب در نظر بگیریم، متمم $A$ (یعنی $A'$) حالتهای نامطلوب خواهد بود. بنابراین: $n(A) = n(U) - n(A')$.
۲. کاربرد روش متمم در مسائل کدگذاری و رمز
فرض کنید میخواهیم تعداد کدهای 4 رقمی را محاسبه کنیم که حداقل یک رقم 7 دارند. شمارش مستقیم این کدها به دلیل حالتهای بسیار (یک بار تکرار، دو بار تکرار، و ...) پیچیده است. اما با روش متمم:
- کل کدهای 4 رقمی (صفر در خانهٔ اول مجاز نیست): $9 \times 10 \times 10 \times 10 = 9000$
- کدهای بدون رقم 7: برای هزارگان 8 حالت (غیرصفر و غیر 7) و برای سه جایگاه بعدی هر کدام 9 حالت (هر رقمی بجز 7): $8 \times 9 \times 9 \times 9 = 5832$
- کدهای مطلوب (حداقل یک 7): $9000 - 5832 = 3168$
۳. روش متمم در جایگشتها
اصل متمم در جایگشت2 نیز کاربرد فراوان دارد. مثلاً چند جایگشت از حروف کلمهٔ گلستان داریم که حرف «الف» در آنها قبل از «ت» نیامده باشد؟ بررسی تمام حالاتی که الف قبل از ت نیست (یعنی ت قبل از الف است) مستقیم دشوار است. اما میدانیم:
- کل جایگشتهای کلمهٔ 6 حرفی با حروف متمایز: $6! = 720$
- در تمام جایگشتها، در نیمی از موارد الف قبل از ت و در نیمی دیگر ت قبل از الف قرار میگیرد. پس تعداد حالاتی که الف قبل از ت است برابر $720 / 2 = 360$ میباشد.
- پس تعداد حالاتی که الف قبل از ت نیست نیز $360$ خواهد بود.
| روش حل | مثال (کد ۴ رقمی با حداقل یک ۷) | میزان پیچیدگی |
|---|---|---|
| شمارش مستقیم | حالات با یک ۷ + دو ۷ + سه ۷ + چهار ۷ | بالا |
| روش متمم | کل حالات (۹۰۰۰) - حالات بدون ۷ (۵۸۳۲) | پایین |
۴. کاربرد در ترکیببندی: انتخاب اعضای یک گروه
از یک کلاس 20 نفره میخواهیم یک تیم 5 نفره انتخاب کنیم. میخواهیم بدانیم در چند حالت تیم حداقل دو دختر دارد اگر کلاس دارای 8 دختر و 12 پسر باشد؟ شمارش مستقیم حالتهای «حداقل دو دختر» به معنی شمردن حالتهای ۲ دختر، ۳ دختر، ۴ دختر و ۵ دختر است. اما روش متمم سادهتر است:
- کل حالتهای انتخاب 5 نفر از 20: $C(20,5) = 15504$
- حالتهای نامطلوب (تیم کمتر از دو دختر دارد) شامل:
- بدون دختر: $C(12,5) = 792$
- دقیقاً یک دختر: $C(8,1) \times C(12,4) = 8 \times 495 = 3960$
- جمع حالتهای نامطلوب: $792 + 3960 = 4752$
- حالتهای مطلوب (حداقل دو دختر): $15504 - 4752 = 10752$
۵. مثال عملی: شمارش اعداد با شرایط خاص
چند عدد طبیعی بین 1 تا 1000 وجود دارد که بر 3 یا 5 (یا هر دو) بخشپذیر نباشند؟ یعنی نه بر 3 و نه بر 5 بخشپذیر باشند.
- کل اعداد: $1000$
- اعداد بخشپذیر بر 3: $\lfloor \frac{1000}{3} \rfloor = 333$
- اعداد بخشپذیر بر 5: $\lfloor \frac{1000}{5} \rfloor = 200$
- اعداد بخشپذیر بر 15 (هم بر 3 و هم بر 5): $\lfloor \frac{1000}{15} \rfloor = 66$
- اعداد بخشپذیر بر 3 یا 5 (اصل شمول و عدم شمول3): $333 + 200 - 66 = 467$
- اعداد نامطلوب (بخشپذیر بر 3 یا 5): $467$
- اعداد مطلوب (نه بر 3 و نه بر 5): $1000 - 467 = 533$
چالشهای مفهومی
❓ چالش ۱: چه زمانی اصلاً نمیتوان از روش متمم استفاده کرد؟
پاسخ زمانی که مجموعهٔ کل حالات یا مجموعهٔ حالات نامطلوب نامتناهی باشد یا شمارش آنها به اندازهٔ خود حالتهای مطلوب دشوار باشد. روش متمم وقتی مفید است که «نه» گفتن (شمردن نامطلوبها) آسانتر از «بله» گفتن باشد.
پاسخ زمانی که مجموعهٔ کل حالات یا مجموعهٔ حالات نامطلوب نامتناهی باشد یا شمارش آنها به اندازهٔ خود حالتهای مطلوب دشوار باشد. روش متمم وقتی مفید است که «نه» گفتن (شمردن نامطلوبها) آسانتر از «بله» گفتن باشد.
❓ چالش ۲: آیا روش متمم همیشه جواب کمتری از کل حالات میدهد؟
پاسخ خیر، اگر حالات نامطلوب بیشتر از نصف کل حالات باشند، جواب (حالات مطلوب) کمتر از نصف میشود، اما این کاهش صرفاً یک نتیجهٔ عددی است. مهم این است که تفریق همیشه یک عدد نامنفی به دست میدهد.
پاسخ خیر، اگر حالات نامطلوب بیشتر از نصف کل حالات باشند، جواب (حالات مطلوب) کمتر از نصف میشود، اما این کاهش صرفاً یک نتیجهٔ عددی است. مهم این است که تفریق همیشه یک عدد نامنفی به دست میدهد.
❓ چالش ۳: چگونه بفهمیم کدام حالتها را «نامطلوب» در نظر بگیریم؟
پاسخ عکس شرط مسئله را در نظر بگیرید. اگر مسئله میگوید «حداقل یک ویژگی»، نامطلوب «هیچ ویژگی» است. اگر میگوید «همهٔ ویژگیها»، نامطلوب «نداشتن دستکم یکی» است. همیشه «نه» شرط اصلی را بهعنوان حالت نامطلوب تعریف کنید.
پاسخ عکس شرط مسئله را در نظر بگیرید. اگر مسئله میگوید «حداقل یک ویژگی»، نامطلوب «هیچ ویژگی» است. اگر میگوید «همهٔ ویژگیها»، نامطلوب «نداشتن دستکم یکی» است. همیشه «نه» شرط اصلی را بهعنوان حالت نامطلوب تعریف کنید.
روش متمم یکی از قدرتمندترین ابزارهای جعبهابزار ترکیبیات است. با تبدیل مسائل «حداقل» به «هیچ» و «حداکثر» به «همه»، پیچیدگی محاسبات را کاهش میدهد. بهخاطر داشته باشید: همیشه ابتدا بررسی کنید که آیا شمردن نقطهی مقابل سادهتر است؟ اگر پاسخ مثبت است، دست به کار شوید و با تفریق، مسئله را در کوتاهترین زمان ممکن حل کنید.
پاورقی
[1] روش مکمل (Complement Method): در ترکیبیات، روشی برای شمارش که در آن تعداد اعضای یک مجموعه با کسر تعداد اعضای متمم آن از تعداد اعضای مجموعهٔ جهانی به دست میآید.
[2] جایگشت (Permutation): هر ترتیبخطی از اعضای یک مجموعه که در آن ترتیب قرار گرفتن عناصر مهم است.
[3] اصل شمول و عدم شمول (Inclusion-Exclusion Principle): اصلی برای شمارش تعداد اعضای اجتماع مجموعهها که جمع اعضای تکتک، منهای اشتراکهای دوتایی، بعلاوهٔ اشتراکهای سهتایی و ... را محاسبه میکند.
