050 — Derangement Intro¶

এবার একটা মজার আর সামান্য উল্টো-চিন্তার সমস্যা: n জন পার্টি শেষে টুপি নিচ্ছে, কিন্তু কেউই নিজের টুপি পাবে না — কত ভাবে? এটাই derangement, লেখা !n (বা D(n))। সাধারণ permutation-এ "যেমন খুশি সাজাও", এখানে কঠোর শর্ত — প্রতিটা জিনিস নিজের জায়গা ছাড়া অন্য কোথাও। recurrence-এর গল্পটা একটু চিন্তা চায়, কিন্তু একবার ধরলে চমৎকার লাগবে। এটাও intro — সংখ্যা চেনা আর গল্প বোঝা মূল লক্ষ্য।

Source¶

Original source: Classic combinatorics (derangement)
Platform: Classic combinatorics — https://discrete.openmathbooks.org/
Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
Difficulty: Medium
Pattern: !n recurrence (derangement)
Basic idea inherited from: 039 — Factorial (permutation-এর শর্তযুক্ত রূপ)

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, ...।

2. What is the math idea?¶

মূল idea — recurrence:

D(n) = (n − 1) × (D(n−1) + D(n−2)),    D(1) = 0, D(2) = 1

(সুবিধার জন্য D(0) = 1 ধরা হয়।) আরেকটা চেহারা inclusion-exclusion থেকে:

D(n) = n! × (1 − 1/1! + 1/2! − 1/3! + ... + (−1)ⁿ/n!)

আর মজার approximation: D(n) ≈ n!/e — মানে এলোমেলো সাজালে "কেউ নিজেরটা পায়নি" হওয়ার সম্ভাবনা প্রায় 1/e ≈ 0.368, n যত বড়ই হোক!

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 তার শর্তযুক্ত ভাই।

4. Real-life analogy¶

ভাবো অফিসে "Secret Santa" — n জন কর্মী, প্রত্যেকে একটা করে নাম তুলবে কাকে উপহার দেবে। নিয়ম: কেউ নিজের নাম তুলতে পারবে না (নিজেকে উপহার দেওয়া অর্থহীন)।

সব নাম এমনভাবে বিলি করার কয়টা উপায় আছে যেখানে কেউই নিজের নাম পায়নি? — ঠিক D(n)!

মজার বাস্তবতা: n বড় হলেও, পুরোপুরি এলোমেলো করে বিলি করলে "কাকতালীয়ভাবে কেউ একজন নিজের নাম পেয়ে গেছে" হওয়ার সম্ভাবনা প্রায় 63% (= 1 − 1/e)। মানে valid Secret Santa পেতে প্রায়ই কয়েকবার চেষ্টা লাগে — derangement মোট permutation-এর মোটে ~37%।

5. Visual explanation¶

প্রথমে দেখো n=3-এর সব permutation আর কোনগুলো derangement:

টুপি বিলি (জায়গা 1,2,3 -> কে পেল):

123  -> সবাই নিজেরটা        (derangement নয়)
132  -> 1 নিজেরটা পেল       (নয়)
213  -> 3 নিজেরটা পেল       (নয়)
231  -> কেউ নিজেরটা পায়নি  ✓ derangement
312  -> কেউ নিজেরটা পায়নি  ✓ derangement
321  -> 2 নিজেরটা পেল       (নয়)

মোট 3! = 6, এর মধ্যে D(3) = 2

এবার recurrence-এর গল্প (ব্যক্তি 1 কার টুপি পেল):

ব্যক্তি 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-এর যোগ।

6. Example input and output¶

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 হারে বাড়ে।

7. Brute force thinking¶

সবচেয়ে সরাসরি (আর গল্প-যাচাই) — সব permutation বানিয়ে যেগুলোতে কেউ নিজের জায়গায় নেই, সেগুলো গোনা। Python-এর itertools.permutations:

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!, সব ঘুরতে হয়:

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 (গল্প জমানো):

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-এ ঠিক):

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।

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 — তিনটাই মেলে।

12. Python solution¶

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¶

def derangement(n):
    if n == 0: return 1
    if n == 1: return 0

base case — খালি বিলি 1 ভাবে; একজন থাকলে নিজেরটা পেতে বাধ্য, তাই 0 derangement।

    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)।

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!।

14. Output walkthrough¶

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

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!।

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¶

D(1) ভুল ভাবা — একজন থাকলে নিজেরটা পেতে বাধ্য, তাই D(1) = 0, 1 নয়।
"কেউই না" আর "অন্তত একজন না" গুলিয়ে ফেলা — derangement = কেউই নিজেরটা পায় না; "অন্তত একজন পায় না" = n! − 1 সম্পূর্ণ ভিন্ন।
recurrence-এ (n−1) গুণ ভুলে যাওয়া — D(n) = (n−1)(D(n−1)+D(n−2)); (n−1) বাদ দিলে ভুল ধারা।
round-formula n=0-এ ব্যবহার — round(0!/e) = round(0.368) = 0, কিন্তু D(0) = 1; n=0 আলাদা করে ধরো।
brute বড় n-এ চালানো — n! বিস্ফোরণ; recurrence নাও।

18. Harder problems that inherit this idea¶

CP-Algorithms — Inclusion-Exclusion (https://cp-algorithms.com/combinatorics/inclusion-exclusion.html) — derangement-এর inclusion-exclusion derivation আর আত্মীয় গণনা।
044 — Inclusion-Exclusion Basic (এই repo) — derangement-এর বিকল্প রূপের ভিত্তি।
"Partial derangement" / "exactly k fixed points" সমস্যা — C(n,k) × D(n−k) — derangement-কে combination-এর সাথে মেলানো।

19. Pattern learned¶

Derangement (!n) via recurrence — D(n) = (n−1)(D(n−1)+D(n−2)), D(0)=1, D(1)=0; বা inclusion-exclusion; D(n) ≈ n!/e। মূল signal: "কেউই/কোনোটাই নিজের জায়গায় না / সবাই ভুল ফেরত পেল" দেখলেই derangement (0,1,2,9,44,...)।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "derangement = কেউই নিজেরটা পায় না; D(n)=(n−1)(D(n−1)+D(n−2)), D(0)=1,D(1)=0; ≈ n!/e (~37%)। 'কেউই নিজের জায়গায় না' দেখলেই এটা, 'অন্তত একজন না'-র সাথে গুলিও না।"

পরের ধাপ → 051 — Pigeonhole Principle Problems (গোনা ছাড়াই "অবশ্যই ঘটবে" প্রমাণ)।

ফিরে দেখা: আগের ধাপ → 039 — Factorial · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

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