ইনক্লুশন-এক্সক্লুশন প্রিন্সিপল

১ · কেন সরল যোগ ভুল হতে পারে

L12-এ আমরা শিখেছি যোগের নিয়ম — যদি দুটো বিকল্প পরস্পর-বিচ্ছিন্ন (mutually exclusive) হয়, তাহলে $|A|+|B|$ সঠিক উত্তর দেয়। কিন্তু যদি $A$ ও $B$ ওভারল্যাপ করে (কিছু বস্তু উভয় সেটেই থাকে), তাহলে সরল যোগ ওভারল্যাপ করা অংশটিকে দুইবার গুনে ফেলে। এই ভুল ঠিক করার সূত্রই ইনক্লুশন-এক্সক্লুশন প্রিন্সিপলInclusion-Exclusion Principleএকাধিক ওভারল্যাপিং সেটের ইউনিয়নের আকার সঠিকভাবে গোনার সূত্র — প্রথমে সব একক সেট যোগ করো, তারপর সব জোড়া-ওভারল্যাপ বাদ দাও (দ্বিগুণ গণনা ঠিক করতে), তারপর ত্রয়ী-ওভারল্যাপ আবার যোগ করো (অতিরিক্ত বাদ দেওয়া ঠিক করতে) — এভাবে চলতে থাকে।।

২ · উদাহরণ — ১০০ শিক্ষার্থী

১০০ জন শিক্ষার্থীর মধ্যে ৬০ জন গণিত কোর্সে, ৪৫ জন সিএস কোর্সে, এবং ২৫ জন উভয় কোর্সেই ভর্তি হয়েছে। কতজন অন্তত একটি কোর্সে ভর্তি হয়েছে?

# ২-সেট ইনক্লুশন-এক্সক্লুশন যাচাই — ১০০ শিক্ষার্থী উদাহরণ
A = set(range(1, 61))    # ৬০ জন গণিত কোর্সে (আইডি ১-৬০)
B = set(range(36, 81))   # ৪৫ জন সিএস কোর্সে (আইডি ৩৬-৮০), ওভারল্যাপ ৩৬-৬০ = ২৫ জন

formula = len(A) + len(B) - len(A & B)
brute = len(A | B)

print("|A| =", len(A), " |B| =", len(B), " |A∩B| =", len(A & B))
print("সূত্র দিয়ে |A∪B|:", formula)
print("ব্রুট-ফোর্স |A∪B|:", brute)
print("দুটো মিলে গেছে:", formula == brute)

৩ · ৩-সেট সূত্র

তিনটি সেটের ক্ষেত্রে প্যাটার্নটি চলতে থাকে — একক সেট যোগ করো, জোড়া-ওভারল্যাপ বাদ দাও, তারপর ত্রয়ী-ওভারল্যাপ আবার যোগ করো (কারণ এটি তিনটি জোড়া-বিয়োগেই তিনবার বাদ হয়ে গেছে, একবার ফেরত দিতে হবে):

উদাহরণ: ১ থেকে ৩০ পর্যন্ত সংখ্যার মধ্যে যেগুলো ২, ৩, অথবা ৫ দ্বারা বিভাজ্য, তাদের সংখ্যা বের করুন। এখানে $A$=২-এর গুণিতক, $B$=৩-এর গুণিতক, $C$=৫-এর গুণিতক।

# ৩-সেট ইনক্লুশন-এক্সক্লুশন যাচাই — ১-৩০ এর মধ্যে ২, ৩, ৫-এর গুণিতক
nums = set(range(1, 31))
A = {n for n in nums if n % 2 == 0}
B = {n for n in nums if n % 3 == 0}
C = {n for n in nums if n % 5 == 0}

formula = (len(A) + len(B) + len(C)
           - len(A & B) - len(A & C) - len(B & C)
           + len(A & B & C))
brute = len(A | B | C)

print("|A|, |B|, |C| =", len(A), len(B), len(C))
print("|A∩B|, |A∩C|, |B∩C| =", len(A & B), len(A & C), len(B & C))
print("|A∩B∩C| =", len(A & B & C))
print("সূত্র দিয়ে |A∪B∪C|:", formula)
print("ব্রুট-ফোর্স |A∪B∪C|:", brute)
print("দুটো মিলে গেছে:", formula == brute)