042 — nCr using Pascal Triangle¶

nCr তো শিখেছ গুণ-ভাগ দিয়ে। এবার একই nCr-কে দেখব সম্পূর্ণ অন্য চোখে — কোনো ভাগ ছাড়াই, শুধু যোগ দিয়ে। এটাই Pascal triangle, আর গোপন খবর: এটাই তোমার প্রথম dynamic programming! বড় উত্তর ছোট উত্তরদের যোগ করে বানানো, টেবিলে জমিয়ে রাখা — DP-র পুরো দর্শন এই একটা ত্রিভুজে। ছবিটা একবার এঁকে ফেললে আর ভুলবে না।

Source¶

Original source: LeetCode Pascal's Triangle
Platform: LeetCode — https://leetcode.com/problems/pascals-triangle/
Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
Difficulty: Medium
Pattern: DP-style build (Pascal's rule / additive nCr)
Basic idea inherited from: 041 — Combination Basic (একই nCr, ভিন্ন পথ)

1. Problem in simple words¶

দুটো জিনিস চাই:

Pascal's triangle-এর প্রথম কয়েকটা সারি বানানো। এটা এমন একটা ত্রিভুজ যেখানে প্রতিটা ঘর হলো তার ঠিক উপরের দুই ঘরের যোগ, আর দুই ধার সবসময় 1।
সেই ত্রিভুজ থেকে C(n, r) পড়া — কোনো গুণ বা ভাগ ছাড়াই, শুধু যোগ করে।

মূল মজা: ত্রিভুজের n-তম সারির r-তম ঘর = ঠিক C(n, r)। মানে combination হিসাব করতে factorial-ও লাগে না, ভাগও লাগে না — শুধু যোগ।

2. What is the math idea?¶

মূল idea Pascal's rule:

C(n, r) = C(n−1, r−1) + C(n−1, r)

গল্পটা সুন্দর: n জন থেকে r জন বাছছ। শেষ জনের (ধরো রিমা) দিকে তাকাও — দুটো সম্ভাবনা:

রিমা দলে আছে → বাকি n−1 জন থেকে আরও r−1 জন বাছতে হবে → C(n−1, r−1)
রিমা দলে নেই → বাকি n−1 জন থেকেই পুরো r জন বাছতে হবে → C(n−1, r)

দুটো ক্ষেত্র আলাদা ("অথবা"), তাই যোগ। এটাই triangle-এর "উপরের দুই ঘরের যোগ" নিয়ম।

3. Which basic idea does this inherit from?¶

এটা 041 (Combination Basic)-এরই অন্য রূপ। 041-এ nCr বের করেছিলাম গুণ-ভাগ দিয়ে (n!/(r!(n−r)!))। এখানে একই nCr, কিন্তু recursive যোগের পথে।

কেন দরকার এই দ্বিতীয় পথ?

factorial বা বিশাল মাঝসংখ্যা লাগে না — শুধু ছোট ছোট যোগ
অনেক nCr একসাথে লাগলে পুরো triangle একবার বানিয়ে সব O(1)-এ পড়া যায়
এটাই DP-র হাতেখড়ি — বড় উত্তর ছোট উত্তর থেকে, table-এ জমিয়ে

আর এই additive idea পরে counting DP (coin change, path counting) — সবখানে ফিরবে।

4. Real-life analogy¶

ভাবো একটা পিন-বোর্ডে (Galton board) উপর থেকে একটা বল ফেলছ। প্রতিটা পিন-এ বল হয় বাঁয়ে যায়, নয় ডানে।

একদম উপরের ঘরে পৌঁছানোর 1 উপায় (শুরু)।
নিচের যেকোনো ঘরে পৌঁছাতে হলে বলটা তার ঠিক উপরের বাঁ-ঘর বা ডান-ঘর থেকে নামতে হবে।
তাই কোনো ঘরে পৌঁছানোর উপায়-সংখ্যা = উপরের দুই ঘরের উপায়-সংখ্যার যোগ।

এই উপায়-সংখ্যাগুলো বসালেই — হুবহু Pascal's triangle! আর n ধাপে r বার ডানে যাওয়ার উপায় = C(n, r)। তাই triangle আর "কয়টা path" একই জিনিস।

5. Visual explanation¶

প্রথমে দেখো ত্রিভুজটা কীভাবে যোগ করে বানানো হয়:

row 0:              1
row 1:            1   1
row 2:          1   2   1          (2 = 1 + 1)
row 3:        1   3   3   1        (3 = 1 + 2, আবার 3 = 2 + 1)
row 4:      1   4   6   4   1      (6 = 3 + 3)
row 5:    1   5  10  10   5   1    (10 = 4 + 6)
                  ^
        প্রতিটা ভেতরের ঘর = মাথার উপরের দুই ঘরের যোগ

এবার দেখো কোথায় কোন nCr লুকিয়ে — row n, position r:

row 5:    1    5   10   10    5    1
position: 0    1    2    3    4    5
          |    |    |    |    |    |
       C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5)
          1    5   10   10    5    1

C(5,2) = 10  <- 5-তম সারির 2-তম ঘর ✓
দুই ধার সবসময় 1 = C(n,0) = C(n,n)

লক্ষ করো — কোনো গুণ-ভাগ নেই, শুধু পাশাপাশি ঘরের যোগ। আর প্রতিটা সারি বাম-ডান প্রতিসম (symmetry)।

6. Example input and output¶

generate(5) -> পুরো triangle (প্রথম 5 সারি):
[
 [1],
 [1, 1],
 [1, 2, 1],
 [1, 3, 3, 1],
 [1, 4, 6, 4, 1]
]

nCr_pascal(n, r) -> একক মান:
   (5, 2) -> 10
   (5, 0) -> 1
   (6, 3) -> 20
   (4, 4) -> 1
   (4, 5) -> 0      (r > n -> ঘর নেই)

Edge case: দুই ধার (r = 0 আর r = n) সবসময় 1; r > n হলে ত্রিভুজে সে ঘর নেই, তাই 0।

7. Brute force thinking¶

সবচেয়ে সরাসরি — Pascal's rule সরাসরি recursion-এ লেখা:

def nCr_rec(n, r):
    if r == 0 or r == n:        # দুই ধার = 1
        return 1
    if r < 0 or r > n:
        return 0
    return nCr_rec(n - 1, r - 1) + nCr_rec(n - 1, r)

এটা সংজ্ঞার হুবহু অনুবাদ — "শেষ জন আছে নাকি নেই" দুই শাখার যোগ। ছোট n-এ একদম ঠিক উত্তর দেয়, আর গল্পটা সবচেয়ে পরিষ্কার দেখায়।

8. Why brute force may be slow¶

সমস্যা হলো এই recursion একই উপ-সমস্যা বারবার হিসাব করে। যেমন nCr_rec(5, 2) ডাকতে গিয়ে nCr_rec(3, 1) বহুবার আলাদা শাখায় ফিরে আসে:

nCr_rec(5,2) তলায় গেলে একই (3,1), (2,1) বারবার গণনা হয়

গাছটা প্রায় দ্বিগুণ হারে ফুলে ওঠে -> O(2^n) মতো
n = 30 হলেই কোটি কোটি বার call -> Time Limit Exceeded

ঠিক Fibonacci-র মতো — overlapping subproblem। এটাই DP-র দরজা: একবার হিসাব করো, জমিয়ে রাখো, আবার লাগলে পড়ে নাও।

9. Better thinking¶

মূল insight: একই উপ-সমস্যা বারবার না করে, নিচ থেকে উপরে (bottom-up) পুরো triangle একবার বানাও — প্রতিটা সারি আগের সারি থেকে:

def generate(num_rows):
    triangle = []
    for n in range(num_rows):
        row = [1] * (n + 1)             # দুই ধার আর জায়গা ভরা
        for r in range(1, n):           # ভেতরের ঘর গুলো
            row[r] = triangle[n - 1][r - 1] + triangle[n - 1][r]
        triangle.append(row)
    return triangle

প্রতিটা ভেতরের ঘর আগের সারির দুই ঘরের যোগ। একবার বানিয়ে নিলে যেকোনো C(n, r) সাথে সাথে triangle[n][r] থেকে পড়া যায় — O(1)। এটাই tabulation (DP)।

10. Thinking tweak¶

আসল "আহা" মুহূর্ত: recursion-এর গাছটাকে উল্টে দাও — নিচ থেকে উপরে টেবিল ভরো।

Recursion বড় থেকে ছোটতে নামে আর একই ছোট বারবার হিসাব করে। তার বদলে ছোট থেকে শুরু করো (row 0 = [1]), প্রতিটা নতুন সারি আগেরটা দেখে এক pass-এ বানাও। প্রতিটা উপ-উত্তর ঠিক একবার হিসাব হয়, table-এ থাকে।

এই "overlapping subproblem দেখলেই table বানাও" মোচড়টাই DP-র প্রাণ — Pascal triangle তার সবচেয়ে মিষ্টি প্রথম উদাহরণ।

11. Step-by-step dry run¶

চলো generate(4) চালাই — সারি একটা একটা করে:

n	শুরুর row	ভেতরের ঘর হিসাব	পূর্ণ row
0	[1]	—	[1]
1	[1, 1]	— (ভেতর নেই)	[1, 1]
2	[1, 1, 1]	row[1] = 1+1 = 2	[1, 2, 1]
3	[1, 1, 1, 1]	row[1]=1+2=3, row[2]=2+1=3	[1, 3, 3, 1]

শেষ ত্রিভুজ: [[1],[1,1],[1,2,1],[1,3,3,1]]।

এবার C(3, 1) পড়তে চাইলে → triangle[3][1] = 3 ✓।

12. Python solution¶

def generate(num_rows):
    """Pascal's triangle-এর প্রথম num_rows সারি বানায়।"""
    triangle = []
    for n in range(num_rows):
        row = [1] * (n + 1)
        for r in range(1, n):                       # ভেতরের ঘর
            row[r] = triangle[n - 1][r - 1] + triangle[n - 1][r]
        triangle.append(row)
    return triangle


def nCr_pascal(n, r):
    """C(n, r) — Pascal's rule দিয়ে, কোনো ভাগ ছাড়া (শুধু যোগ)।"""
    if r < 0 or r > n:
        return 0
    # n-তম সারি পর্যন্ত বানিয়ে r-তম ঘর পড়ি
    prev = [1]
    for _ in range(n):
        cur = [1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1]
        prev = cur
    return prev[r]


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

# generate ঠিক ত্রিভুজ দেয় কিনা
assert generate(1) == [[1]]
assert generate(5) == [
    [1],
    [1, 1],
    [1, 2, 1],
    [1, 3, 3, 1],
    [1, 4, 6, 4, 1],
]

# প্রতিটা ঘর = উপরের দুই ঘরের যোগ (নিজে যাচাই)
tri = generate(12)
for n in range(2, 12):
    for r in range(1, n):
        assert tri[n][r] == tri[n - 1][r - 1] + tri[n - 1][r]

# nCr_pascal == math.comb (পুরো triangle 0..12)
for n in range(0, 13):
    for r in range(0, n + 1):
        assert nCr_pascal(n, r) == math.comb(n, r)

assert nCr_pascal(5, 2) == 10
assert nCr_pascal(6, 3) == 20
assert nCr_pascal(4, 5) == 0       # r > n
assert nCr_pascal(7, 0) == 1       # ধার

# প্রতি সারির যোগফল = 2^n (বোনাস সত্য)
for n in range(0, 12):
    assert sum(tri[n]) == 2 ** n

print(generate(4))      # [[1],[1,1],[1,2,1],[1,3,3,1]]
print(nCr_pascal(5, 2)) # 10
print(nCr_pascal(6, 3)) # 20
print("সব test pass!")

13. Line-by-line explanation¶

def generate(num_rows):
    triangle = []
    for n in range(num_rows):
        row = [1] * (n + 1)

প্রতিটা নতুন সারি শুরু করি সব 1 দিয়ে (n+1 টা ঘর) — তাতে দুই ধার এমনিতেই 1 হয়ে যায়।

        for r in range(1, n):
            row[r] = triangle[n - 1][r - 1] + triangle[n - 1][r]

শুধু ভেতরের ঘরগুলো (1 থেকে n−1) আগের সারির দুই ঘরের যোগ দিয়ে ভরি। এটাই Pascal's rule।

def nCr_pascal(n, r):
    ...
    prev = [1]
    for _ in range(n):
        cur = [1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1]
        prev = cur
    return prev[r]

একক C(n, r) চাইলে পুরো ত্রিভুজ না রেখে শুধু আগের সারিটা রাখি (memory বাঁচাতে), n বার নতুন সারি বানাই, শেষে r-তম ঘর পড়ি।

বাকি assert লাইনগুলো ত্রিভুজের গঠন, math.comb-এর সাথে মিল, আর "সারির যোগ = 2ⁿ" — সব দিক যাচাই করছে। সব মিললে শেষে সব test pass!।

14. Output walkthrough¶

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

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
10
20
সব test pass!

প্রথম লাইন generate(4)-এর ত্রিভুজ। পরের দুই লাইন nCr_pascal(5,2) = 10, nCr_pascal(6,3) = 20। তার আগের সব assert (গঠন, math.comb, 2ⁿ — সব cross-check) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity¶

পুরো triangle (n সারি) বানাতে O(n²) — মোট ঘর-সংখ্যা 1+2+...+n ≈ n²/2, প্রতিটা একবার যোগ। একক nCr_pascal(n, r)-ও O(n²) (n সারি, প্রতিটা পর্যন্ত O(n) কাজ)।

(তুলনায়: 041-এর সরাসরি গুণ-ভাগ একক nCr-এ O(r) — দ্রুত। কিন্তু অনেক nCr একসাথে লাগলে একবার triangle বানিয়ে সব O(1)-এ পড়া লাভজনক।)

16. Space complexity¶

পুরো triangle রাখলে O(n²)। একটা একক C(n, r)-এর জন্য শুধু আগের সারি রাখলে O(n) (nCr_pascal-এ ঠিক তাই করেছি)।

17. Common mistakes¶

Naive recursion ব্যবহার করা — overlapping subproblem-এ O(2ⁿ); table বানাও বা memoize করো।
দুই ধার ভুলে যাওয়া — প্রতি সারির প্রথম ও শেষ ঘর সবসময় 1; না বসালে যোগ ভুল হবে।
Index গুলিয়ে ফেলা — row n-এর ঘর 0 থেকে n পর্যন্ত (n+1 টা); C(n, r) = triangle[n][r], off-by-one সাবধান।
r > n-এ crash — ত্রিভুজে সে ঘর নেই; আগে 0 ফেরত দাও।
বড় n-এ এটাই দ্রুততম ভাবা — একক nCr-এ 041-এর O(r) গুণ-ভাগ দ্রুত; Pascal লাভজনক যখন অনেক মান একসাথে চাই।

18. Harder problems that inherit this idea¶

LeetCode — Pascal's Triangle II (https://leetcode.com/problems/pascals-triangle-ii/) — শুধু একটা সারি, O(n) space-এ।
048 — Count Paths in Grid (এই repo) — path-সংখ্যা = এই additive nCr।
LeetCode — Unique Paths (https://leetcode.com/problems/unique-paths/) — grid DP, একই "উপরের দুই ঘরের যোগ"।

19. Pattern learned¶

Tabulation / additive DP (Pascal's rule) — C(n,r) = C(n−1,r−1) + C(n−1,r), বড় উত্তর ছোট উত্তরদের যোগ, table-এ জমানো। মূল signal: overlapping subproblem দেখলেই recursion-কে নিচ থেকে উপরে table-এ উল্টে দাও — এটাই DP-র প্রথম পাঠ।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Pascal: প্রতিটা ঘর = উপরের দুই ঘরের যোগ, row n ঘর r = C(n,r); ভাগ লাগে না, শুধু যোগ — আর এটাই আমার প্রথম DP (overlapping subproblem → table)।"

পরের ধাপ → 043 — Stars and Bars Basic (একই rকম জিনিস ভাগ করার ছবি — bar বসানোর কৌশল)।

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