Skip to content

Problems — Level 3: Counting & Combinatorics

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

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

প্রতিটা note লেখা হয় ../../../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-এর recommended order ধরো — factorial থেকে শুরু, paradox দিয়ে শেষ
  2. প্রতিটা problem-এ আগে ছবি আঁকো, পরে code
  3. Solve হলে Status planned → done

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
039 Factorial Easy n! — Classic exercise 039-factorial.md planned
040 Permutation Basic Easy nPr 039 Classic exercise 040-permutation-basic.md planned
041 Combination Basic Easy nCr 040 Classic exercise 041-combination-basic.md planned
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 planned
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 planned
044 Inclusion-Exclusion Basic Medium overcount correction 041 CP-Algorithms — https://cp-algorithms.com/combinatorics/inclusion-exclusion.html 044-inclusion-exclusion-basic.md planned
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 planned
046 Count Triplets Medium C(n,3) / grouping 045 Classic exercise 046-count-triplets.md planned
047 Count Subsets Easy 2^n choices 041 Concept link: LeetCode Subsets — https://leetcode.com/problems/subsets/ 047-count-subsets.md planned
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 planned
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 planned
050 Derangement Intro Medium !n recurrence 039 Classic combinatorics 050-derangement-intro.md planned
051 Pigeonhole Principle Problems Medium existence argument — Classic combinatorics 051-pigeonhole-principle.md planned
052 Birthday Paradox Style Problems Medium collision probability 051 Classic probability 052-birthday-paradox-style.md planned

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। ছবির ভাণ্ডার → ../visualization-ideas.md।