# Problems — Level 3: Counting & Combinatorics

> এই folder-এ Level 3-এর 14টা problem-এর নোট আছে। প্রতিটার জন্য আলাদা `.md` file — প্রশ্নের নিজের-ভাষা অনুবাদ, ছবি, ছোট case-এ হাতে গোনা, formula, code, ভুলের হিসাব।

## কীভাবে problem গুলো use করবে?

প্রতিটা note লেখা হয় [../../../templates/math-problem-note-template.md](../../../templates/math-problem-note-template.md) follow করে — ২০টা section-এর template (নিজের ভাষায় problem → brute force → optimization → dry run → complexity → এক লাইনের শিক্ষা)। এই level-এ "brute force" section-এর মানে একটু আলাদা: **সবচেয়ে ছোট case-এ সব সাজানো হাতে লিখে গোনা** — সেটাই formula-র verifier। ছোট case না মিললে formula ভুল, যত সুন্দরই দেখাক।

নিয়ম:

1. [../README.md](../README.md)-এর recommended order ধরো — factorial থেকে শুরু, paradox দিয়ে শেষ
2. প্রতিটা problem-এ আগে ছবি আঁকো, পরে code
3. নিজে সমাধান করার অগ্রগতি আলাদা খাতায় বা tracker-এ রাখো। “নোট আছে” কেবল ব্যাখ্যার উপস্থিতি বোঝায়।

## Tracker table

| # | Problem | Difficulty | Pattern | Inherits from | Source | Note file | নোটের অবস্থা |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 039 | Factorial | Easy | n! | — | Classic exercise | [039-factorial.md](039-factorial.md) | নোট আছে |
| 040 | Permutation Basic | Easy | nPr | 039 | Classic exercise | [040-permutation-basic.md](040-permutation-basic.md) | নোট আছে |
| 041 | Combination Basic | Easy | nCr | 040 | Classic exercise | [041-combination-basic.md](041-combination-basic.md) | নোট আছে |
| 042 | nCr using Pascal Triangle | Medium | DP-style build | 041 | LeetCode Pascal's Triangle — <https://leetcode.com/problems/pascals-triangle/> | [042-ncr-pascal-triangle.md](042-ncr-pascal-triangle.md) | নোট আছে |
| 043 | Stars and Bars Basic | Medium | identical items split | 041 | Classic combinatorics (book: Levin, Discrete Mathematics — <https://discrete.openmathbooks.org/>) | [043-stars-and-bars.md](043-stars-and-bars.md) | নোট আছে |
| 044 | Inclusion-Exclusion Basic | Medium | overcount correction | 041 | CP-Algorithms — <https://cp-algorithms.com/combinatorics/inclusion-exclusion.html> | [044-inclusion-exclusion-basic.md](044-inclusion-exclusion-basic.md) | নোট আছে |
| 045 | Count Pairs | Easy | C(n,2) | 041 | LeetCode Number of Good Pairs — <https://leetcode.com/problems/number-of-good-pairs/> | [045-count-pairs.md](045-count-pairs.md) | নোট আছে |
| 046 | Count Triplets | Medium | C(n,3) / grouping | 045 | Classic exercise | [046-count-triplets.md](046-count-triplets.md) | নোট আছে |
| 047 | Count Subsets | Easy | 2^n choices | 041 | Concept link: LeetCode Subsets — <https://leetcode.com/problems/subsets/> | [047-count-subsets.md](047-count-subsets.md) | নোট আছে |
| 048 | Count Paths in Grid | Medium | C(m+n, n) | 041 | LeetCode Unique Paths — <https://leetcode.com/problems/unique-paths/> | [048-count-paths-in-grid.md](048-count-paths-in-grid.md) | নোট আছে |
| 049 | Catalan Number Intro | Medium | balanced structures | 048 | Related: LeetCode Unique Binary Search Trees — <https://leetcode.com/problems/unique-binary-search-trees/> | [049-catalan-number-intro.md](049-catalan-number-intro.md) | নোট আছে |
| 050 | Derangement Intro | Medium | !n recurrence | 039 | Classic combinatorics | [050-derangement-intro.md](050-derangement-intro.md) | নোট আছে |
| 051 | Pigeonhole Principle Problems | Medium | existence argument | — | Classic combinatorics | [051-pigeonhole-principle.md](051-pigeonhole-principle.md) | নোট আছে |
| 052 | Birthday Paradox Style Problems | Medium | collision probability | 051 | Classic probability | [052-birthday-paradox-style.md](052-birthday-paradox-style.md) | নোট আছে |

## Problem-দের পারিবারিক গাছ

```
039 (factorial) ─┬─> 040 (nPr) ─> 041 (nCr) ─┬─> 042 (Pascal build)
                 │                           ├─> 043 (stars and bars)
                 └─> 050 (derangement)       ├─> 044 (inclusion-exclusion)
                                             ├─> 045 (pairs) ─> 046 (triplets)
                                             ├─> 047 (subsets, 2^n)
                                             └─> 048 (grid path) ─> 049 (Catalan)

051 (pigeonhole) ─> 052 (birthday paradox)    <- আলাদা শাখা: যুক্তির খেলা
```

041 (nCr) এই গাছের কাণ্ড — ওটা পোক্ত হলে অর্ধেক level আপনিই দাঁড়িয়ে যায়। আর মনে রেখো: Level 2-এর 034 (nCr mod Prime) এই 039-এরও উপর দাঁড়িয়ে — দুই level-এর গাছ এখানে এসে মিশেছে।

## একটা ছোট পরামর্শ

Combinatorics-এ সবচেয়ে কাজের debugging tool: **brute force enumerator।** Python-এর `itertools` দিয়ে ছোট case-এর সব permutation/combination generate করে গুনে ফেলো, formula-র সাথে মেলাও — 10 লাইনের checker, কিন্তু আত্মবিশ্বাস শতগুণ। আর interview-তে উত্তর formula-তে দিলেও **গল্পটা বলতে পারা** চাই ("প্রতিটা path আসলে R/D-র সারি, তাই...") — note-এ সেই গল্পটাই নিজের ভাষায় লেখো, formula না।

Concept ঝালাই → [../concept-notes.md](../concept-notes.md)। ছবির ভাণ্ডার → [../visualization-ideas.md](../visualization-ideas.md)।