148 — Inclusion-Exclusion Hard¶

Counting জোড়ার প্রথমটা। Level 3-এর inclusion-exclusion (044) আর derangement (050) এবার বড় মঞ্চে ফিরছে। মূল ছাঁচ: "অন্তত একটা খারাপ property আছে" গোনা কঠিন হলে, উল্টে গোনো — "কোনো খারাপ property নেই" — sign বদলে বদলে যোগ-বিয়োগ করে। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী)।

Source¶

Original source: Inclusion-exclusion principle (derangements, surjections)
Platform: CP-Algorithms — https://cp-algorithms.com/combinatorics/inclusion-exclusion.html
Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
Difficulty: Hard
Pattern: forbidden properties (sign-সহ subset যোগফল)
Basic idea inherited from: 044 (inclusion-exclusion), 050 (derangement)

1. Problem in simple words¶

দুটো classic counting দিয়ে hard IE শিখব:

Derangement: n জন লোক, প্রত্যেকের একটা নিজের চেয়ার। কতভাবে সবাইকে বসানো যায় যেন কেউ নিজের চেয়ারে না বসে? (n=4 → 9)
Surjection (onto function): nটা আলাদা বল kটা আলাদা বাক্সে রাখা, যেন প্রতিটা বাক্সে অন্তত একটা বল থাকে — কতভাবে? (n=4, k=2 → 14)

দুটোতেই সরাসরি গোনা কঠিন (নিষিদ্ধ শর্ত জড়ানো)। সমাধান একই অস্ত্রে: inclusion-exclusion — "সব বিন্যাস" থেকে শুরু করে "খারাপ" কেসগুলো sign বদলে বদলে যোগ-বিয়োগ।

এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; 044/050 ঝালিয়ে ফিরলে এটা চেনা লাগবে।

2. What is the math idea?¶

মূল ধারণা inclusion-exclusion principle (IE):

"কোনো খারাপ property নেই" = সব − (1টা property থাকা)
                              + (2টা property একসাথে)
                              − (3টা একসাথে) + ...

প্রতিটা k-property intersection-এ sign = (−1)^k

কেন sign বদলায়? কারণ "অন্তত একটা খারাপ" গুনতে গেলে overlap বারবার গোনা হয়; এক-property যোগ করলে দুই-property দুবার ঢোকে, তাই বিয়োগ করতে হয়; তিন-property আবার যোগ — এই দোলনই (−1)^k। Derangement-এ "খারাপ" = কেউ নিজের জায়গায়; surjection-এ "খারাপ" = কোনো বাক্স খালি।

3. Which basic idea does this inherit from?¶

দুই শিকড়: inclusion-exclusion (044) আর derangement (050)। 044 থেকে এসেছে মূল sign-বদল যোগ-বিয়োগ ছাঁচ; 050 থেকে derangement-এর ধারণা — কিন্তু সেখানে হয়তো recurrence (D(n) = (n−1)(D(n−1)+D(n−2))) দিয়ে শিখেছিলে, এখানে দেখব এর IE-চেহারা।

নতুন যেটা যোগ হলো: IE-কে forbidden property-র সাধারণ কাঠামোয় দেখা — কোন "খারাপ গুণ" বাদ দিতে হবে সেটা চিনে, তার উপর IE। আর surjection দিয়ে দেখি একই ছাঁচ ভিন্ন problem-এ — "কোনো বাক্স খালি নয়"। এটা 044-এর IE আর 050-এর derangement-এর hard, generalized রূপ।

4. Real-life analogy¶

ভাবো একটা পার্টিতে অতিথিদের উপহার বিনিময় (Secret Santa) — কিন্তু নিয়ম: কেউ নিজের আনা উপহার নিজে পাবে না। কতভাবে উপহার বিলি করা যায়?

সরাসরি গোনা কঠিন। তাই উল্টো — সব সম্ভাব্য বিলি (n!) থেকে "খারাপ" কেস বাদ দাও। "ব্যক্তি 1 নিজেরটা পেল" এমন কেস বাদ দাও, "ব্যক্তি 2 নিজেরটা পেল"-ও — কিন্তু যেখানে দুজনেই নিজেরটা পেল, সেটা দুবার বাদ পড়ল, তাই একবার যোগ করে ফেরত দাও। তিনজন... আবার বাদ। এই "বাদ দাও, বেশি বাদ পড়লে ফেরত দাও, আবার..." দোলনই inclusion-exclusion — overlap-এর হিসাব ঠিক রাখার সহজাত উপায়।

5. Visual explanation¶

Derangement-এ IE-র sign-দোলন (n = 3):

D(n) = Σ_{k=0}^{n} (−1)^k · C(n,k) · (n−k)!
       └─ k জন নির্দিষ্ট লোক নিজের জায়গায় "আটকানো", বাকিরা যেমন খুশি ((n−k)!)

n = 3:
  k=0:  +C(3,0)·3! = +1·6 = +6     (সব বিন্যাস)
  k=1:  −C(3,1)·2! = −3·2 = −6     (অন্তত 1 জন নিজের জায়গায়, বাদ)
  k=2:  +C(3,2)·1! = +3·1 = +3     (2 জন — overlap, ফেরত)
  k=3:  −C(3,3)·0! = −1·1 = −1     (3 জনই — আবার বাদ)
  ----------------------------------
  D(3) = 6 − 6 + 3 − 1 = 2 ✓

প্রথম কয়েকটা: D(0..6) = 1, 0, 1, 2, 9, 44, 265

লক্ষ করো — sign +/−/+/− করে দুলছে, প্রতিটা (−1)^k। এই দোলনই overlap-এর double-counting ঠিক করে।

6. Example input and output¶

Derangement D(n):
n     D(n)    যোগ-বিয়োগ
-----------------------------------------------
0     1       খালি বিন্যাস — শূন্যভাবে "ঠিক"
1     0       একজন — নিজের জায়গা ছাড়া উপায় নেই
3     2       6 − 6 + 3 − 1
4     9
5     44

Surjection (n বল -> k বাক্স, কোনো বাক্স খালি নয়):
n  k   উত্তর   কীভাবে (IE: k^n − C(k,1)(k−1)^n + ...)
-----------------------------------------------------
4  2   14      2⁴ − 2·1⁴ = 16 − 2
3  3   6        = 3! (সব bijection)
5  3   150
n  k>n  0       বল কম, প্রতি বাক্সে অন্তত একটা অসম্ভব

মূল edge case: D(0) = 1 (খালি বিন্যাস শূন্যভাবে derangement); D(1) = 0; আর surjection-এ k > n হলে 0 (বল কম পড়ে)।

7. Brute force thinking¶

IE না জেনে — সরাসরি enumerate করা। Derangement: সব n! permutation ঘুরে যেগুলোয় কেউ নিজের জায়গায় নেই গুনো:

from itertools import permutations, product


def derangement_brute(n):
    count = 0
    for p in permutations(range(n)):
        if all(p[i] != i for i in range(n)):       # কেউ নিজের জায়গায় নয়?
            count += 1
    return count


def surjection_brute(n, k):
    count = 0
    for f in product(range(k), repeat=n):          # প্রতিটা বলের বাক্স
        if len(set(f)) == k:                        # সব বাক্স ব্যবহৃত?
            count += 1
    return count

দুটোই সংজ্ঞার হুবহু — ঠিক উত্তর দেয় (derangement_brute(4) → 9)। আর IE সূত্র যাচাইয়ের নিখুঁত মাপকাঠি। কিন্তু n! বা k^n — দ্রুত অসম্ভব।

8. Why brute force may be slow¶

Derangement-এ n! permutation, surjection-এ k^n function — দুটোই বিস্ফোরক:

derangement n = 12  ->  12! ≈ 48 কোটি         (ধীর)
derangement n = 20  ->  20! ≈ 2×10^18          (অসম্ভব)
surjection k^n, n=30, k=5  ->  5^30            (কল্পনাতীত)

IE সূত্র: derangement O(n), surjection O(k) টা term

মূল কথা — IE পুরো enumeration-কে কয়েকটা term-এর যোগফলে গুটিয়ে দেয়; exponential/factorial থেকে নেমে linear।

9. Better thinking¶

মূল insight: "কোনো খারাপ property নেই" সরাসরি গোনার বদলে — সব থেকে শুরু করে property-গুলো sign বদলে যোগ-বিয়োগ:

Derangement: D(n) = Σ (−1)ᵏ C(n,k) (n−k)!। k জনকে নিজের জায়গায় "আটকে" (C(n,k) উপায়), বাকি (n−k) জন যেমন খুশি ((n−k)!), sign (−1)ᵏ।
Surjection: Σ (−1)ⁱ C(k,i) (k−i)ⁿ। iটা বাক্স "নিষিদ্ধ" করে বাকি (k−i) বাক্সে সব বল, sign (−1)ⁱ।

দুটোই কয়েকটা term-এর যোগ — O(n) বা O(k)। আর property-র সংখ্যা subset-আকারে বাড়লে bitmask দিয়ে subset enumerate করে (−1)^popcount (044 + level 4-এর bitmask-এর মিলন)।

10. Thinking tweak¶

এক লাইনের "আহা": "অন্তত একটা খারাপ" সরাসরি গুনতে যেও না — "সব" থেকে শুরু করে খারাপ property-গুলো (−1)ᵏ sign-এ যোগ-বিয়োগ করো; overlap আপনাআপনি ঠিক হয়।

সবচেয়ে বড় ফাঁদ: sign-এর হিসাব হারানো (concept-notes mistake #10)। kটা property-র intersection-এ sign (−1)ᵏ — term লেখার আগে ছোট case-এ (যেমন n=3) sign-pattern হাতে লিখে নাও (+, −, +, −...)। আর কোনটা "খারাপ property" সেটা পরিষ্কার সংজ্ঞায়িত করা জরুরি — derangement-এ "i নিজের জায়গায়", surjection-এ "বাক্স i খালি"।

11. Step-by-step dry run¶

Surjection n = 4 বল, k = 2 বাক্স — IE-তে:

সূত্র: Σ_{i=0}^{2} (−1)ⁱ C(2,i) (2−i)⁴।
i = 0: +C(2,0)·2⁴ = +1·16 = 16। (সব function, কোনো বিধিনিষেধ নেই)।
i = 1: −C(2,1)·1⁴ = −2·1 = −2। (1টা বাক্স খালি — অর্থাৎ সব বল এক বাক্সে; 2 ভাবে এমন হয়, বাদ)।
i = 2: +C(2,2)·0⁴ = +1·0 = 0। (2টাই খালি — অসম্ভব)।
যোগ: 16 − 2 + 0 = 14। surjection = 14। brute force-ও 14 বলে ✓।

12. Python solution¶

from math import comb, factorial


def derangement(n):
    """n জনের derangement — কেউ নিজের জায়গায় নয়, IE-তে।"""
    return sum((-1) ** k * comb(n, k) * factorial(n - k) for k in range(n + 1))


def surjections(n, k):
    """n বল -> k বাক্স, কোনো বাক্স খালি নয় (onto), IE-তে।"""
    return sum((-1) ** i * comb(k, i) * (k - i) ** n for i in range(k + 1))


from itertools import permutations, product


def derangement_brute(n):
    """সব permutation — যাচাইয়ের জন্য।"""
    return sum(1 for p in permutations(range(n))
               if all(p[i] != i for i in range(n)))


def surjection_brute(n, k):
    """সব function — যাচাইয়ের জন্য।"""
    return sum(1 for f in product(range(k), repeat=n) if len(set(f)) == k)


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert [derangement(n) for n in range(7)] == [1, 0, 1, 2, 9, 44, 265]
assert surjections(4, 2) == 14
assert surjections(3, 3) == 6                      # = 3!
assert surjections(2, 5) == 0                      # বল কম, কোনো onto নেই

# brute force-এর সাথে মিল (IE সূত্রের প্রমাণ)
for n in range(7):
    assert derangement(n) == derangement_brute(n), n

for n in range(6):
    for k in range(5):
        assert surjections(n, k) == surjection_brute(n, k), (n, k)

# derangement আর !n / e (নিকটতম পূর্ণসংখ্যা) সম্পর্ক — sanity
# D(n) ≈ n!/e; n=5: 44, round(120/2.71828) = 44
from math import e
for n in range(2, 8):
    assert derangement(n) == round(factorial(n) / e), n

print([derangement(n) for n in range(6)])   # [1, 0, 1, 2, 9, 44]
print(surjections(4, 2))                     # 14
print(surjections(5, 3))                     # 150
print("সব test pass!")

13. Line-by-line explanation¶

    return sum((-1) ** k * comb(n, k) * factorial(n - k) for k in range(n + 1))

Derangement-এর IE সূত্র। প্রতিটা k-এর জন্য: comb(n,k) = কোন k জনকে নিজের জায়গায় আটকাব তার উপায়, factorial(n-k) = বাকিদের যেমন খুশি সাজানো, (-1)**k = sign-দোলন (overlap সংশোধন)। সব k-এর যোগ।

    return sum((-1) ** i * comb(k, i) * (k - i) ** n for i in range(k + 1))

Surjection-এর IE। comb(k,i) = কোন iটা বাক্স খালি ধরব, (k-i)**n = বাকি বাক্সে সব n বল যেভাবে খুশি, (-1)**i = sign। "কোনো বাক্স খালি নয়" = সব − (1 খালি) + (2 খালি) − ...।

    assert derangement(n) == round(factorial(n) / e), n

মজার যাচাই — derangement D(n) সবচেয়ে কাছের পূর্ণসংখ্যা n!/e-এর (IE-যোগফল আসলে e⁻¹-এর Taylor series-এর truncation)। এটা স্বাধীনভাবে সূত্র ঠিক কিনা দেখায়।

বাকি assert গুলো brute force-এর সাথে সব ছোট case-এ মিলিয়ে দেখে। সব মিললে সব test pass!।

14. Output walkthrough¶

চালালে ছাপবে:

[1, 0, 1, 2, 9, 44]
14
150
সব test pass!

প্রথম লাইন derangement D(0..5)। দ্বিতীয় surjection n=4,k=2 → 14। তৃতীয় n=5,k=3 → 150। তার আগের সব assert চুপচাপ pass — IE সূত্র, brute force, আর n!/e তিনটাই একমত। সবশেষে সব test pass!।

15. Time complexity¶

Derangement: O(n) — n+1টা term (comb/factorial precompute ধরলে)। Surjection: O(k) — k+1টা term। brute force ছিল O(n!) / O(k^n) — IE সেটাকে linear-এ নামিয়েছে। (বড় mod-এ comb modular inverse-এ, তবু linear।)

16. Space complexity¶

O(1) — যোগফল চলতে চলতে জমে, কোনো বড় array লাগে না (factorial/comb precompute করলে O(n))। brute version factorial/exponential কাজ করে কিন্তু স্থান কম; আসল সমাধান O(1)–O(n)।

17. Common mistakes¶

Sign-এর হিসাব হারানো — k-property intersection-এ sign (−1)ᵏ; ছোট case-এ pattern (+,−,+,−) আগে লিখে নাও (concept-notes mistake #10)।
"খারাপ property" অস্পষ্ট রাখা — কোনটা বাদ দিচ্ছি (i নিজের জায়গায় / বাক্স খালি) পরিষ্কার না হলে term ভুল।
Derangement-এ D(0) ভুল — D(0) = 1 (খালি বিন্যাস), D(1) = 0; এগুলো base হিসেবে গুরুত্বপূর্ণ।
Surjection-এ k > n ভুলে যাওয়া — বল কম হলে উত্তর 0; সূত্র নিজেই 0 দেয়, কিন্তু intuition রাখো।
IE আর সরাসরি যোগ গুলিয়ে ফেলা — "অন্তত একটা" সরাসরি যোগ করলে overlap বারবার গোনা হয়; sign-বদল ছাড়া IE নয়।

18. Harder problems that inherit this idea¶

CP-Algorithms — Inclusion-Exclusion (https://cp-algorithms.com/combinatorics/inclusion-exclusion.html) — forbidden property-র নানা প্রয়োগ, bitmask-IE।
CSES — Counting / Christmas Party (https://cses.fi/problemset/) — derangement-ঘরানা সরাসরি problem।
Codeforces — combinatorics + IE tag (https://codeforces.com/problemset?tags=combinatorics) — subset-আকারে property বাড়ার hard IE।

19. Pattern learned¶

Hard inclusion-exclusion (forbidden properties) — "অন্তত একটা খারাপ property" এড়াতে: সব − (1 fix) + (2 fix) − ..., প্রতি k-property-তে sign (−1)ᵏ। Derangement = Σ(−1)ᵏC(n,k)(n−k)!, surjection = Σ(−1)ⁱC(k,i)(k−i)ⁿ। property বেশি হলে bitmask + (−1)^popcount।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "forbidden property গোনায় inclusion-exclusion — সব থেকে শুরু করে (−1)ᵏ sign-এ যোগ-বিয়োগ। derangement = Σ(−1)ᵏC(n,k)(n−k)!, surjection = Σ(−1)ⁱC(k,i)(k−i)ⁿ। sign-pattern ছোট case-এ আগে লিখে নাও।"

পরের ধাপ → 149 — Combinatorics with DP (counting জোড়ার দ্বিতীয় — counting DP, Catalan)। শিকড় → 044 — Inclusion-Exclusion, 050 — Derangement।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।