Concept Notes — Counting & Combinatorics¶
এই level-এর সবচেয়ে বড় কথা: formula মুখস্থ কোরো না, ছবি দেখো। প্রতিটা formula-র পেছনে একটা গল্প আছে — জামা-প্যান্ট, চকলেট-bar, টুপি অদলবদল। গল্পটা ধরতে পারলে formula নিজেই বেরিয়ে আসে। আর প্রতিটা formula ছোট case-এ হাতে গুনে verify করো — সেটাই dry run।
1. Multiplication principle — জামা × প্যান্ট¶
তোমার 3টা জামা, 4টা প্যান্ট। কত রকম সাজ?
জামা-1 জামা-2 জামা-3
/ | \ \ / | \ \ / | \ \
প1 প2 প3 প4 প1 প2 প3 প4 প1 প2 প3 প4
প্রতিটা জামার নিচে 4টা শাখা -> মোট 3 × 4 = 12 টা পাতা
নিয়ম: কাজটা ধাপে ধাপে হয়, আর প্রতিটা ধাপের choice-সংখ্যা আগের choice-এর উপর নির্ভর করে না — তাহলে মোট উপায় = ধাপগুলোর গুণফল। আর choice গুলো "অথবা" হলে (পিৎজা অথবা বার্গার) — যোগ।
Mini dry run: 3 জামা × 4 প্যান্ট = 12 সাজ; প্রতিটার সাথে 2 জুতা → 12 × 2 = 24। গাছটা মনে মনে আঁকো — 3 শাখা, প্রতিটায় 4, প্রতিটায় 2।
এই এক নিয়মই Level 1-এ লুকিয়ে ছিল: divisor count = (e1+1)(e2+1)... — প্রতিটা prime-এর power বাছাই এক একটা ধাপ! পুরো combinatorics আসলে এই গুণের নিয়মেরই নানা ছদ্মবেশ।
2. Factorial — লাইনে দাঁড় করানো¶
n জনকে এক লাইনে কত ভাবে দাঁড় করানো যায়? প্রথম জায়গায় n জনের যে কেউ, দ্বিতীয়তে বাকি n−1, তৃতীয়তে n−2... — multiplication principle:
n! = n × (n−1) × (n−2) × ... × 2 × 1
3 জন (A, B, C) -> 3! = 6 লাইন:
ABC ACB BAC BCA CAB CBA <- হাতে গুনে মিলিয়ে নাও!
Mini dry run (n = 5): 1 → 2 → 6 → 24 → 120। লক্ষ করো কী ভয়ংকর দ্রুত বাড়ে: 10! = 36,28,800; 20! ≈ 2.4×10¹⁸ (64-bit-এর কিনারা!); 100!-এ 158 digit। এজন্যই বড় counting-এ mod লাগে — Level 2-এর গল্প।
আর 0! = 1 কেন? শূন্য জনকে লাইনে দাঁড় করানোর ঠিক একটাই উপায় — কিছুই না করা। (formula-র দিক থেকেও: nCn = n!/(n!·0!) = 1 হতে হলে 0! = 1 চাই।)
3. Permutation vs combination — order matters?¶
পুরো combinatorics-এর সবচেয়ে জরুরি প্রশ্ন: সাজানোর ক্রম কি আলাদা গোনা হবে?
- Permutation (nPr): 5 জন থেকে president, VP, secretary — পদ আলাদা, তাই (A,B,C) আর (B,A,C) ভিন্ন।
P(5,3) = 5×4×3 = 60। - Combination (nCr): 5 জন থেকে 3 জনের committee — দল একটাই, ক্রম অর্থহীন। {A,B,C} যেভাবেই লেখো, এক।
দুটোর সম্পর্কটাই আসল ছবি: প্রতিটা 3-জনের দলকে ভেতরে ভেতরে 3! = 6 ভাবে সাজানো যায় — মানে permutation-এ প্রতিটা দল 6 বার গোনা হয়েছে!
P(5,3) = 60 টা সাজানো সারি
প্রতি 6টা সারি = একই দল -> C(5,3) = 60 / 6 = 10
সূত্রে: P(n,r) = n! / (n−r)! C(n,r) = P(n,r) / r! = n! / (r!(n−r)!)
def nPr(n, r):
result = 1
for i in range(n, n - r, -1): # n, n-1, ..., n-r+1
result *= i
return result
def nCr(n, r):
return nPr(n, r) // factorial(r)
Mini dry run (n=5, r=2): nPr = 5×4 = 20। nCr = 20 // 2 = 10। হাতে check: {1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5} — ঠিক 10 ✓।
মনে রাখার মন্ত্র: "P-তে পদ, C-তে দল।" পদ (position) আলাদা হলে P, শুধু দল (group) হলে C।
4. Pascal triangle — nCr-এর DP-চেহারা¶
nCr-এর আরেকটা জাদুকরি নিয়ম: C(n, r) = C(n−1, r−1) + C(n−1, r)।
গল্পটা: n জন থেকে r জন বাছছ; শেষ জন (ধরো রিমা) এর দিকে তাকাও — হয় রিমা দলে আছে (বাকি n−1 থেকে r−1 জন বাছো), নয় নেই (বাকি n−1 থেকে পুরো r জন)। দুটো ক্ষেত্র আলাদা ("অথবা") — তাই যোগ। এই নিয়ম সাজালেই Pascal triangle:
row 0: 1
row 1: 1 1
row 2: 1 2 1
row 3: 1 3 3 1
row 4: 1 4 6 4 1
row 5: 1 5 10 10 5 1
^
প্রতিটা ঘর = মাথার উপরের দুই ঘরের যোগ (10 = 4 + 6)
row n-এর r-তম ঘর = C(n, r) -> C(5,2) = 10 ✓
def pascal(n):
row = [1]
triangle = [row]
for _ in range(n):
row = [1] + [row[i] + row[i + 1] for i in range(len(row) - 1)] + [1]
triangle.append(row)
return triangle
Mini dry run: [1] → [1,1] → [1, 1+1, 1] = [1,2,1] → [1, 1+2, 2+1, 1] = [1,3,3,1] → [1,4,6,4,1]। প্রতিটা নতুন row আগেরটার পাশাপাশি জোড়ার যোগ।
এটা আসলে তোমার প্রথম dynamic programming: বড় উত্তর (C(n,r)) ছোট উত্তরদের (C(n−1,·)) থেকে বানানো, আর টেবিলে জমিয়ে রাখা। factorial overflow/mod-এর ঝামেলা ছাড়াই ছোট n-এ nCr — Pascal-ই সবচেয়ে নিরাপদ পথ। (বড় n + mod হলে → Level 2-এর fact/inv_fact pipeline।) বোনাস লক্ষ: প্রতি row-এর যোগফল 1, 2, 4, 8, 16 — মানে ΣC(n,r) = 2ⁿ — section 7-এ এর মানে খুলবে।
5. Stars and bars — একই চকলেট ভাগের ছবি¶
7টা একই রকম চকলেট 3 বন্ধুকে দেবে (কেউ 0-ও পেতে পারে) — কত ভাবে? চকলেট আলাদা করে চেনা যায় না, তাই multiplication principle সরাসরি খাটে না। কৌশল: চকলেটগুলো star হিসেবে সারিতে রাখো, আর 2টা bar বসিয়ে 3 ভাগ করো —
★ ★ | ★ ★ ★ ★ | ★ -> বন্ধু A: 2, B: 4, C: 1
| ★ ★ ★ ★ ★ ★ ★ | -> A: 0, B: 7, C: 0
★ ★ ★ ★ ★ ★ ★ | | -> A: 7, B: 0, C: 0
প্রতিটা ভাগ-ব্যবস্থা = star আর bar-এর একটা সাজানো সারি! মোট জিনিস 7+2 = 9টা জায়গা, তার মধ্যে bar-এর জন্য 2টা বাছো —
Mini dry run (ছোট case — 3 চকলেট, 2 জন): formula C(4,1) = 4। হাতে: (0,3), (1,2), (2,1), (3,0) — ঠিক 4 ✓। "প্রত্যেকে অন্তত 1" চাইলে আগে সবাইকে 1টা করে দিয়ে দাও (n−k বাকি), তারপর একই খেলা: C(n−1, k−1)।
এই pattern interview-তে ছদ্মবেশে আসে: "x1 + x2 + x3 = 7-এর কয়টা non-negative integer solution?" — হুবহু একই প্রশ্ন, 36।
6. Inclusion-exclusion — যোগ-বিয়োগের correction¶
Class-এ 25 জন cricket খেলে, 18 জন football, 10 জন দুটোই। অন্তত একটা খেলে কয়জন? 25 + 18 = 43 বললে ভুল — দুটোই-খেলা 10 জন দুবার গোনা হয়ে গেছে! একবার ফেরত দাও:
|A ∪ B| = |A| + |B| − |A ∩ B| = 25 + 18 − 10 = 33
Venn: cricket (25) football (18)
+-----------+-----+-----------+
| | | | মাঝের 10 দুই বৃত্তেই —
| 15 | 10 | 8 | যোগে দুবার গোনা,
| | | | তাই একবার বিয়োগ
+-----------+-----+-----------+
15 + 10 + 8 = 33 ✓
3 set-এ ঢেউটা আরেক ধাপ গড়ায়: জোড়াগুলো বিয়োগ করতে গিয়ে একদম-মাঝ (তিনটাতেই আছে) তিনবার যোগ, তিনবার বিয়োগ — শূন্যবার গোনা! ফেরত যোগ:
Mini dry run (classic CP রূপ): 1 থেকে 100-এ কয়টা সংখ্যা 2 বা 3 দিয়ে ভাগ যায়? |A| = 100//2 = 50, |B| = 100//3 = 33, |A∩B| = 6-এর multiple = 100//6 = 16 → 50 + 33 − 16 = 67। (এখানেই Level 1-এর lcm উঁকি দিল — "2 এবং 3 দুটোই" মানে lcm(2,3) = 6 দিয়ে ভাগ।)
মন্ত্র: জোড় সংখ্যক set-এর intersection বিয়োগ, বিজোড় সংখ্যকেরটা যোগ — overcounting-এর ঢেউ পালা করে শুধরানো।
7. Count subsets, pairs, triplets — ছোট তিন অস্ত্র¶
Subsets = 2ⁿ: n জিনিসের set-এ প্রতিটা জিনিসের কাছে দুটো প্রশ্ন — "তুমি subset-এ আছ? হ্যাঁ/না।" n টা independent হ্যাঁ/না → multiplication principle → 2ⁿ।
Pairs = C(n,2) = n(n−1)/2: n জন পার্টিতে, সবাই সবার সাথে handshake — প্রথম জন বাছার n উপায়, দ্বিতীয় জনের n−1, কিন্তু (A,B) আর (B,A) একই handshake → 2 দিয়ে ভাগ। Triplets = C(n,3) — একই যুক্তি, 3! = 6 দিয়ে ভাগ।
Mini dry run (n = 4 pairs): 4×3//2 = 6 → {12,13,14,23,24,34} ✓। Interview-তে এর প্রিয় ছদ্মবেশ: "array-তে কয়টা equal pair?" — প্রতিটা value-র frequency f হলে উত্তর Σ C(f, 2) — গোনার আগে দল ভাগ করো, তারপর প্রতি দলে handshake।
8. Grid path — হাঁটা মানে letter সাজানো¶
(0,0) থেকে (n, m) — শুধু ডানে (R) বা নিচে (D) — কয়টা path? জাদু-অনুবাদ: প্রতিটা path = R আর D-এর একটা সারি! 2×2 ধাপের grid:
মোট ধাপ R-সংখ্যা + D-সংখ্যা; এর মধ্যে R-গুলো কোথায় বসবে বাছলেই path ঠিক হয়ে যায়:
Mini dry run (3 R, 1 D): C(4,1) = 4 → RRRD, RRDR, RDRR, DRRR ✓। Counting প্রশ্নকে "জিনিস সাজানো"-তে অনুবাদ করা — এটা combinatorics-এর core skill, আর এই problem-টাই (LeetCode Unique Paths ধাঁচ) পরে DP-র হাতেখড়ি হিসেবে ফিরবে: formula-পথ আর DP-পথ, দুটোই জানা চাই।
9. Catalan আর derangement — দুই বিখ্যাত চরিত্রের intro¶
Catalan number: n জোড়া bracket কত ভাবে balanced সাজানো যায়?
n=1: () -> 1
n=2: ()() (()) -> 2
n=3: ()()() (())() ()(()) (()()) ((())) -> 5
ধারা: 1, 1, 2, 5, 14, 42, ... সূত্র: Cat(n) = C(2n, n) / (n + 1)
Mini dry run (n=3): C(6,3)/4 = 20/4 = 5 ✓। মজার তথ্য: n node-এর BST-সংখ্যা, mountain range, polygon triangulation — সবই এই একই ধারা! এখন শুধু চরিত্রটা চেনো; গভীর গল্প পরে tree/DP-তে।
Derangement (!n): n জন পার্টি শেষে টুপি ফেরত নিচ্ছে — কেউই নিজেরটা পাবে না, কত ভাবে? Recurrence-এর গল্প: ব্যক্তি 1-এর মাথায় j-এর টুপি (n−1 choice); এবার j-এর দিকে তাকাও — হয় j পেল 1-এর টুপি (দুজনে অদলবদল সারা — বাকি n−2 জনের derangement), নয় পেল না (j এখন কার্যত "1-এর টুপি আমার নিষেধ" — n−1 জনের derangement)।
Mini dry run (D(3)): 2 × (D(2) + D(1)) = 2 × 1 = 2। হাতে check (টুপি 1,2,3): 231 আর 312 — ঠিক 2 ✓। আরেকটা মজা: !n ≈ n!/e — মানে সবাই এলোমেলো টুপি নিলে "কেউ নিজেরটা পেল না" হওয়ার সম্ভাবনা ~37%, n যত বড়ই হোক!
10. Pigeonhole আর birthday paradox — গোনা ছাড়াই সিদ্ধান্ত¶
Pigeonhole principle: n+1 পায়রা n খোপে ঢুকলে কোনো এক খোপে অন্তত 2টা — উপায় নেই। শুনতে তুচ্ছ, কিন্তু এ দিয়ে "অবশ্যই ঘটবে" প্রমাণ করা যায়, কোনটা ঘটবে না জেনেও:
- 13 জন মানুষ → অন্তত 2 জনের জন্মমাস এক (12 খোপ, 13 পায়রা)
- যেকোনো n+1 টা সংখ্যা থেকে 2টা পাওয়া যাবেই যাদের পার্থক্য n দিয়ে ভাগ যায় — কারণ remainder mod n-এর খোপ মোটে n টা! (Level 2-এর ঘড়ি এখানে খোপ হয়ে ফিরল।)
সাধারণ রূপ: n পায়রা, k খোপ → কোনো খোপে অন্তত ⌈n/k⌉। মনে রাখো: এটা অস্তিত্বের গ্যারান্টি — কোন খোপ, বলে না।
Birthday paradox: 365 দিনের বছরে মাত্র 23 জন থাকলেই কারো-না-কারো জন্মদিন মেলার সম্ভাবনা 50% ছাড়ায়! চমকের কারণ: তুলনা হয় জোড়ায় জোড়ায় — 23 জনে C(23, 2) = 253 জোড়া; প্রতিটা জোড়াই মিলে যাওয়ার এক একটা সুযোগ।
def prob_all_distinct(n, days=365):
p = 1.0
for i in range(n):
p *= (days - i) / days # i-তম জন আগের সবার থেকে আলাদা
return 1 - p # অন্তত এক মিল
# prob_all_distinct(23) ≈ 0.507
Mini dry run (n = 3): p = 1 × 365/365 × 364/365 × 363/365 ≈ 0.9918 → মিলের সম্ভাবনা ≈ 0.0082। n = 23 পর্যন্ত চালালে ≈ 0.507 — অর্ধেক পেরোল! এই "জোড়া C(n,2)-এর হারে collision বাড়ে" অনুভবটাই Level 2-এর hashing collision-এর ব্যাখ্যা: hash space M হলে মোটামুটি √M জিনিসেই collision-এর ভালো সম্ভাবনা।
এক নজরে (cheat sheet)¶
ধাপে ধাপে choice -> গুণ; "অথবা" -> যোগ
n! -> n জনের লাইন; 0! = 1
P(n,r) = n!/(n−r)! -> পদ আলাদা (order matters)
C(n,r) = P(n,r)/r! -> শুধু দল; C(n,r) = C(n−1,r−1)+C(n−1,r)
stars and bars -> n same items, k জন: C(n+k−1, k−1)
inclusion-exclusion -> যোগ − জোড়া + তিন-মাঝ − ...
subsets -> 2ⁿ (প্রতিটার হ্যাঁ/না)
pairs, triplets -> C(n,2), C(n,3)
grid path -> C(মোট ধাপ, R-ধাপ)
Catalan: 1,1,2,5,14 -> balanced bracket, BST, ...
derangement: 0,1,2,9,44 -> D(n) = (n−1)(D(n−1)+D(n−2))
pigeonhole -> n+1 পায়রা n খোপে -> কোথাও ≥ 2
birthday paradox -> C(n,2) জোড়া -> collision দ্রুত
বড় উত্তর + mod চাইলে -> Level 2-এর nCr mod p pipeline
পরের ধাপ: problems/-এর 14টা problem। প্রতিটাতে আগে ছোট case হাতে গুনে formula verify কোরো — combinatorics-এ এটাই debugging। এই level শেষ মানে module-এর math-ভিত complete — সামনে bit manipulation, যেখানে 2ⁿ subsets-এর প্রতিটা subset একটা binary সংখ্যা হয়ে ধরা দেবে।