Problem link ও উৎস
- **Original source:** Classic exercise (combination fundamentals)
- **Platform:** Classic exercise —
- **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! দিয়ে ভাগ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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`।
### Input ও output {#6-example-input-and-output}
```text
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 (যত আছে তার বেশি বাছা যায় না)।
### চেনা উদাহরণে বোঝা {#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।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এর প্রায় সবার ভিত্তি।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea: **combination = permutation কিন্তু ভেতরের সাজানো গুনো না।**
permutation-এ প্রতিটা r-জনের দলকে আবার r! ভাবে সাজানো হয়, মানে একই দল r! বার গোনা হয়ে যায়। তাই সেই overcounting ঠিক করতে r! দিয়ে ভাগ করো:
```text
C(n, r) = P(n, r) / r! = n! / (r! × (n − r)!)
```
আরেকটা সুন্দর সম্পত্তি — **symmetry**: `C(n, r) = C(n, n−r)`। কারণ r জনকে বাছা মানেই বাকি n−r জনকে "বাছলাম না" বলে আলাদা করা — একই কাজ!
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি — সংজ্ঞা মেনে তিনটা factorial হিসাব করে ভাগ:
```python
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!` মহাজাগতিক সংখ্যা, অথচ উত্তর হয়তো ছোট:
```text
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! দিয়ে ভাগ। মাঝপথের সংখ্যা ছোট রাখতে প্রতি ধাপে গুণ করে ভাগ:
```python
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 নাও, কাজ কমে।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো permutation থেকে কীভাবে combination নামে — একই দল কতবার গোনা হয়:
```text
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)):
```text
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 টা সংখ্যা।
### ছোট input-এ ধাপে ধাপে {#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টা ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
def nCr(n, r):
if r < 0 or r > n:
return 0
```
পাহারা — অসম্ভব ক্ষেত্রে (negative বা r > n) উত্তর 0।
```text
r = min(r, n - r)
```
symmetry কাজে লাগাই — `C(n, r) = C(n, n−r)`, তাই ছোট r নিয়ে loop ছোট করি।
```text
result = 1
for i in range(r):
result = result * (n - i) // (i + 1)
```
এটাই হৃদয়। i = 0, 1, ..., r−1-এ ধাপে ধাপে উপরের গুণ (n−i) করি, সাথে সাথে নিচের (i+1) দিয়ে ভাগ। প্রতি ধাপে ভাগ নিঃশেষ হয়, তাই integer থাকে আর মাঝপথের সংখ্যা ছোট থাকে।
```text
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!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 ভুল করতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#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** (