Problem link ও উৎস
- **Original source:** Inclusion-exclusion principle (derangements, surjections)
- **Platform:** CP-Algorithms —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো classic counting দিয়ে hard IE শিখব:
1. **Derangement:** `n` জন লোক, প্রত্যেকের একটা নিজের চেয়ার। কতভাবে সবাইকে বসানো যায় যেন **কেউ নিজের চেয়ারে না বসে**? (`n=4` → 9)
2. **Surjection (onto function):** `n`টা আলাদা বল `k`টা আলাদা বাক্সে রাখা, যেন **প্রতিটা বাক্সে অন্তত একটা বল** থাকে — কতভাবে? (`n=4, k=2` → 14)
দুটোতেই সরাসরি গোনা কঠিন (নিষিদ্ধ শর্ত জড়ানো)। সমাধান একই অস্ত্রে: **inclusion-exclusion** — "সব বিন্যাস" থেকে শুরু করে "খারাপ" কেসগুলো sign বদলে বদলে যোগ-বিয়োগ।
> এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; 044/050 ঝালিয়ে ফিরলে এটা চেনা লাগবে।
### Input ও output {#6-example-input-and-output}
```text
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 (বল কম পড়ে)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পার্টিতে অতিথিদের উপহার বিনিময় (Secret Santa) — কিন্তু নিয়ম: **কেউ নিজের আনা উপহার নিজে পাবে না**। কতভাবে উপহার বিলি করা যায়?
সরাসরি গোনা কঠিন। তাই উল্টো — সব সম্ভাব্য বিলি (`n!`) থেকে "খারাপ" কেস বাদ দাও। "ব্যক্তি 1 নিজেরটা পেল" এমন কেস বাদ দাও, "ব্যক্তি 2 নিজেরটা পেল"-ও — কিন্তু যেখানে দুজনেই নিজেরটা পেল, সেটা দুবার বাদ পড়ল, তাই একবার যোগ করে ফেরত দাও। তিনজন... আবার বাদ। এই "বাদ দাও, বেশি বাদ পড়লে ফেরত দাও, আবার..." দোলনই inclusion-exclusion — overlap-এর হিসাব ঠিক রাখার সহজাত উপায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 রূপ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **inclusion-exclusion principle (IE)**:
```text
"কোনো খারাপ property নেই" = সব − (1টা property থাকা)
+ (2টা property একসাথে)
− (3টা একসাথে) + ...
প্রতিটা k-property intersection-এ sign = (−1)^k
```
কেন sign বদলায়? কারণ "অন্তত একটা খারাপ" গুনতে গেলে overlap বারবার গোনা হয়; এক-property যোগ করলে দুই-property দুবার ঢোকে, তাই বিয়োগ করতে হয়; তিন-property আবার যোগ — এই দোলনই `(−1)^k`। Derangement-এ "খারাপ" = কেউ নিজের জায়গায়; surjection-এ "খারাপ" = কোনো বাক্স খালি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
IE না জেনে — সরাসরি enumerate করা। Derangement: সব `n!` permutation ঘুরে যেগুলোয় কেউ নিজের জায়গায় নেই গুনো:
```python
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 — দুটোই বিস্ফোরক:
```text
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 খালি"।
### ছবিতে বোঝা {#5-visual-explanation}
Derangement-এ IE-র sign-দোলন (`n = 3`):
```text
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 ঠিক করে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
Surjection `n = 4` বল, `k = 2` বাক্স — IE-তে:
1. **সূত্র:** `Σ_{i=0}^{2} (−1)ⁱ C(2,i) (2−i)⁴`।
2. **i = 0:** `+C(2,0)·2⁴` = `+1·16` = 16। (সব function, কোনো বিধিনিষেধ নেই)।
3. **i = 1:** `−C(2,1)·1⁴` = `−2·1` = −2। (1টা বাক্স খালি — অর্থাৎ সব বল এক বাক্সে; 2 ভাবে এমন হয়, বাদ)।
4. **i = 2:** `+C(2,2)·0⁴` = `+1·0` = 0। (2টাই খালি — অসম্ভব)।
5. **যোগ:** `16 − 2 + 0 = 14`। surjection = **14**। brute force-ও 14 বলে ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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`-এর যোগ।
```text
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 খালি) − ...।
```text
assert derangement(n) == round(factorial(n) / e), n
```
মজার যাচাই — derangement `D(n)` সবচেয়ে কাছের পূর্ণসংখ্যা `n!/e`-এর (IE-যোগফল আসলে `e⁻¹`-এর Taylor series-এর truncation)। এটা স্বাধীনভাবে সূত্র ঠিক কিনা দেখায়।
বাকি `assert` গুলো brute force-এর সাথে সব ছোট case-এ মিলিয়ে দেখে। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
[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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **Sign-এর হিসাব হারানো** — `k`-property intersection-এ sign `(−1)ᵏ`; ছোট case-এ pattern (+,−,+,−) আগে লিখে নাও (concept-notes mistake #10)।
2. **"খারাপ property" অস্পষ্ট রাখা** — কোনটা বাদ দিচ্ছি (i নিজের জায়গায় / বাক্স খালি) পরিষ্কার না হলে term ভুল।
3. **Derangement-এ `D(0)` ভুল** — `D(0) = 1` (খালি বিন্যাস), `D(1) = 0`; এগুলো base হিসেবে গুরুত্বপূর্ণ।
4. **Surjection-এ `k > n` ভুলে যাওয়া** — বল কম হলে উত্তর 0; সূত্র নিজেই 0 দেয়, কিন্তু intuition রাখো।
5. **IE আর সরাসরি যোগ গুলিয়ে ফেলা** — "অন্তত একটা" সরাসরি যোগ করলে overlap বারবার গোনা হয়; sign-বদল ছাড়া IE নয়।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Inclusion-Exclusion** (