041 — Combination Basic

এটা এই পুরো level-এর কাণ্ড (trunk) — এই একটা note পোক্ত হলে অর্ধেক level আপনিই দাঁড়িয়ে যায়। Permutation শিখেছ (order matters); এবার ঠিক উল্টোটা: শুধু দল, ক্রম অর্থহীন। 5 জন থেকে 3 জনের committee — কে আগে কে পরে তাতে কিছু আসে যায় না। এই "ক্রম ভুলে যাও" idea-টাই combination, আর DSA-র অসংখ্য counting problem-এর প্রাণ। ধীরে পড়ো, এটাই সবচেয়ে দামি।

Source

• Original source: Classic exercise (combination fundamentals)
• Platform: Classic exercise — https://discrete.openmathbooks.org/
• Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
• Difficulty: Easy
• Pattern: nCr (combination / binomial coefficient)
• Basic idea inherited from: 040 — Permutation Basic (nPr কে r! দিয়ে ভাগ)

1. Problem in simple words

n টা আলাদা জিনিস আছে। তার মধ্যে থেকে r টা বেছে নিতে হবে — কিন্তু এবার সাজানো নয়, শুধু বাছাই। কত ভাবে করা যায়?

এই সংখ্যাটাকে বলে combination, লেখা হয় C(n, r), nCr, বা ⁿCᵣ।

সবচেয়ে জরুরি পার্থক্য: এখানে ক্রম গুরুত্বপূর্ণ নয়। মানে {A, B} দল আর {B, A} দল — একই জিনিস, একবারই গোনা হবে।

যেমন 3 জন (A, B, C) থেকে 2 জনের দল: {A,B}, {A,C}, {B,C} — মোট 3 উপায়। (permutation-এ ছিল 6, কারণ সেখানে AB আর BA আলাদা; এখানে এক।) তাই C(3, 2) = 3।

2. What is the math idea?

মূল idea: combination = permutation কিন্তু ভেতরের সাজানো গুনো না।

permutation-এ প্রতিটা r-জনের দলকে আবার r! ভাবে সাজানো হয়, মানে একই দল r! বার গোনা হয়ে যায়। তাই সেই overcounting ঠিক করতে r! দিয়ে ভাগ করো:

C(n, r) = P(n, r) / r! = n! / (r! × (n − r)!)

আরেকটা সুন্দর সম্পত্তি — symmetry: C(n, r) = C(n, n−r)। কারণ r জনকে বাছা মানেই বাকি n−r জনকে "বাছলাম না" বলে আলাদা করা — একই কাজ!

3. Which basic idea does this inherit from?

এটা সরাসরি 040 (Permutation Basic)-এর উপর দাঁড়িয়ে, যা আবার 039 (Factorial)-এর উপর। চেইনটা দেখো:

• 039: n! = সব জিনিস সাজানো
• 040: P(n, r) = n!/(n−r)! = r জন বেছে সাজানো (order matters)
• 041: C(n, r) = P(n, r)/r! = r জন বেছে, সাজানো বাদ (order ভুলে যাও)

মূল গল্প: permutation-এ একই দলকে ভেতরে r! ভাবে সাজিয়ে r! বার গোনা হয়েছে। দল গুনতে চাই, সাজানো নয় — তাই r! দিয়ে ভাগ করে সেই বাড়তি গোনা মুছি। এই 041-ই হবে 042–048-এর প্রায় সবার ভিত্তি।

4. Real-life analogy

ভাবো ক্লাসে n = 5 জন আছে, আর শিক্ষক r = 3 জনের একটা group বানাবেন একসাথে project করার জন্য।

• যদি প্রতিটা group-এর ভেতরে কে leader, কে assistant — পদ থাকত, তাহলে order গুরুত্বপূর্ণ → permutation (P(5,3) = 60)।
• কিন্তু এখানে শুধু "এই 3 জন একসাথে" — কোনো পদ নেই, কে আগে নাম লিখল তাতে কিছু যায় আসে না → combination।

{রিমা, করিম, সোহা} group — তুমি যে ক্রমেই নাম ডাকো, group একটাই। তাই P(5,3) = 60-কে 3! = 6 (একই 3 জনকে সাজানোর উপায়) দিয়ে ভাগ → C(5,3) = 10 টা আলাদা group।

5. Visual explanation

প্রথমে দেখো permutation থেকে কীভাবে combination নামে — একই দল কতবার গোনা হয়:

3 জন (A, B, C) থেকে 2 জন:

permutation (order matters) -> 6 টা:
   AB   BA   |   AC   CA   |   BC   CB
   \___/         \___/         \___/
  একই দল {A,B}  একই দল {A,C}  একই দল {B,C}

প্রতি 2! = 2 টা সাজানো = একই দল
তাই combination = 6 / 2 = 3 টা দল:  {A,B} {A,C} {B,C}

এবার দেখো formula-তে কীভাবে কাটে (C(5,3)):

        P(5,3)     5 × 4 × 3      60
C(5,3) = ------ = ----------- = ----- = 10
          3!        3 × 2 × 1      6

symmetry: C(5,3) = C(5,2) = 10   (3 জন বাছা = 2 জন বাদ দেওয়া)

লক্ষ করো — উপরে r টা গুণ (n থেকে নিচে), নিচে r! — দুটোতেই ঠিক r টা সংখ্যা।

6. Example input and output

input (n, r)  ->  output
------------------------
   (3, 2)     ->  3        (P(3,2)/2! = 6/2)
   (5, 3)     ->  10       (60/6)
   (5, 2)     ->  10       (symmetry: C(5,2) = C(5,3))
   (5, 0)     ->  1        (কিছু না বাছার 1 উপায়)
   (5, 5)     ->  1        (সবাইকে বাছার 1 উপায়)
   (6, 3)     ->  20

Edge case গুলো: C(n, 0) = 1 (খালি দল = 1 উপায়), C(n, n) = 1 (সবাইকে নেওয়া = 1 উপায়), আর r > n হলে 0 (যত আছে তার বেশি বাছা যায় না)।

7. Brute force thinking

সবচেয়ে সরাসরি — সংজ্ঞা মেনে তিনটা factorial হিসাব করে ভাগ:

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def nCr_brute(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

এটা n! / (r! (n−r)!)-এর হুবহু অনুবাদ — ঠিক উত্তর দেয়।

verify করার জন্য আসল brute force: itertools.combinations দিয়ে ছোট case-এর সব দল generate করে গুনে formula মেলানো — combinatorics-এ এটাই সবচেয়ে নিশ্চিন্ত checker।

8. Why brute force may be slow

তিনটা পুরো factorial বানানো অপচয়। বড় n-এ n! মহাজাগতিক সংখ্যা, অথচ উত্তর হয়তো ছোট:

C(100, 2) = 4950   (ছোট উত্তর!)
কিন্তু brute force আগে বানায়:
  100! -> 158 digit-এর দানব
  2!, 98! -> আরও দুটো বিশাল সংখ্যা
  তারপর ভাগ করে নামায় 4950-তে

বিশাল মাঝপথের সংখ্যা বানিয়ে তারপর কেটে ফেলা — সময় আর memory দুটোরই অপচয়। আর modular জগতে (Level 2) সরাসরি ভাগ তো নিষেধই!

9. Better thinking

দুটো ভালো পথ:

পথ 1 — সরাসরি গুণ-ভাগ (factorial ছাড়া): C(n, r) = (n × (n−1) × ... × (n−r+1)) / r! — মানে nPr বের করে r! দিয়ে ভাগ। মাঝপথের সংখ্যা ছোট রাখতে প্রতি ধাপে গুণ করে ভাগ:

def nCr(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)               # symmetry: কম দিকটা নাও (কম কাজ)
    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)
    return result

প্রতি ধাপে result × (n−i) সবসময় (i+1) দিয়ে নিঃশেষে ভাগ যায় (combinatorics-এর সুন্দর সত্য), তাই integer-ই থাকে।

পথ 2 — Pascal triangle build: C(n,r) = C(n−1,r−1) + C(n−1,r) — পরের problem 042-এর মূল বিষয়।

r = min(r, n−r) লাইনটা symmetry কাজে লাগিয়ে loop ছোট করে — C(100, 98)-কে C(100, 2)-এর মতো অল্প কাজে নামায়।

10. Thinking tweak

আসল "আহা" মুহূর্ত: permutation গোনো, তারপর ভেতরের সাজানো (r!) ভাগ করে মুছে দাও।

মনে মনে দুই ধাপ: (১) r জন বেছে সাজাও = nPr; (২) কিন্তু আমি তো সাজানো চাই না, শুধু দল — প্রতিটা দল r! বার গোনা হয়েছে, তাই r! দিয়ে ভাগ। এই "overcount করে তারপর ভাগ করে শোধরাও" চিন্তাটা combinatorics-এর সবচেয়ে শক্তিশালী অস্ত্রগুলোর একটা — stars and bars, grid path — সবখানে ফিরবে।

আর symmetry-র tweak: C(n, r) = C(n, n−r) — r বড় হলে n−r নাও, কাজ কমে।

11. Step-by-step dry run

চলো C(5, 2) চালাই (path 1, r = min(2, 3) = 2, loop i = 0, 1):

step (i)	result (শুরুতে)	result × (n−i)	// (i+1)	result (পরে)
শুরু	—	—	—	1
0	1	1 × 5 = 5	5 // 1	5
1	5	5 × 4 = 20	20 // 2	10

Loop শেষ → result = 10 → C(5, 2) = 10 ✓।

মনে মনে মেলাও: 5 জন থেকে 2 জনের দল — {12,13,14,15,23,24,25,34,35,45} — ঠিক 10টা ✓।

12. Python solution

def nCr(n, r):
    """C(n, r): n জিনিস থেকে r টা বেছে নেওয়ার উপায় (order matters না)।"""
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)               # symmetry: কম দিকটা নিলে loop ছোট
    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)
    return result


# --- ছোট test গুলো (সব pass করা উচিত) ---
import math
from itertools import combinations

assert nCr(3, 2) == 3
assert nCr(5, 3) == 10
assert nCr(5, 2) == 10              # symmetry
assert nCr(5, 0) == 1
assert nCr(5, 5) == 1
assert nCr(6, 3) == 20
assert nCr(3, 5) == 0              # r > n

# math.comb দিয়ে cross-check (পুরো triangle 0..12)
for n in range(0, 13):
    for r in range(0, n + 1):
        assert nCr(n, r) == math.comb(n, r)

# symmetry নিজে যাচাই
for n in range(0, 13):
    for r in range(0, n + 1):
        assert nCr(n, r) == nCr(n, n - r)

# brute force: itertools দিয়ে সব দল গুনে formula মেলানো
def nCr_count(items, r):
    return sum(1 for _ in combinations(items, r))

assert nCr(5, 2) == nCr_count([1, 2, 3, 4, 5], 2)   # 10
assert nCr(6, 3) == nCr_count([1, 2, 3, 4, 5, 6], 3)  # 20

print(nCr(3, 2))    # 3
print(nCr(5, 3))    # 10
print(nCr(6, 3))    # 20
print("সব test pass!")

13. Line-by-line explanation

def nCr(n, r):
    if r < 0 or r > n:
        return 0

পাহারা — অসম্ভব ক্ষেত্রে (negative বা r > n) উত্তর 0।

    r = min(r, n - r)

symmetry কাজে লাগাই — C(n, r) = C(n, n−r), তাই ছোট r নিয়ে loop ছোট করি।

    result = 1
    for i in range(r):
        result = result * (n - i) // (i + 1)

এটাই হৃদয়। i = 0, 1, ..., r−1-এ ধাপে ধাপে উপরের গুণ (n−i) করি, সাথে সাথে নিচের (i+1) দিয়ে ভাগ। প্রতি ধাপে ভাগ নিঃশেষ হয়, তাই integer থাকে আর মাঝপথের সংখ্যা ছোট থাকে।

def nCr_count(items, r):
    return sum(1 for _ in combinations(items, r))

verify-র brute force — itertools.combinations ছোট list-এর সব r-দলের তালিকা, আমরা গুনি; formula মেলানোর নিশ্চিন্ত উপায়।

বাকি assert লাইনগুলো math.comb, symmetry আর brute count-এর সাথে মিলিয়ে চেক করছে। সব মিললে শেষে সব test pass!।

14. Output walkthrough

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

3
10
20
সব test pass!

তিনটা print(nCr(...)) থেকে: (3,2) → 3, (5,3) → 10, (6,3) → 20। তার আগের সব assert (math.comb, symmetry, itertools brute force — তিন দিক থেকে cross-check) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity

O(r) (আসলে O(min(r, n−r)) symmetry-র জন্য) — loop ততবার চলে, প্রতিবার একটা গুণ আর ভাগ। factorial বানানোর O(n) আর বিশাল মাঝসংখ্যা — দুটোই এড়ানো গেল।

16. Space complexity

O(1) — শুধু একটা result variable, কোনো table বা list নেই (উত্তর সংখ্যাটার নিজের জায়গা বাদে)।

17. Common mistakes

1. Order matters কি না না ভেবে P বসিয়ে দেওয়া — "committee/দল/বেছে নাও" = C; "সাজাও/পদ" = P। আগে এই প্রশ্ন করো।
2. তিন factorial বানিয়ে ভাগ — বড় n-এ ভয়ানক slow আর বিশাল মাঝসংখ্যা; সরাসরি গুণ-ভাগ বা Pascal নাও।
3. C(n, 0) বা C(n, n) ভুল ভাবা — দুটোই 1 (খালি দল, পুরো দল — প্রতিটা ঠিক একভাবে)।
4. Modular জগতে সরাসরি ভাগ — % MOD-এ // কাজ করে না; তখন Level 2-এর fact + inverse pipeline (problem 034) লাগে।
5. r > n ভুলে যাওয়া — উত্তর 0; check না করলে loop ভুল করতে পারে।

18. Harder problems that inherit this idea

• 042 — nCr using Pascal Triangle (এই repo) — একই nCr DP-পথে।
• 045 — Count Pairs (এই repo) — C(n, 2)-এর সরাসরি প্রয়োগ।
• 048 — Count Paths in Grid (এই repo) — grid path = C(m+n, n)।
• LeetCode — Unique Paths (https://leetcode.com/problems/unique-paths/) — combination-এর জীবন্ত রূপ।

19. Pattern learned

Combination = permutation / r! (overcount then divide) — দল বাছতে হলে আগে সাজিয়ে গোনো (nPr), পরে r! দিয়ে ভাগ করে সাজানোর বাড়তি মুছে দাও। মূল signal: "বেছে নাও / দল / কয়টা উপসেট" দেখলেই combination — order অর্থহীন। সাথে symmetry: C(n,r) = C(n,n−r)।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "C(n,r) = n!/(r!(n−r)!) = nPr/r!; 'order matters?' না হলে combination। factorial বানিয়ো না — গুণে-ভাগে নামাও, আর C(n,r)=C(n,n−r)। এটাই level-এর কাণ্ড।"

পরের ধাপ → 042 — nCr using Pascal Triangle (একই nCr এবার DP-র চোখে — C(n,r)=C(n−1,r−1)+C(n−1,r))।

ফিরে দেখা: আগের ধাপ → 040 — Permutation Basic · এই 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"।