Problem link ও উৎস
- **Original source:** Classic combinatorics (book: Levin, Discrete Mathematics)
- **Platform:** Levin, Discrete Mathematics —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Medium
- **Pattern:** identical items split (stars and bars)
- **Basic idea inherited from:** 041 — Combination Basic (ছবিটা শেষে একটা nCr হয়)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n` টা **একই রকম** জিনিস (যেমন একই ব্র্যান্ডের চকলেট — আলাদা করে চেনা যায় না) `k` জনে ভাগ করতে হবে। কেউ 0টাও পেতে পারে। কত ভাবে ভাগ করা যায়?
সমান প্রশ্নের আরেকটা চেহারা (interview-তে এভাবেই বেশি আসে): **`x₁ + x₂ + ... + xₖ = n`** সমীকরণের কয়টা non-negative integer solution আছে?
দুটো এক জিনিস — চকলেট = মোট n, প্রতি বন্ধুর ভাগ = `xᵢ`।
যেমন 3টা চকলেট 2 জনে: (0,3), (1,2), (2,1), (3,0) — মোট 4 উপায়।
### Input ও output {#6-example-input-and-output}
```text
input (n items, k people) -> output = C(n+k−1, k−1)
----------------------------------------------------
(3, 2) -> 4 C(4, 1) = 4
(7, 3) -> 36 C(9, 2) = 36
(5, 1) -> 1 সব 1 জনকে -> 1 উপায়
(0, 3) -> 1 কিছু নেই, সবাই 0 -> 1 উপায়
(4, 2) -> 5 C(5, 1) = 5: (0,4)(1,3)(2,2)(3,1)(4,0)
(2, 3) -> 6 C(4, 2) = 6
```
Edge case: **`k = 1`** হলে সব n একজনকে → 1 উপায় (`C(n, 0) = 1`); **`n = 0`** হলে সবাই 0 → 1 উপায়। আর "প্রত্যেকে অন্তত 1" চাইলে formula বদলায় (section 9 দেখো)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার হাতে `n = 7` টা **একই রকম** লজেন্স, আর `k = 3` জন বাচ্চা — সমান ভাগ করার দরকার নেই, যেভাবে খুশি দিতে পারো (কেউ 0টাও পেতে পারে)।
লজেন্সগুলো এক সারিতে রাখো। এবার 2টা (k−1 = 2) লাঠি (bar) বসিয়ে সারিটাকে 3 ভাগে ভাগ করো — প্রথম ভাগ প্রথম বাচ্চার, মাঝেরটা দ্বিতীয়জনের, শেষটা তৃতীয়জনের।
লাঠি দুটো কোথায় বসাবে — সেটাই পুরো ভাগ-ব্যবস্থা ঠিক করে দেয়! তাই "কত ভাবে ভাগ" = "7 লজেন্স + 2 লাঠি = 9টা জায়গায় 2টা লাঠির জায়গা কত ভাবে বাছা যায়" = `C(9, 2) = 36`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা **041 (Combination Basic)**-এর উপর দাঁড়িয়ে। পুরো চালাকিটার শেষ ধাপ একটা সাধারণ nCr — শুধু কোন nCr সেটা বের করতে star-bar ছবিটা লাগে।
মূল গল্প: "একই রকম জিনিস ভাগ" সরাসরি multiplication principle-এ ধরা দেয় না (কারণ জিনিসগুলো আলাদা নয়, তাই সাজানো অর্থহীন)। কিন্তু ছবিটা সমস্যাটাকে বদলে দেয় "n+k−1 টা জায়গার মধ্যে k−1 টা bar-এর জায়গা বাছা"-তে — আর সেটা তো খাঁটি combination, যেটা 041-এ শিখেছ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **জিনিসটাকে star-bar সাজানোয় অনুবাদ করা।**
n টা চকলেটকে star (★) হিসেবে এক সারিতে রাখো। k জনে ভাগ করতে দরকার `k−1` টা **bar** (|) — bar গুলো star-দের কয়টা টুকরোয় ভাগ করে:
```text
★★ | ★★★★ | ★ -> A: 2, B: 4, C: 1
```
মোট জিনিস = n টা star + (k−1) টা bar = `n + k − 1` টা জায়গা। এর মধ্যে শুধু **bar-গুলো কোথায় বসবে** ঠিক করলেই ভাগ ঠিক হয়ে যায়:
```text
উপায় = C(n + k − 1, k − 1)
```
(সমানভাবে star-দের জায়গা বাছলেও হয়: `C(n + k − 1, n)` — symmetry।)
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
ছোট case-এ সবচেয়ে সরাসরি — **সব ভাগ nested loop-এ গুনে ফেলা।** k = 3, মোট n হলে:
```python
def stars_bars_brute(n, k):
if k == 1:
return 1 # সব একজনকে
count = 0
# প্রথম জনকে a, বাকি (n-a) recursively k-1 জনে ভাগ
for a in range(n + 1):
count += stars_bars_brute(n - a, k - 1)
return count
```
এটা সংজ্ঞার সরাসরি গোনা — প্রথম জনকে 0 থেকে n কত দিতে পারি, প্রতিটার জন্য বাকিটা বাকিদের মধ্যে ভাগ। ছোট n, k-তে একদম ঠিক — আর formula verify করার নিখুঁত উপায়।
(আরও সরল verify: `itertools.product` বা nested loop দিয়ে সব `(x₁,...,xₖ)` ঘুরে যেগুলোর যোগ n, সেগুলো গোনা।)
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই recursion-ও **একই উপ-সমস্যা বারবার** করে, আর ভাগের সংখ্যা দ্রুত বাড়ে:
```text
n = 50, k = 10 হলে উত্তর = C(59, 9) ≈ 1.2 কোটি
brute force সবগুলো একে একে গুনতে গেলে কোটি কোটি ধাপ -> অসম্ভব ধীর
আর nested loop (k স্তর) হলে প্রায় O(n^(k-1)) -> k একটু বড় হলেই বিস্ফোরণ
```
মোট ভাগ-সংখ্যাই বিশাল, তাই একে একে গোনা অর্থহীন যখন একটা formula এক ধাপে উত্তর দেয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: গোনার দরকার নেই — **star-bar ছবিটা সমস্যাটাকে একটা nCr-এ বদলে দেয়।** n star আর k−1 bar, মোট n+k−1 জায়গা, bar-এর জায়গা বাছো:
```python
def stars_and_bars(n, k):
"""n একই জিনিস, k জনে, কেউ 0 পেতে পারে।"""
from math import comb
return comb(n + k - 1, k - 1)
```
এক ধাপে উত্তর — কোটি কোটি ভাগ না গুনেই।
**"প্রত্যেকে অন্তত 1" চাইলে?** আগে প্রত্যেককে 1টা করে দিয়ে দাও (k টা খরচ হলো, n−k বাকি), তারপর বাকিটা একই খেলায় ভাগ:
```python
def stars_and_bars_positive(n, k):
"""প্রত্যেকে অন্তত 1 পায়।"""
from math import comb
if n < k:
return 0 # সবাইকে 1 দেওয়াই যায় না
return comb(n - 1, k - 1)
```
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **"একই রকম জিনিস ভাগ" সরাসরি গুনো না — bar বসিয়ে ছবিটাকে 'কোথায় bar বসবে' প্রশ্নে বদলে দাও।**
কারণ জিনিসগুলো আলাদা নয়, তাই কোন star কোথায় তাতে কিছু যায় আসে না — পুরো তথ্যটা আছে শুধু bar-গুলোর অবস্থানে। n+k−1 জায়গায় k−1 bar বাছা = combination। এই "ভাগ-সমস্যাকে অবস্থান-বাছাই-এ অনুবাদ" মোচড়টাই stars and bars-এর প্রাণ, আর interview-তে ছদ্মবেশে আসা "কয়টা non-negative solution" প্রশ্নের চাবি।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো একই star-bar সারি কীভাবে এক-একটা ভাগ বোঝায় (n=7, k=3):
```text
★★|★★★★|★ -> A:2 B:4 C:1
|★★★★★★★| -> A:0 B:7 C:0 (bar পাশাপাশি = মাঝেরজন সব)
★★★★★★★|| -> A:7 B:0 C:0
★★★|★★|★★ -> A:3 B:2 C:2
প্রতিটা আলাদা bar-বিন্যাস = আলাদা একটা ভাগ
```
এবার দেখো কেন উত্তর একটা nCr:
```text
মোট জায়গা = 7 star + 2 bar = 9 টা ঘর:
[ _ _ _ _ _ _ _ _ _ ] <- 9 টা ঘর
এর মধ্যে 2 টা ঘরে bar বসবে, বাকিতে star
bar-এর জায়গা বাছা = C(9, 2) = 36
সাধারণ রূপ: n star, k−1 bar -> C(n + k − 1, k − 1)
```
লক্ষ করো — star আলাদা করে চেনা যায় না বলেই শুধু "bar কোথায়" গুরুত্বপূর্ণ, star সাজানো নয়।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `n = 3` চকলেট, `k = 2` জন — formula `C(3+2−1, 2−1) = C(4, 1) = 4`।
হাতে যাচাই — star-bar সব বিন্যাস (3 star, 1 bar, মোট 4 জায়গা, bar-এর জায়গা বাছি):
| bar যেখানে | star-bar ছবি | ভাগ (A, B) |
| --- | --- | --- |
| জায়গা 1 | `\|★★★` | (0, 3) |
| জায়গা 2 | `★\|★★` | (1, 2) |
| জায়গা 3 | `★★\|★` | (2, 1) |
| জায়গা 4 | `★★★\|` | (3, 0) |
ঠিক 4টা — formula `C(4,1) = 4`-এর সাথে মিলল ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from math import comb
def stars_and_bars(n, k):
"""n একই রকম জিনিস k জনে ভাগ (কেউ 0 পেতে পারে): C(n+k-1, k-1)।"""
if k <= 0:
return 0
return comb(n + k - 1, k - 1)
def stars_and_bars_positive(n, k):
"""প্রত্যেকে অন্তত 1 পায়: C(n-1, k-1)।"""
if k <= 0 or n < k:
return 0
return comb(n - 1, k - 1)
# --- brute force verifier (ছোট case-এর সব ভাগ গুনে formula মেলায়) ---
def brute_count(n, k):
"""x1+...+xk = n, সব xi >= 0 -- কয়টা solution, একে একে গুনে।"""
if k == 1:
return 1
total = 0
for first in range(n + 1):
total += brute_count(n - first, k - 1)
return total
def brute_count_positive(n, k):
if k == 1:
return 1 if n >= 1 else 0
total = 0
for first in range(1, n - (k - 1) + 1): # প্রত্যেকে >=1
total += brute_count_positive(n - first, k - 1)
return total
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert stars_and_bars(3, 2) == 4
assert stars_and_bars(7, 3) == 36
assert stars_and_bars(5, 1) == 1
assert stars_and_bars(0, 3) == 1
assert stars_and_bars(4, 2) == 5
assert stars_and_bars(2, 3) == 6
# formula == brute force (ছোট range জুড়ে)
for n in range(0, 9):
for k in range(1, 6):
assert stars_and_bars(n, k) == brute_count(n, k)
# "প্রত্যেকে অন্তত 1" version-ও brute-এর সাথে মেলে
for n in range(0, 12):
for k in range(1, 6):
assert stars_and_bars_positive(n, k) == brute_count_positive(n, k)
assert stars_and_bars_positive(7, 3) == comb(6, 2) # 15
assert stars_and_bars_positive(2, 3) == 0 # 3 জনকে 1 করে দিতে 3 লাগে
print(stars_and_bars(3, 2)) # 4
print(stars_and_bars(7, 3)) # 36
print(stars_and_bars_positive(7, 3)) # 15
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def stars_and_bars(n, k):
if k <= 0:
return 0
return comb(n + k - 1, k - 1)
```
মূল formula — n+k−1 জায়গায় k−1 bar বাছা। `k <= 0` অর্থহীন, তাই 0।
```text
def stars_and_bars_positive(n, k):
if k <= 0 or n < k:
return 0
return comb(n - 1, k - 1)
```
প্রত্যেকে অন্তত 1: আগে সবাইকে 1টা দিলে n−k বাকি, একই খেলা → `C((n−k)+k−1, k−1) = C(n−1, k−1)`। n < k হলে সবাইকে 1ও দেওয়া যায় না → 0।
```text
def brute_count(n, k):
if k == 1:
return 1
total = 0
for first in range(n + 1):
total += brute_count(n - first, k - 1)
return total
```
verify-র জন্য একে একে গোনা — প্রথম জনকে 0..n দিয়ে, বাকিটা recursively। ছোট case-এ formula মেলানোর নিশ্চিত উপায়।
বাকি `assert` লাইনগুলো formula-কে brute force-এর সাথে পুরো ছোট range জুড়ে মেলাচ্ছে — দুই দিক থেকে। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
4
36
15
সব test pass!
```
তিনটা print: `stars_and_bars(3,2)` = 4, `stars_and_bars(7,3)` = 36, `stars_and_bars_positive(7,3)` = 15 (`C(6,2)`)। তার আগের সব `assert` (formula বনাম brute force, দুই version-ই) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
formula version **O(k)** (একটা `comb(n+k−1, k−1)` হিসাব — ভেতরে min(k−1, n) টা গুণ-ভাগ)। brute force-এর O(n^(k−1)) থেকে আকাশ-পাতাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু formula হিসাব, কোনো বাড়তি list বা table নেই (`comb`-এর ভেতরের সামান্য জায়গা বাদে)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **"0 চলবে" আর "অন্তত 1" গুলিয়ে ফেলা** — 0 হলে `C(n+k−1, k−1)`; প্রত্যেকে ≥1 হলে আগে k বিলিয়ে `C(n−1, k−1)`।
2. **bar-সংখ্যা ভুল** — k ভাগ করতে লাগে `k−1` টা bar, k টা নয়।
3. **জিনিস আলাদা ভেবে ফেলা** — stars and bars শুধু **একই রকম** জিনিসে খাটে; আলাদা জিনিস হলে অন্য হিসাব (kⁿ ইত্যাদি)।
4. **`n < k`-এ "অন্তত 1" ভুল** — সবাইকে 1ও দেওয়া না গেলে উত্তর 0।
5. **C(n+k−1, n) আর C(n+k−1, k−1) নিয়ে দ্বিধা** — দুটো সমান (symmetry), যেকোনোটা ঠিক।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Integer Break সদৃশ counting** ও non-negative solution counting — stars and bars-এর সরাসরি ক্ষেত্র।
- **CSES — Distributing Apples** (