Problem link ও উৎস
- **Original source:** Classic combinatorics (derangement)
- **Platform:** Classic combinatorics —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Medium
- **Pattern:** !n recurrence (derangement)
- **Basic idea inherited from:** 039 — Factorial (permutation-এর শর্তযুক্ত রূপ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা জিনিস তাদের নিজের নিজের জায়গায় আছে (জিনিস 1 জায়গা 1-এ, জিনিস 2 জায়গা 2-এ, ...)। এগুলোকে এমনভাবে আবার সাজাতে হবে যেন **কোনো জিনিসই তার নিজের জায়গায় না থাকে**। কত ভাবে করা যায়?
এই সংখ্যাকে বলে **derangement**, লেখা `!n` বা `D(n)`।
গল্প-রূপ: n জন তাদের টুপি একটা ঝুড়িতে রেখেছিল; এলোমেলোভাবে একটা করে তুলে নিচ্ছে — এমন কয়টা বিলি-ব্যবস্থা আছে যেখানে **কেউই** নিজের টুপি পেল না?
যেমন n=3 (টুপি 1,2,3): শুধু 231 আর 312 — কেউ নিজেরটা পায়নি। তাই `D(3) = 2`। ধারা: `D(0)=1, D(1)=0, D(2)=1, D(3)=2, D(4)=9, ...`।
### Input ও output {#6-example-input-and-output}
```text
n -> D(n)
-----------
0 -> 1 (খালি -> 1 ভাবে, বিশেষ নিয়ম)
1 -> 0 (একজন থাকলে নিজেরটাই পেতে বাধ্য -> 0 উপায়)
2 -> 1 (দুজন অদলবদল -> ঠিক 1)
3 -> 2
4 -> 9
5 -> 44
6 -> 265
7 -> 1854
```
Edge case: **D(0) = 1** (খালি বিলি, ঠিক একভাবে), আর **D(1) = 0** (একজন থাকলে নিজের টুপি পাওয়া ছাড়া উপায় নেই)। ধারাটা প্রায় `n!/e` হারে বাড়ে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো অফিসে "Secret Santa" — n জন কর্মী, প্রত্যেকে একটা করে নাম তুলবে কাকে উপহার দেবে। নিয়ম: **কেউ নিজের নাম তুলতে পারবে না** (নিজেকে উপহার দেওয়া অর্থহীন)।
সব নাম এমনভাবে বিলি করার কয়টা উপায় আছে যেখানে কেউই নিজের নাম পায়নি? — ঠিক `D(n)`!
মজার বাস্তবতা: n বড় হলেও, পুরোপুরি এলোমেলো করে বিলি করলে "কাকতালীয়ভাবে কেউ একজন নিজের নাম পেয়ে গেছে" হওয়ার সম্ভাবনা প্রায় 63% (= 1 − 1/e)। মানে valid Secret Santa পেতে প্রায়ই কয়েকবার চেষ্টা লাগে — derangement মোট permutation-এর মোটে ~37%।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা **039 (Factorial)**-এর উপর দাঁড়িয়ে। Factorial = সব permutation (যেমন খুশি সাজাও)। Derangement = সেই permutation-গুলোর **একটা সীমাবদ্ধ উপসেট** — যেখানে কোনো জিনিস নিজের জায়গায় নেই।
মূল সম্পর্ক: মোট permutation `n!`; তার মধ্যে "অন্তত একজন নিজেরটা পেল" বাদ দিলে derangement থাকে (এটাই inclusion-exclusion রূপ — তাই 044-এর সাথেও যোগ)। আর recurrence-এর "ব্যক্তি 1 কার টুপি পেল" শাখা-ভাগ-এ multiplication আর addition principle (039-এর শিকড়) — দুটোই খেলে। তাই factorial বুঝলে derangement তার শর্তযুক্ত ভাই।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **recurrence**:
```text
D(n) = (n − 1) × (D(n−1) + D(n−2)), D(1) = 0, D(2) = 1
```
(সুবিধার জন্য `D(0) = 1` ধরা হয়।) আরেকটা চেহারা inclusion-exclusion থেকে:
```text
D(n) = n! × (1 − 1/1! + 1/2! − 1/3! + ... + (−1)ⁿ/n!)
```
আর মজার approximation: `D(n) ≈ n!/e` — মানে এলোমেলো সাজালে "কেউ নিজেরটা পায়নি" হওয়ার সম্ভাবনা প্রায় `1/e ≈ 0.368`, **n যত বড়ই হোক**!
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি (আর গল্প-যাচাই) — **সব permutation বানিয়ে যেগুলোতে কেউ নিজের জায়গায় নেই, সেগুলো গোনা।** Python-এর `itertools.permutations`:
```python
from itertools import permutations
def derangement_brute(n):
count = 0
for perm in permutations(range(n)):
# perm[i] = জায়গা i-তে কোন জিনিস; নিজের জায়গায় থাকা মানে perm[i] == i
if all(perm[i] != i for i in range(n)):
count += 1
return count
```
প্রতিটা permutation ঘুরে চেক করি কোনো position-এ `perm[i] == i` (নিজের জায়গা) আছে কিনা; না থাকলে গোনা। ছোট n-এ একদম ঠিক — derangement সংখ্যা চোখে যাচাইয়ের নিখুঁত উপায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা — মোট permutation `n!`, সব ঘুরতে হয়:
```text
n = 10 হলে: 10! ≈ 36 লক্ষ permutation -> চলে কিন্তু ভারী
n = 13 হলে: 13! ≈ 6×10^9 -> অসম্ভব ধীর
n = 20 হলে: 20! ≈ 2.4×10^18 -> মহাজাগতিক
recurrence/formula: O(n) -> এক pass-এ!
```
derangement মোট permutation-এর ~37%, তবু সব `n!` ঘুরে বাছা বিরাট অপচয় — recurrence এক pass-এ উত্তর দেয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
দুটো ভালো পথ:
**পথ 1 — recurrence DP (গল্প জমানো):**
```python
def derangement(n):
if n == 0:
return 1
if n == 1:
return 0
d_prev2, d_prev1 = 1, 0 # D(0), D(1)
for k in range(2, n + 1):
d_cur = (k - 1) * (d_prev1 + d_prev2)
d_prev2, d_prev1 = d_prev1, d_cur
return d_prev1
```
দুটো আগের মান রেখে এগোই (Fibonacci-র মতো) — O(n) সময়, O(1) মতো জায়গা।
**পথ 2 — inclusion-exclusion / round formula:** `D(n) = round(n!/e)` (n ≥ 1-এ ঠিক):
```python
import math
def derangement_round(n):
if n == 0:
return 1
return round(math.factorial(n) / math.e)
```
recurrence integer-নিরাপদ আর সবচেয়ে নির্ভরযোগ্য; round-formula দ্রুত intuition দেয়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **"কেউই নিজের জায়গায় না" — এই শর্ত সরাসরি গোনা কঠিন, তাই একটা প্রাকৃতিক ভাগ-বিন্দু বেছে নাও (ব্যক্তি 1 কার টুপি পেল), আর সেই choice-এর ভেতরে দুটো ছোট derangement-এ নামাও।**
মূল চালাকি: ব্যক্তি 1-এর `n−1` রকম choice; প্রতিটার পর "যাকে দিল, সে আবার 1-এর টুপি নেবে কিনা" — এই দুই case ছোট derangement (D(n−1), D(n−2)) তৈরি করে। এই "এক element-এর সিদ্ধান্ত fix করে বাকিটা ছোট একই সমস্যায় ভাঙা" চিন্তাটা recurrence-ভিত্তিক counting-এর প্রাণ (Catalan-এও দেখেছ)। বিকল্পে: মোট permutation থেকে "অন্তত একজন নিজেরটা পেল" বাদ = inclusion-exclusion।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো n=3-এর সব permutation আর কোনগুলো derangement:
```text
টুপি বিলি (জায়গা 1,2,3 -> কে পেল):
123 -> সবাই নিজেরটা (derangement নয়)
132 -> 1 নিজেরটা পেল (নয়)
213 -> 3 নিজেরটা পেল (নয়)
231 -> কেউ নিজেরটা পায়নি ✓ derangement
312 -> কেউ নিজেরটা পায়নি ✓ derangement
321 -> 2 নিজেরটা পেল (নয়)
মোট 3! = 6, এর মধ্যে D(3) = 2
```
এবার recurrence-এর গল্প (ব্যক্তি 1 কার টুপি পেল):
```text
ব্যক্তি 1 পেল j-এর টুপি (j ≠ 1, তাই n−1 choice)। এবার j-এর দিকে তাকাও:
case A: j পেল 1-এর টুপি -> দুজনে অদলবদল সারা
-> বাকি n−2 জনের derangement = D(n−2)
case B: j পেল 1-এর টুপি পেল না -> j-এর কাছে "1-এর টুপি নিষেধ"
-> কার্যত n−1 জনের derangement = D(n−1)
D(n) = (n−1) × (D(n−1) + D(n−2))
```
লক্ষ করো — j-এর `n−1` choice দুই case-কেই গুণ করছে, ভেতরে দুই উপ-derangement-এর যোগ।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `derangement(4)` চালাই (`D(0)=1, D(1)=0` থেকে):
| k | (k−1) × (D(k−1) + D(k−2)) | D(k) |
| --- | --- | --- |
| শুরু | D(0)=1, D(1)=0 | — |
| 2 | 1 × (0 + 1) = 1 | 1 |
| 3 | 2 × (1 + 0) = 2 | 2 |
| 4 | 3 × (2 + 1) = 9 | 9 |
`D(4) = 9` ✓।
হাতে যাচাই (D(3)=2): permutation 231, 312 — দুটোতেই কেউ নিজেরটা পায়নি, ঠিক 2 ✓। recurrence, brute, formula — তিনটাই মেলে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
import math
def derangement(n):
"""!n: কেউই নিজের জায়গায় না, এমন বিন্যাস। D(n) = (n−1)(D(n−1)+D(n−2))।"""
if n == 0:
return 1
if n == 1:
return 0
d_prev2, d_prev1 = 1, 0 # D(0), D(1)
for k in range(2, n + 1):
d_cur = (k - 1) * (d_prev1 + d_prev2)
d_prev2, d_prev1 = d_prev1, d_cur
return d_prev1
def derangement_round(n):
"""একই সংখ্যা: round(n!/e) (n ≥ 1-এ ঠিক, n=0 আলাদা)।"""
if n == 0:
return 1
return round(math.factorial(n) / math.e)
# --- brute force verifier (সব permutation বানিয়ে fixed-point-হীন গোনা) ---
from itertools import permutations
def derangement_brute(n):
count = 0
for perm in permutations(range(n)):
if all(perm[i] != i for i in range(n)):
count += 1
return count
# --- ছোট test গুলো (সব pass করা উচিত) ---
# জানা মান
known = [1, 0, 1, 2, 9, 44, 265, 1854, 14833]
for n, val in enumerate(known):
assert derangement(n) == val
# recurrence == brute force (ছোট n, 0..8)
for n in range(0, 9):
assert derangement(n) == derangement_brute(n)
# recurrence == round(n!/e) (1..15 জুড়ে)
for n in range(1, 16):
assert derangement(n) == derangement_round(n)
# inclusion-exclusion রূপও মেলে: D(n) = Σ (-1)^k n!/k!
def derangement_incl_excl(n):
return sum(((-1) ** k) * math.factorial(n) // math.factorial(k) for k in range(n + 1))
for n in range(0, 12):
assert derangement(n) == derangement_incl_excl(n)
print(derangement(3)) # 2
print(derangement(4)) # 9
print(derangement(5)) # 44
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def derangement(n):
if n == 0: return 1
if n == 1: return 0
```
base case — খালি বিলি 1 ভাবে; একজন থাকলে নিজেরটা পেতে বাধ্য, তাই 0 derangement।
```text
d_prev2, d_prev1 = 1, 0
for k in range(2, n + 1):
d_cur = (k - 1) * (d_prev1 + d_prev2)
d_prev2, d_prev1 = d_prev1, d_cur
```
recurrence — দুটো আগের মান (D(k−2), D(k−1)) রেখে `(k−1)(D(k−1)+D(k−2))` দিয়ে পরেরটা; তারপর জানালা এক ধাপ সরাই (Fibonacci-style)।
```text
def derangement_brute(n):
for perm in permutations(range(n)):
if all(perm[i] != i for i in range(n)): count += 1
```
verify-র brute — সব permutation ঘুরে যেগুলোতে কোনো `perm[i] == i` (নিজের জায়গা) নেই, সেগুলো গোনে।
বাকি `assert` লাইনগুলো জানা মান, brute force, round(n!/e) আর inclusion-exclusion রূপ — চার দিক থেকে যাচাই করছে। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
2
9
44
সব test pass!
```
প্রথম: `derangement(3)` = 2 (231, 312)। দ্বিতীয়: `derangement(4)` = 9। তৃতীয়: `derangement(5)` = 44। আগের সব `assert` (জানা মান, recurrence = brute = round(n!/e) = inclusion-exclusion — চার দিক cross-check) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
recurrence `derangement(n)` **O(n)** — একটা loop, n−1 ধাপ। round-formula **O(n)** (factorial হিসাব)। brute **O(n · n!)** — সব permutation ঘুরে চেক। recurrence-ই সবচেয়ে নিরাপদ ও দ্রুত (বিশাল n-এও integer-নির্ভুল)।
### অতিরিক্ত জায়গা {#16-space-complexity}
recurrence **O(1)** — শুধু দুটো আগের মান রাখি (উত্তর সংখ্যাটার নিজের জায়গা বাদে)। brute **O(n)** — একটা permutation ধরতে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **D(1) ভুল ভাবা** — একজন থাকলে নিজেরটা পেতে বাধ্য, তাই `D(1) = 0`, 1 নয়।
2. **"কেউই না" আর "অন্তত একজন না" গুলিয়ে ফেলা** — derangement = **কেউই** নিজেরটা পায় না; "অন্তত একজন পায় না" = `n! − 1` সম্পূর্ণ ভিন্ন।
3. **recurrence-এ (n−1) গুণ ভুলে যাওয়া** — `D(n) = (n−1)(D(n−1)+D(n−2))`; (n−1) বাদ দিলে ভুল ধারা।
4. **round-formula n=0-এ ব্যবহার** — `round(0!/e) = round(0.368) = 0`, কিন্তু `D(0) = 1`; n=0 আলাদা করে ধরো।
5. **brute বড় n-এ চালানো** — n! বিস্ফোরণ; recurrence নাও।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Inclusion-Exclusion** (