049 — Catalan Number Intro

এবার এক রহস্যময় সংখ্যা-ধারার সাথে পরিচয় — Catalan number: 1, 1, 2, 5, 14, 42, ... । মজার ব্যাপার, একদম আলাদা দেখতে অনেকগুলো সমস্যার উত্তর হুবহু এই একই ধারা: balanced bracket, n-node BST, mountain range, polygon triangulation। এই note-টা intro — লক্ষ্য সংখ্যাটাকে চেনা আর দুটো গল্প (bracket, BST) বোঝা, গভীর তত্ত্ব নয়। পরে tree/DP-তে এই চরিত্র পুরো রূপে ফিরবে।

Source

• Original source: Related — LeetCode Unique Binary Search Trees
• Platform: LeetCode — https://leetcode.com/problems/unique-binary-search-trees/
• Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
• Difficulty: Medium
• Pattern: balanced structures (Catalan number)
• Basic idea inherited from: 048 — Count Paths in Grid (lattice path-এর বিশেষ রূপ → Catalan)

1. Problem in simple words

n-তম Catalan number, লেখা Cat(n), বের করতে হবে। এই সংখ্যা অনেক "balanced" গোছের জিনিস গোনে। সবচেয়ে সহজ গল্প — balanced bracket:

n জোড়া bracket (মানে n টা ( আর n টা )) কত ভাবে সঠিকভাবে সাজানো যায়, যেন প্রতিটা (-এর জন্য পরে একটা মেলানো ) থাকে আর কখনো )-এর সংখ্যা (-কে ছাড়িয়ে না যায়?

যেমন n=3: ()()(), (())(), ()(()), (()()), ((())) — মোট 5টা। তাই Cat(3) = 5।

ধারা: Cat(0)=1, Cat(1)=1, Cat(2)=2, Cat(3)=5, Cat(4)=14, ...।

2. What is the math idea?

দুটো সমান চেহারা:

বন্ধ-রূপ (closed form):

Cat(n) = C(2n, n) / (n + 1)

(সমান: C(2n, n) − C(2n, n+1)।) gridপথ-এর সাথে যোগ: 2n ধাপের মধ্যে diagonal না-পেরিয়ে যাওয়া path — মোট path C(2n, n) থেকে "নিয়ম-ভাঙা" বাদ দিলে এটাই।

Recurrence (গল্প-রূপ): প্রথম (-এর মেলানো ) কোথায়, সেটা দিয়ে ভাগ করো — ভেতরে i জোড়া, বাইরে বাকি:

Cat(n) = Σ (i=0..n−1) Cat(i) × Cat(n−1−i),   Cat(0) = 1

দুটোই একই ধারা দেয়; closed form দ্রুত, recurrence গল্পটা বোঝায়।

3. Which basic idea does this inherit from?

এটা 048 (Count Paths in Grid)-এর উপর দাঁড়িয়ে। সেখানে শিখেছ grid path = R/D সাজানো = C(m+n, n)। Catalan হলো তারই একটা বিশেষ, সীমাবদ্ধ রূপ: এমন path যা কখনো diagonal পেরোয় না (অর্থাৎ সবসময় )-এর চেয়ে ( সমান-বা-বেশি)।

মূল ধারাবাহিকতা: মোট path C(2n, n) (048-এর সরাসরি প্রয়োগ); তার থেকে নিয়ম-ভাঙা path বাদ দিলে C(2n,n)/(n+1)। তাই 048-এর nCr-চিন্তা না থাকলে Catalan-এর closed form-টাই দাঁড়ায় না। আর recurrence-এ "ভেতর × বাইর" multiplication principle (039-এর শিকড়)-এরই খেলা।

4. Real-life analogy

ভাবো n জন মানুষ একটা সিনেমার টিকিট কিনছে, টিকিটের দাম 50 টাকা। অর্ধেকের (n জন) কাছে আছে 50 টাকার নোট, বাকি অর্ধেকের কাছে 100 টাকার। কাউন্টারে শুরুতে কোনো খুচরা নেই।

100-টাকার লোককে ফেরত দিতে হলে আগে একটা 50-টাকার নোট জমা থাকতে হবে। তাই লাইনে এমনভাবে দাঁড়াতে হবে যেন যেকোনো মুহূর্তে জমা-হওয়া 50-নোটের সংখ্যা ≥ চাওয়া-ফেরতের সংখ্যা — নাহলে কাউন্টার আটকে যাবে।

এই "কখনো ঘাটতি হবে না" শর্ত মানা লাইন কত রকম? — ঠিক Cat(n)! 50-নোট = (, 100-নোট = ) ভাবলেই হুবহু balanced bracket। এই "কখনো নিচে নামবে না" চরিত্রই Catalan-এর সর্বত্র লুকিয়ে।

5. Visual explanation

প্রথমে দেখো n=3-এর 5টা balanced bracket (কেন 5):

n = 3 (3 টা '(' , 3 টা ')'):

  ()()()      (())()      ()(())      (()())      ((()))
   \                                                /
    সবগুলোতেই প্রতি ')' -এর আগে যথেষ্ট '(' আছে -> valid
    মোট 5 = Cat(3)

এবার দেখো recurrence-এর গল্প (প্রথম (-এর জোড়া কোথায়):

( A ) B    -> A = ভেতরের balanced, B = বাইরের balanced
ভেতরে i জোড়া হলে বাইরে (n−1−i) জোড়া

Cat(3) = Cat(0)·Cat(2) + Cat(1)·Cat(1) + Cat(2)·Cat(0)
       =    1 · 2     +    1 · 1     +    2 · 1
       =    2 + 1 + 2 = 5 ✓

আর closed form: Cat(3) = C(6,3)/4 = 20/4 = 5 ✓ — তিন পথ, এক উত্তর।

6. Example input and output

n  ->  Cat(n)
-------------
0  ->  1       (খালি -> 1 ভাবে, বিশেষ নিয়ম)
1  ->  1       "()"
2  ->  2       "()()", "(())"
3  ->  5
4  ->  14
5  ->  42
6  ->  132
10 ->  16796

Edge case: Cat(0) = 1 (খালি bracket-সারির ঠিক একটা সাজানো — কিছু না; factorial-এর 0!=1-এর মতো)। ধারাটা দ্রুত বাড়ে কিন্তু 2ⁿ-এর চেয়ে ধীরে।

7. Brute force thinking

সবচেয়ে সরাসরি (আর গল্প-বোঝানো) — সত্যিই সব bracket-সারি বানিয়ে valid-গুলো গোনা। 2n জায়গায় প্রতিটায় ( বা ), তারপর balanced কিনা চেক:

from itertools import product

def is_balanced(s):
    bal = 0
    for ch in s:
        bal += 1 if ch == '(' else -1
        if bal < 0:                 # ')' বেশি হয়ে গেল -> invalid
            return False
    return bal == 0                 # শেষে সমান

def catalan_brute(n):
    if n == 0:
        return 1
    count = 0
    for combo in product('()', repeat=2 * n):
        if is_balanced(''.join(combo)):
            count += 1
    return count

প্রতিটা সম্ভাব্য সারি ঘুরে valid গুনি — ছোট n-এ একদম ঠিক, আর Catalan সংখ্যা চোখে যাচাইয়ের নিখুঁত উপায়।

8. Why brute force may be slow

সমস্যা — 2n জায়গায় প্রতিটায় 2 রকম, মানে 2^(2n) = 4ⁿ সারি ঘুরতে হয়, যার বেশিরভাগই invalid:

n = 10 হলে:  4^10 ≈ 10^6 সারি -> চলে কিন্তু ভারী
n = 15 হলে:  4^15 ≈ 10^9 সারি -> অসম্ভব ধীর

closed form: C(2n, n)/(n+1) -> এক ধাপে, O(n)!

মোট valid সারিই Cat(n) (যা 4ⁿ-এর তুলনায় ছোট), কিন্তু সব 4ⁿ ঘুরে valid বাছা বিরাট অপচয় — formula সরাসরি উত্তর দেয়।

9. Better thinking

দুটো ভালো পথ:

পথ 1 — closed form (সবচেয়ে দ্রুত):

from math import comb

def catalan(n):
    return comb(2 * n, n) // (n + 1)

C(2n, n) সবসময় (n+1) দিয়ে নিঃশেষে ভাগ যায় (Catalan-এর সুন্দর সত্য), তাই integer থাকে।

পথ 2 — DP recurrence (গল্প জমানো, overlapping subproblem):

def catalan_dp(n):
    cat = [0] * (n + 1)
    cat[0] = 1
    for k in range(1, n + 1):
        cat[k] = sum(cat[i] * cat[k - 1 - i] for i in range(k))
    return cat[n]

DP-তে ছোট Catalan জমিয়ে বড়টা বানাই — closed form না মনে থাকলেও এটা চলে, আর recurrence-এর গল্পটাই code।

10. Thinking tweak

আসল "আহা" মুহূর্ত: "একটা শর্ত যা কখনো ভাঙা যাবে না, শুরু থেকে শেষ পর্যন্ত balanced থাকতে হবে" — এই চরিত্র দেখলেই Catalan সন্দেহ করো।

আর recurrence-এর tweak: একটা স্বাভাবিক "প্রথম বিভাজন বিন্দু" খোঁজো (প্রথম (-এর মেলানো ), বা root node) — সেটা সমস্যাটাকে দুটো ছোট একই-ধরনের সমস্যায় ভাগ করে, আর তাদের গুণ-যোগই recurrence। এই "প্রথম মেলানো জোড়া দিয়ে দুই ভাগ" চিন্তাটা পরে tree/bracket DP-তে বারবার ফিরবে — Catalan তার প্রথম আভাস।

11. Step-by-step dry run

চলো catalan_dp(3) চালাই (cat[0]=1 থেকে শুরু):

k	হিসাব (Σ cat[i]·cat[k−1−i])	cat[k]
0	— (শুরু)	1
1	cat[0]·cat[0] = 1·1	1
2	cat[0]·cat[1] + cat[1]·cat[0] = 1+1	2
3	cat[0]·cat[2] + cat[1]·cat[1] + cat[2]·cat[0] = 2+1+2	5

cat[3] = 5 ✓।

closed form দিয়ে যাচাই: C(6,3)/4 = 20/4 = 5 ✓। হাতে bracket-ও 5টা — তিন পথ মিলল।

12. Python solution

from math import comb


def catalan(n):
    """n-তম Catalan number (closed form): C(2n, n) / (n+1)।"""
    return comb(2 * n, n) // (n + 1)


def catalan_dp(n):
    """একই সংখ্যা DP recurrence-এ: Cat(k) = Σ Cat(i)·Cat(k−1−i)।"""
    cat = [0] * (n + 1)
    cat[0] = 1
    for k in range(1, n + 1):
        cat[k] = sum(cat[i] * cat[k - 1 - i] for i in range(k))
    return cat[n]


# --- brute force verifier (সব bracket-সারি বানিয়ে valid গোনা) ---
from itertools import product


def is_balanced(s):
    bal = 0
    for ch in s:
        bal += 1 if ch == '(' else -1
        if bal < 0:
            return False
    return bal == 0


def catalan_brute(n):
    if n == 0:
        return 1
    count = 0
    for combo in product('()', repeat=2 * n):
        if is_balanced(''.join(combo)):
            count += 1
    return count


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

# জানা মান
known = [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
for n, val in enumerate(known):
    assert catalan(n) == val
    assert catalan_dp(n) == val

# closed form == DP (0..15 জুড়ে)
for n in range(0, 16):
    assert catalan(n) == catalan_dp(n)

# closed form == brute force enumeration (ছোট n, 0..8)
for n in range(0, 9):
    assert catalan(n) == catalan_brute(n)

# Cat(n) = C(2n,n) − C(2n,n+1) (বিকল্প রূপও মেলে)
for n in range(0, 12):
    assert catalan(n) == comb(2 * n, n) - comb(2 * n, n + 1)

print(catalan(3))       # 5
print(catalan(5))       # 42
print(catalan_dp(4))    # 14
print("সব test pass!")

13. Line-by-line explanation

def catalan(n):
    return comb(2 * n, n) // (n + 1)

closed form — C(2n, n) গুনে (n+1) দিয়ে ভাগ। এই ভাগ সবসময় নিঃশেষ, তাই // integer রাখে।

def catalan_dp(n):
    cat = [0] * (n + 1)
    cat[0] = 1
    for k in range(1, n + 1):
        cat[k] = sum(cat[i] * cat[k - 1 - i] for i in range(k))

DP — cat[0]=1 থেকে শুরু; প্রতিটা cat[k] আগের সব মান থেকে recurrence দিয়ে (ভেতরে i জোড়া × বাইরে k−1−i জোড়া, সব i-তে যোগ)।

def is_balanced(s):
    bal = 0
    for ch in s:
        bal += 1 if ch == '(' else -1
        if bal < 0: return False
    return bal == 0

verify-র জন্য — ( হলে +1, ) হলে −1; কখনো negative হলে invalid () বেশি), শেষে 0 হলে valid।

বাকি assert লাইনগুলো জানা মান, closed form vs DP, brute enumeration আর বিকল্প রূপ — চার দিক থেকে যাচাই করছে। সব মিললে শেষে সব test pass!।

14. Output walkthrough

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

5
42
14
সব test pass!

প্রথম: catalan(3) = 5। দ্বিতীয়: catalan(5) = 42। তৃতীয়: catalan_dp(4) = 14। আগের সব assert (জানা মান, closed form = DP = brute = বিকল্প রূপ — চার দিক cross-check) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity

closed form catalan(n) O(n) — একটা C(2n, n) হিসাব (n টা গুণ-ভাগ)। DP catalan_dp(n) O(n²) — প্রতিটা cat[k]-এ k টা পদ যোগ। brute O(4ⁿ · n) — exponential। closed form-ই দ্রুততম।

16. Space complexity

closed form O(1)। DP O(n) — পুরো cat array। brute O(n) — একটা সারি বানাতে।

17. Common mistakes

1. (n+1) দিয়ে ভাগ ভুলে যাওয়া — C(2n, n)-ই Catalan নয়; /(n+1) লাগবেই।
2. Cat(0) ভুল ভাবা — Cat(0) = 1 (খালি, ঠিক একভাবে), 0 নয়।
3. Recurrence-এ index উল্টানো — Cat(i)·Cat(n−1−i), যোগফল i=0..n−1; সীমা ভুল হলে ধারা নষ্ট।
4. brute force বড় n-এ চালানো — 4ⁿ, n≈15-এই অচল; formula বা DP নাও।
5. সব counting-কে Catalan ভাবা — শুধু "কখনো-নিয়ম-ভাঙবে-না / balanced / recursively দুই ভাগ" চরিত্রেই Catalan; সাধারণ বাছাই combination।

18. Harder problems that inherit this idea

• LeetCode — Unique Binary Search Trees (https://leetcode.com/problems/unique-binary-search-trees/) — n node-এর BST-সংখ্যা = Cat(n); হুবহু এই recurrence।
• LeetCode — Generate Parentheses (https://leetcode.com/problems/generate-parentheses/) — balanced bracket সত্যিই বানানো (backtracking), মোট সংখ্যা Cat(n)।
• LeetCode — Different Ways to Add Parentheses (https://leetcode.com/problems/different-ways-to-add-parentheses/) — "প্রথম বিভাজন বিন্দু" দিয়ে ভাগ, Catalan-ধাঁচের DP।

19. Pattern learned

Catalan number (balanced / never-violate structures) — Cat(n) = C(2n,n)/(n+1); recurrence Σ Cat(i)·Cat(n−1−i) "প্রথম মেলানো জোড়া দিয়ে দুই ভাগ"। মূল signal: "balanced bracket / BST গোনা / কখনো নিচে নামবে না এমন path" দেখলেই Catalan (1,1,2,5,14,...)।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Catalan: 1,1,2,5,14,...; Cat(n)=C(2n,n)/(n+1) বা Σ Cat(i)·Cat(n−1−i)। balanced bracket / BST / never-dip path দেখলেই এটা — 'প্রথম মেলানো জোড়া দিয়ে দুই ভাগ'।"

পরের ধাপ → 050 — Derangement Intro (কেউই নিজের জিনিস ফেরত পাবে না — !n recurrence)।

ফিরে দেখা: আগের ধাপ → 048 — Count Paths in Grid · এই 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"।