متمم در شمارش: روش حل که در آن «حالات نامطلوب» شمرده و از «کل حالات» کم می‌شود

با روش مکمل، مسائل پیچیده شمارش را با شمردن حالات نامطلوب و کسر از کل حالات ساده‌تر حل کنید.

در شمارش‌های ترکیبیاتی، گاهی مستقیماً شمردن حالت‌های مطلوب دشوار است. روش متمم (مکمل) با محاسبهٔ «کل حالات» و کسر «حالات نامطلوب» راه‌حلی هوشمندانه ارائه می‌دهد. این مقاله با زبانی ساده و مثال‌های ملموس، کاربرد اصل متمم را در مسائل متنوع شمارش شامل جایگشت، ترکیب، و قوانین جمع و ضرب توضیح می‌دهد.

روش متمم¹ بر پایهٔ یک ایدهٔ ساده بنا شده است: گاهی اوقات شمردن مستقیم چیزهایی که می‌خواهیم سخت است، اما شمردن چیزهایی که نمی‌خواهیم آسان است. در این مواقع، می‌توانیم همهٔ حالت‌های ممکن را بشماریم، حالت‌های نامطلوب را از آن کم کنیم، و به جواب برسیم.

فرمول کلی روش متمم:$\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$

مشاهده می‌کنید که چگونه روش متمم مسئله را به یک تفریق ساده تبدیل کرد.

اصل متمم در جایگشت² نیز کاربرد فراوان دارد. مثلاً چند جایگشت از حروف کلمهٔ گلستان داریم که حرف «الف» در آنها قبل از «ت» نیامده باشد؟ بررسی تمام حالاتی که الف قبل از ت نیست (یعنی ت قبل از الف است) مستقیم دشوار است. اما می‌دانیم:

• کل جایگشت‌های کلمهٔ 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 (اصل شمول و عدم شمول³): $333 + 200 - 66 = 467$
• اعداد نامطلوب (بخش‌پذیر بر 3 یا 5): $467$
• اعداد مطلوب (نه بر 3 و نه بر 5): $1000 - 467 = 533$

روش متمم یکی از قدرتمندترین ابزارهای جعبهابزار ترکیبیات است. با تبدیل مسائل «حداقل» به «هیچ» و «حداکثر» به «همه»، پیچیدگی محاسبات را کاهش می‌دهد. به‌خاطر داشته باشید: همیشه ابتدا بررسی کنید که آیا شمردن نقطه‌ی مقابل ساده‌تر است؟ اگر پاسخ مثبت است، دست به کار شوید و با تفریق، مسئله را در کوتاه‌ترین زمان ممکن حل کنید.