Level 3 — Counting & Combinatorics (কত উপায়ে?)¶
আগের level গুলোতে প্রশ্ন ছিল "উত্তরটা কত?" — এই level-এ প্রশ্ন বদলে যায়: "কত উপায়ে?" জামা-প্যান্ট মেলানো থেকে grid-এ path গোনা পর্যন্ত — গোনাগুনতির এই শিল্পটাই combinatorics, আর DSA-র অর্ধেক counting problem-এর প্রাণ।
এই level এ কী শিখবে?¶
Combinatorics-এর মজা হলো — হাতে গুনলে যেখানে ঘণ্টা লাগত, সঠিক ছবিটা দেখতে পেলে সেখানে এক লাইনের formula। এই level-এ শিখব সেই ছবিগুলো দেখতে।
মূল idea গুলো:
- Multiplication principle — ধাপে ধাপে choice হলে গুণ (জামা × প্যান্ট)
- Factorial — n জনকে লাইনে দাঁড় করানোর উপায়, n!
- Permutation vs combination — order matters কি না, এই এক প্রশ্নেই দুই জগৎ
- nCr আর Pascal triangle — formula আর DP-style build, দুই পথেই
- Stars and bars — একই রকম জিনিস ভাগ করার কৌশল (bar বসানোর ছবি)
- Inclusion-exclusion — overcounting-এর যোগ-বিয়োগ correction (Venn)
- Grid path counting — R/D letter সাজানো = C(m+n, n)
- Catalan number — balanced bracket আর তার আত্মীয়রা (intro)
- Derangement — কেউ নিজের জিনিস ফেরত পাবে না (টুপি অদলবদল)
- Pigeonhole principle — n+1 পায়রা, n খোপ → কোথাও দুজন
- Birthday paradox — collision কত তাড়াতাড়ি ঘটে, তার অনুভব
কেন এই level দরকার?¶
Competitive programming (CP) এ: "Count the number of ways..." — Codeforces আর CSES-এ এই বাক্যটা দেখলেই বোঝো combinatorics ডাকছে। বড় উত্তর mod 10⁹+7-এ চাইবে — তখন Level 2-এর nCr mod p pipeline-টাই অস্ত্র। Pigeonhole দিয়ে existence proof, inclusion-exclusion দিয়ে "at least one" গোনা — Div 2-এর নিয়মিত খেলা।
Interview এ: Unique Paths, Pascal's Triangle, Subsets — সবই common interview pattern। Interviewer প্রায়ই recursive counting থেকে formula-তে নামতে দেখতে চায় — "এটা তো আসলে C(m+n, n)" বলতে পারাটাই পার্থক্য গড়ে। Birthday paradox hashing-এর collision আলোচনায় ফিরে আসে — system design-এও।
পরের level গুলোতে: Counting DP (কতভাবে coin বানানো যায়, কতগুলো path) — পুরোটাই আজকের multiplication principle আর nCr-এর সম্প্রসারণ। Catalan number পরে BST counting, bracket DP-তে পুরো চরিত্রে ফিরবে। Probability-র ভিতও এই গোনাগুনতি।
Prerequisites¶
- Level 0, Level 1 — loop, factor, GCD
- Level 2 — বিশেষ করে nCr mod p pipeline (problem 034); বড় nCr-এর হিসাবে ওটাই লাগবে
- কাগজ-কলম! এই level-এ গাছ (tree) আর ছবি আঁকা code লেখার চেয়ে বেশি জরুরি
Learning goals (checklist)¶
এই level শেষে নিজেকে জিজ্ঞেস করো:
- [ ] Multiplication principle কখন খাটে (ধাপগুলো independent) আর কখন না — উদাহরণসহ বলতে পারি
- [ ] n! মানে কী, আর 0! = 1 কেন — যুক্তি দিতে পারি
- [ ] nPr আর nCr-এর পার্থক্য এক লাইনে বলতে পারি ("order matters?"), আর nCr = nPr / r! কেন — জানি
- [ ] Pascal triangle-এর নিয়ম
C(n,r) = C(n−1,r−1) + C(n−1,r)build করতে পারি, আর গল্পটা ("শেষ জনকে নেব কি নেব না") বলতে পারি - [ ] Stars and bars-এর ছবি এঁকে "n টা একই চকলেট k জনে" formula C(n+k−1, k−1) নামাতে পারি
- [ ] Inclusion-exclusion-এর Venn ছবি দিয়ে |A∪B| আর |A∪B∪C| লিখতে পারি
- [ ] Grid path = letter সাজানো — এই অনুবাদটা করতে পারি, C(m+n, n) সহ
- [ ] Catalan-এর প্রথম কয়েকটা মান (1, 1, 2, 5, 14) আর কোথায় কোথায় ওঠে — চিনি
- [ ] Derangement-এর recurrence
D(n) = (n−1)(D(n−1) + D(n−2))এর গল্পটা বলতে পারি - [ ] Pigeonhole দিয়ে অন্তত একটা "অবশ্যই ঘটবে" যুক্তি দাঁড় করাতে পারি
- [ ] Birthday paradox-এর মূল চমক (23 জনেই 50%) আর কেন — C(n,2) জোড়ার হিসাবে বুঝি
Problem list¶
মোট 14টা problem — 5টা Easy, 9টা Medium। Easy গুলো formula-র হাতেখড়ি, Medium গুলোতে ছবি-আঁকা চিন্তার আসল practice।
Easy¶
| # | Problem | Pattern | Source |
|---|---|---|---|
| 039 | Factorial | n! | Classic exercise |
| 040 | Permutation Basic | nPr | Classic exercise |
| 041 | Combination Basic | nCr | Classic exercise |
| 045 | Count Pairs | C(n,2) | LeetCode Number of Good Pairs — https://leetcode.com/problems/number-of-good-pairs/ |
| 047 | Count Subsets | 2^n choices | Concept link: LeetCode Subsets — https://leetcode.com/problems/subsets/ |
Medium¶
| # | Problem | Pattern | Source |
|---|---|---|---|
| 042 | nCr using Pascal Triangle | DP-style build | LeetCode Pascal's Triangle — https://leetcode.com/problems/pascals-triangle/ |
| 043 | Stars and Bars Basic | identical items split | Classic combinatorics (book: Levin, Discrete Mathematics — https://discrete.openmathbooks.org/) |
| 044 | Inclusion-Exclusion Basic | overcount correction | CP-Algorithms — https://cp-algorithms.com/combinatorics/inclusion-exclusion.html |
| 046 | Count Triplets | C(n,3) / grouping | Classic exercise |
| 048 | Count Paths in Grid | C(m+n, n) | LeetCode Unique Paths — https://leetcode.com/problems/unique-paths/ |
| 049 | Catalan Number Intro | balanced structures | Related: LeetCode Unique Binary Search Trees — https://leetcode.com/problems/unique-binary-search-trees/ |
| 050 | Derangement Intro | !n recurrence | Classic combinatorics |
| 051 | Pigeonhole Principle Problems | existence argument | Classic combinatorics |
| 052 | Birthday Paradox Style Problems | collision probability | Classic probability |
পুরো tracker table (status সহ) আছে problems/README.md-তে।
Recommended order¶
- 039 → 040 → 041 — factorial → permutation → combination; "order matters?" প্রশ্নটা এখানেই গাঁথো
- 042 — Pascal triangle build; nCr-কে DP-র চোখে প্রথম দেখা
- 045 → 046 → 047 — C(n,2), C(n,3), 2^n — ছোট ছোট গোনার অস্ত্র
- 043 — stars and bars; bar বসানোর ছবিটা ধৈর্য নিয়ে আঁকো
- 044 — inclusion-exclusion; Venn-এর যোগ-বিয়োগ
- 048 — grid path; এতদিনের nCr এখানে জীবন্ত হয়
- 049 → 050 — Catalan আর derangement; দুটোই intro — গল্পটা বোঝাই লক্ষ্য
- 051 → 052 — pigeonhole আর birthday paradox; formula কম, যুক্তি বেশি — মাথা খেলানোর problem
Common mistakes (সাধারণ ভুল)¶
- Order matters কি না না ভেবে formula বসানো — "5 জন থেকে 3 জনের committee" = C(5,3) = 10, কিন্তু "president-VP-secretary" = P(5,3) = 60। আগে প্রশ্ন করো: দল বদলে নাম বদলালে কি নতুন গোনা হবে?
- nCr হিসাবে আগে দুটো factorial পুরো কেটে ভাগ —
factorial(n) // (factorial(r) * factorial(n-r))Python-এ চলে কিন্তু বড় n-এ slow; আর mod-জগতে সরাসরি ভাগ তো নিষেধই (Level 2!)। হয় Pascal build, নয় fact + inv_fact pipeline। - Multiplication আর addition principle গুলিয়ে ফেলা — ধাপগুলো "এবং" (পরপর ঘটে) হলে গুণ, "অথবা" (যেকোনো একটা) হলে যোগ। "জামা এবং প্যান্ট" = 3×4; "পিৎজা অথবা বার্গার" = 3+4।
- Stars and bars-এ "অন্তত 1 করে" আর "0 হতে পারে" গুলিয়ে ফেলা — 0 চললে C(n+k−1, k−1); প্রত্যেকে অন্তত 1 পেলে আগে k টা বিলিয়ে দাও, তারপর C(n−1, k−1)।
- Inclusion-exclusion-এ মাঝের অংশ একবারের জায়গায় দুবার রেখে দেওয়া — |A∪B| = |A| + |B| − |A∩B| — বিয়োগটাই পুরো পদ্ধতির প্রাণ; 3 set-এ আবার তিন-জোড়া বিয়োগ, তারপর মাঝেরটা ফেরত যোগ।
- Grid path-এ ধাপ গোনায় off-by-one — m×n ঘরের grid-এ ডান-ধাপ n−1 টা, নিচ-ধাপ m−1 টা → C(m+n−2, m−1)। "ঘর" নাকি "ধাপ" — আগে ঠিক করো।
- Derangement-এ "সবাই ভুল" আর "অন্তত একজন ভুল" গুলিয়ে ফেলা — derangement মানে কেউই নিজেরটা পায় না; "অন্তত একজন পায় না" = n! − 1 ভিন্ন জিনিস।
- Pigeonhole-কে গড়পড়তা ভাবা — pigeonhole বলে "কোনো এক খোপে অন্তত ⌈n/k⌉" — এটা গ্যারান্টি, average না। "কোন খোপে" তা বলে না — শুধু অস্তিত্ব।
- বড় উত্তরে mod ভুলে যাওয়া — C(10⁶, 5×10⁵) মহাজাগতিক সংখ্যা; problem mod চাইলে Level 2-এর pipeline, প্রতি গুণে
% MOD।
পরের level এ যাওয়ার আগে checklist¶
- [ ] 14টা problem-এর অন্তত 11টা নিজে solve করেছি
- [ ] Pascal triangle-এর প্রথম 6টা সারি হাতে এঁকেছি আর তাতে C(5,2) = 10 খুঁজে পেয়েছি
- [ ] Stars and bars-এর ★|★★|★ ছবি দিয়ে একটা ছোট case (4 চকলেট, 3 জন) হাতে গুনে formula-র সাথে মিলিয়েছি
- [ ] 2×3 grid-এর সব path হাতে এঁকে (3টা হওয়ার কথা: RRD, RDR, DRR) C(3,1)-এর সাথে মিলিয়েছি
- [ ] "Order matters?" — যেকোনো counting প্রশ্নে এটা প্রথম প্রশ্ন হিসেবে করা অভ্যাস হয়ে গেছে
- [ ] nCr mod p দরকার হলে Level 2-এর কোন problem-এ (034) pipeline আছে — মনে আছে
- [ ] অন্তত একটা problem-এ brute force (সব সাজিয়ে গোনা) দিয়ে formula verify করেছি
সব টিক দিতে পারলে — এই module-এর গাণিতিক ভিত শেষ! সামনে Level 4: Bit Manipulation — যেখানে আজকের 2^n subsets-এর গল্পটাই bit-এর ভাষায় নতুন রূপ নেবে।
Source map¶
এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে source-map.md-তে।