043 — Stars and Bars Basic¶

এবার একটা সত্যিকারের চালাকি — এত সুন্দর যে প্রথমবার দেখলে মুগ্ধ হবে। প্রশ্ন: একই রকম (আলাদা করে চেনা যায় না) কতগুলো জিনিস কয়েকজনে ভাগ করতে কত উপায়? সরাসরি গোনা কঠিন, কিন্তু একটা ছবি আঁকলে — star আর bar সাজানো — পুরো সমস্যাটা মুহূর্তে combination-এ বদলে যায়। কাগজে star-bar এঁকে ছোট case হাতে গুনো, তারপর formula — তাহলেই গেঁথে যাবে।

Source¶

Original source: Classic combinatorics (book: Levin, Discrete Mathematics)
Platform: Levin, Discrete Mathematics — https://discrete.openmathbooks.org/
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 হয়)

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 উপায়।

2. What is the math idea?¶

মূল idea — জিনিসটাকে star-bar সাজানোয় অনুবাদ করা।

n টা চকলেটকে star (★) হিসেবে এক সারিতে রাখো। k জনে ভাগ করতে দরকার k−1 টা bar (|) — bar গুলো star-দের কয়টা টুকরোয় ভাগ করে:

★★ | ★★★★ | ★   ->  A: 2, B: 4, C: 1

মোট জিনিস = n টা star + (k−1) টা bar = n + k − 1 টা জায়গা। এর মধ্যে শুধু bar-গুলো কোথায় বসবে ঠিক করলেই ভাগ ঠিক হয়ে যায়:

উপায় = C(n + k − 1, k − 1)

(সমানভাবে star-দের জায়গা বাছলেও হয়: C(n + k − 1, n) — symmetry।)

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-এ শিখেছ।

4. Real-life analogy¶

ভাবো তোমার হাতে n = 7 টা একই রকম লজেন্স, আর k = 3 জন বাচ্চা — সমান ভাগ করার দরকার নেই, যেভাবে খুশি দিতে পারো (কেউ 0টাও পেতে পারে)।

লজেন্সগুলো এক সারিতে রাখো। এবার 2টা (k−1 = 2) লাঠি (bar) বসিয়ে সারিটাকে 3 ভাগে ভাগ করো — প্রথম ভাগ প্রথম বাচ্চার, মাঝেরটা দ্বিতীয়জনের, শেষটা তৃতীয়জনের।

লাঠি দুটো কোথায় বসাবে — সেটাই পুরো ভাগ-ব্যবস্থা ঠিক করে দেয়! তাই "কত ভাবে ভাগ" = "7 লজেন্স + 2 লাঠি = 9টা জায়গায় 2টা লাঠির জায়গা কত ভাবে বাছা যায়" = C(9, 2) = 36।

5. Visual explanation¶

প্রথমে দেখো একই star-bar সারি কীভাবে এক-একটা ভাগ বোঝায় (n=7, k=3):

★★|★★★★|★    ->  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:

মোট জায়গা = 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 সাজানো নয়।

6. Example input and output¶

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 দেখো)।

7. Brute force thinking¶

ছোট case-এ সবচেয়ে সরাসরি — সব ভাগ nested loop-এ গুনে ফেলা। k = 3, মোট n হলে:

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-ও একই উপ-সমস্যা বারবার করে, আর ভাগের সংখ্যা দ্রুত বাড়ে:

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-এর জায়গা বাছো:

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 বাকি), তারপর বাকিটা একই খেলায় ভাগ:

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" প্রশ্নের চাবি।

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-এর সাথে মিলল ✓।

12. Python solution¶

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¶

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।

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।

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!।

14. Output walkthrough¶

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

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!।

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¶

"0 চলবে" আর "অন্তত 1" গুলিয়ে ফেলা — 0 হলে C(n+k−1, k−1); প্রত্যেকে ≥1 হলে আগে k বিলিয়ে C(n−1, k−1)।
bar-সংখ্যা ভুল — k ভাগ করতে লাগে k−1 টা bar, k টা নয়।
জিনিস আলাদা ভেবে ফেলা — stars and bars শুধু একই রকম জিনিসে খাটে; আলাদা জিনিস হলে অন্য হিসাব (kⁿ ইত্যাদি)।
n < k-এ "অন্তত 1" ভুল — সবাইকে 1ও দেওয়া না গেলে উত্তর 0।
C(n+k−1, n) আর C(n+k−1, k−1) নিয়ে দ্বিধা — দুটো সমান (symmetry), যেকোনোটা ঠিক।

18. Harder problems that inherit this idea¶

LeetCode — Integer Break সদৃশ counting ও non-negative solution counting — stars and bars-এর সরাসরি ক্ষেত্র।
CSES — Distributing Apples (https://cses.fi/problemset/task/1716) — হুবহু "n একই জিনিস k জনে", mod সহ — stars and bars-এর প্রামাণ্য problem।
044 — Inclusion-Exclusion Basic (এই repo) — "প্রত্যেকের সীমা আছে" (যেমন কেউ ≤5) version stars and bars + inclusion-exclusion মিলিয়ে সমাধান হয়।

19. Pattern learned¶

Stars and bars (split identical items → choose bar positions) — n একই জিনিস k জনে: C(n+k−1, k−1); প্রত্যেকে ≥1 হলে C(n−1, k−1)। মূল signal: "একই রকম জিনিস ভাগ" বা "x₁+...+xₖ = n-এর non-negative solution" দেখলেই star-bar ছবি আঁকো।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "একই জিনিস ভাগ = star-bar ছবি; n star, k−1 bar → C(n+k−1, k−1)। 'অন্তত 1' হলে আগে বিলিয়ে C(n−1, k−1)। 'কয়টা non-negative solution' দেখলেই এটা।"

পরের ধাপ → 044 — Inclusion-Exclusion Basic (overcounting-এর যোগ-বিয়োগ সংশোধন — Venn ছবি)।

ফিরে দেখা: আগের ধাপ → 041 — Combination 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"।