গণনার কৌশল — lattice path, bijection আর double counting

১ · গ্রিডে পথ — lattice path আর C(m + n, n)

কাল্পনিক অনলাইন দোকান বাজারঘরের একটি গুদাম শহরের এমন এলাকায়, যেখানে রাস্তাগুলো দাবার ছকের মতো: পূর্ব-পশ্চিমে কয়েকটি সমান্তরাল রাস্তা, উত্তর-দক্ষিণে কয়েকটি। একজন ডেলিভারি রাইডার গুদাম থেকে ৫ ব্লক পূর্বে আর ৩ ব্লক উত্তরে এক গ্রাহকের বাসায় যাবেন। সবচেয়ে ছোট পথে যেতে চাইলে তিনি কখনো পশ্চিমে বা দক্ষিণে যাবেন না; প্রতিটি মোড়ে শুধু পূর্বে (ডানে) বা উত্তরে (ওপরে)। প্রশ্ন: এমন আলাদা পথ কয়টি?

প্রমাণ (bijection দিয়ে):

1. যেকোনো পথে x-স্থানাঙ্ক 0 থেকে m-এ ওঠে, আর প্রতিটি R ধাপ এটি ঠিক 1 বাড়ায়, U ধাপ বাড়ায় না। তাই পথে ঠিক m-টি R; একই যুক্তিতে ঠিক n-টি U, মোট m + n ধাপ। — স্থানাঙ্কের হিসাব
2. প্রতিটি পথকে তার ধাপগুলোর শব্দে পাঠান: f(পথ) = R/U-এর দৈর্ঘ্য m + n-এর একটি শব্দ, যাতে m-টি R আর n-টি U. — f সুসংজ্ঞায়িত
3. উল্টো দিকে, এমন যেকোনো শব্দ (0, 0) থেকে শুরু করে অক্ষর ধরে ধরে হাঁটলে ঠিক (m, n)-এ পৌঁছায়, আর পথটি শব্দ দিয়েই পুরো ঠিক হয়। তাই f-এর একটি inverse আছে, অর্থাৎ f একটি bijection (পর্ব ১৬)। — দুই দিকে inverse
4. এমন শব্দ পুরো ঠিক হয় m + n-টি ঘরের কোন n-টিতে U বসল, তা দিয়ে; সেই বাছাই C(m + n, n) উপায়ে হয়। ∎ — combination-এর সংজ্ঞা

রাইডারের প্রশ্নে m = 5, n = 3, তাই পথ C(8, 3) = 56টি। এই প্রমাণটি একটি bijective proof: অচেনা বস্তু (পথ) গোনার বদলে আমরা একটি চেনা বস্তুর (R/U শব্দ) সঙ্গে এক-এক মিল দেখিয়েছি। পুরো পর্বে এই কৌশল বারবার ফিরবে।

দ্বিতীয় পথ: শেষ ধাপ ধরে ভাগ

N(x, y) দিয়ে (0, 0) থেকে (x, y)-এর পথের সংখ্যা বোঝান। যেকোনো পথ (x, y)-তে পৌঁছায় হয় বাঁ দিকের (x − 1, y) থেকে একটি R দিয়ে, নয়তো নিচের (x, y − 1) থেকে একটি U দিয়ে, আর এই দুই দল পরস্পর বিচ্ছিন্ন। যোগের নিয়মে (পর্ব ৩১ “গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ”):

N(x, y) = N(x − 1, y) + N(x, y − 1), N(x, 0) = N(0, y) = 1

এটি আসলে Pascal-এর identity C(m + n, n) = C(m + n − 1, n) + C(m + n − 1, n − 1), শুধু গ্রিডে আঁকা (পর্ব ৩৪ “Binomial coefficient, Pascal-এর ত্রিভুজ আর combinatorial identity”-এ বিস্তারিত)। প্রোগ্রামিংয়ে এটিই গ্রিড-পথের dynamic programming, যার কোড আর জটিলতা DSA কোর্সের পর্ব ৫২-এ আছে। সূত্রের সুবিধা হলো এক লাইনে উত্তর; DP-র সুবিধা হলো বাধা থাকলেও কাজ করে। নিচের stepper ছোট একটি গ্রিডে টেবিলটি ভরে দেখায়।

1(0,0) → (3,2): 3 R, 2 U2কিনারা: N(x,0) = N(0,y) = 13y = 1: 2, 3, 44y = 2: 3, 6, 105C(5, 2) = 10 ✓6(1,1) বন্ধ: 10 − 2·3 = 4

নিষিদ্ধ বিন্দু এড়ানো — complement আর গুণের নিয়ম

বৃষ্টিতে রাইডারের পথের (2, 1) মোড়টি জলাবদ্ধ। কয়টি ছোট পথ এই মোড় এড়ায়? সরাসরি গোনার বদলে উল্টো দিক থেকে ভাবুন: আগে মোট পথ, তারপর বাদ দিন যেগুলো (2, 1) দিয়ে যায়। এটিই complement-এর নিয়ম. (2, 1) দিয়ে যাওয়া পথ দুই খণ্ডে ভাগ হয়: (0, 0) থেকে (2, 1), তারপর (2, 1) থেকে (5, 3). দুই খণ্ড স্বাধীনভাবে বাছা যায়, তাই গুণের নিয়মে C(3, 1) × C(5, 2) = 3 × 10 = 30. এড়ানো পথ 56 − 30 = 26.

এবার Python-এ দুটি পথই মেলানো যাক: DP টেবিল (বাধার ঘরে 0) আর সূত্র। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import comb

def count_paths(m, n, blocked=()):
    """DP: N(x, y) = N(x-1, y) + N(x, y-1); a blocked point gets 0"""
    N = {}
    for x in range(m + 1):
        for y in range(n + 1):
            if (x, y) in blocked:
                N[x, y] = 0
            elif x == 0 and y == 0:
                N[x, y] = 1
            else:
                N[x, y] = N.get((x - 1, y), 0) + N.get((x, y - 1), 0)
    return N

N = count_paths(3, 2)
for y in (2, 1, 0):                       # top row first, like the grid
    print("y =", y, ":", [N[x, y] for x in range(4)])
print("paths to (3, 2):", N[3, 2], "  C(5, 2) =", comb(5, 2))

# 5 blocks east, 3 north; the crossing (2, 1) is flooded
total = comb(8, 3)
through = comb(3, 1) * comb(5, 2)         # (0,0)->(2,1), then (2,1)->(5,3)
dp = count_paths(5, 3, blocked={(2, 1)})[5, 3]
print("total:", total, "  through (2, 1):", through)
print("avoid by formula:", total - through, "  avoid by DP:", dp)

print("C(m+n, n) correct for every grid up to 8 x 8:",
      all(count_paths(m, n)[m, n] == comb(m + n, n)
          for m in range(9) for n in range(9)))

y = 2 : [1, 3, 6, 10]
y = 1 : [1, 2, 3, 4]
y = 0 : [1, 1, 1, 1]
paths to (3, 2): 10   C(5, 2) = 10
total: 56   through (2, 1): 30
avoid by formula: 26   avoid by DP: 26
C(m+n, n) correct for every grid up to 8 x 8: True

২ · Reflection principle — খারাপ পথকে আয়নায় দেখা

এবার একটি কঠিন শর্ত। বাজারঘরের একটি ভ্যানে পার্সেল ওঠে আর নামে; ধরুন দিনে n-টি পার্সেল ওঠে আর n-টি নামে, আর নামানোর আগে সেটি উঠতে হবে, তাই কোনো মুহূর্তেই নামানো পার্সেলের সংখ্যা ওঠানোর চেয়ে বেশি হতে পারে না। ওঠা = R, নামা = U ধরলে প্রতিটি দিনের হিসাব (0, 0) থেকে (n, n)-এর একটি পথ, যা কখনো কর্ণ y = x-এর ওপরে যায় না (y ≤ x সবসময়)। এমন পথকে বলে Dyck path. কয়টি?

সব পথ C(2n, n)টি; সমস্যা হলো “খারাপ” পথগুলো গোনা, যারা কোনো এক সময় কর্ণের ওপরে ওঠে। খেয়াল করুন, কর্ণের ওপরে ওঠা মানে কোনো বিন্দুতে y = x + 1 রেখাটি ছোঁয়া, কারণ প্রতিটি ধাপে y − x ঠিক 1 বদলায়। খারাপ পথ সরাসরি গোনা কঠিন; কিন্তু তাদের একটি আয়নায় দেখলে ছবিটি হঠাৎ সহজ হয়ে যায়। এই কৌশলের নাম reflection principle.

প্রমাণ: খারাপ পথ P-তে প্রথম যে বিন্দুতে y = x + 1 ছোঁয়া হয়, তাকে T বলুন। φ(P) সংজ্ঞায়িত করুন: T পর্যন্ত পথ যেমন আছে তেমন, আর T-এর পরের প্রতিটি ধাপে R আর U অদলবদল।

1. T-এর পরে P-তে বাকি ছিল কিছু R আর কিছু U, যা T = (t, t + 1) থেকে (n, n)-এ পৌঁছায়: n − t-টি R আর n − t − 1টি U. অদলবদলের পর সেখানে n − t − 1টি R আর n − t-টি U, তাই নতুন পথ শেষ হয় (t + n − t − 1, t + 1 + n − t) = (n − 1, n + 1)-এ। — ধাপ গোনা
2. জ্যামিতিতে এটি T-এর পরের অংশকে রেখা y = x + 1-এর সাপেক্ষে প্রতিফলন; বিন্দু (n, n)-এর প্রতিফলন (n − 1, n + 1). — প্রতিফলন (x, y) ↦ (y − 1, x + 1)
3. উল্টো দিকে, (0, 0) থেকে (n − 1, n + 1)-এর যেকোনো পথ Q শুরু করে রেখার নিচে (0 − 0 = 0 < 1) আর শেষ করে রেখার ওপরে (n + 1 − (n − 1) = 2 > 1); প্রতিটি ধাপে y − x ঠিক 1 বদলায়, তাই Q অবশ্যই কোথাও y − x = 1 ছোঁয়। প্রথম ছোঁয়ার পরে আবার R আর U অদলবদল করলে (n, n)-এর একটি খারাপ পথ পাওয়া যায়। — বিচ্ছিন্ন মধ্যবর্তী মান
4. অদলবদল দুবার করলে পথ ফিরে আসে, আর প্রথম ছোঁয়ার বিন্দু T বদলায় না (T-এর আগের অংশ ছোঁয়া হয়নি)। তাই দুই ফাংশন পরস্পরের inverse, অর্থাৎ φ একটি bijection. — পর্ব ১৬
5. (n − 1, n + 1)-এর পথ উপপাদ্য ১.২ অনুযায়ী C(2n, n + 1) = C(2n, n − 1)টি। ∎ — উপপাদ্য ১.২

প্রমাণ: n = 0-তে একটিই (খালি) পথ, আর C(0, 0)/1 = 1. n ≥ 1 হলে:

1. সব পথ C(2n, n)টি, আর প্রতিটি পথ হয় ভালো, নয়তো খারাপ (y = x + 1 ছোঁয়)। — উপপাদ্য ১.২, complement
2. লেমা ২.১ অনুযায়ী খারাপ পথ C(2n, n + 1)টি, তাই ভালো পথ C(2n, n) − C(2n, n + 1). — বিয়োগ
3. C(2n, n + 1) = (2n)! / ((n + 1)! (n − 1)!) = C(2n, n) · n/(n + 1). — factorial সাজানো
4. তাই C_n = C(2n, n) (1 − n/(n + 1)) = C(2n, n)/(n + 1). ∎ — বীজগণিত

নামটি এসেছে বেলজিয়ান গণিতবিদ Eugène Catalan-এর নামে, যিনি ১৮৩৮ সালের দিকে বন্ধনী বসানোর উপায় নিয়ে লেখেন; তবে সংখ্যাগুলো তার আগেই Euler-এর হাতে (বহুভুজের triangulation, আনুমানিক ১৭৫১) এসেছিল, আর ভাবনার প্রশ্নে এর ইতিহাস আছে। Catalan সংখ্যার recurrence, generating function আর আরও প্রয়োগ পর্ব ৫০ “বিশেষ সংখ্যা — Catalan, Stirling আর partition”-এ আসবে; এখানে মূল কথা হলো প্রমাণটি সম্পূর্ণ গণনামূলক। নিচের stepper n = 3-এ প্রতিফলনটি ধাপে ধাপে দেখায়।

1পথ: R U U R U R → (3,3)2(1,0) (1,1) (1,2) ← ছোঁয়া3বাকি R U R → U R U4নতুন: R U U U R U → (2,4)5উল্টো: আবার অদলবদল620 − 15 = 5 = C₃

Ballot problem — সবসময় এগিয়ে থাকা

একটি নির্বাচনে প্রার্থী A পেয়েছেন a ভোট, B পেয়েছেন b ভোট, a > b. ভোটগুলো একটি একটি করে গোনা হয়। কতগুলো গোনার ক্রমে A প্রতিটি ভোটের পর কঠোরভাবে এগিয়ে থাকেন? এই প্রশ্নের নাম ballot problem.

প্রমাণ: A = R, B = U ধরুন; সারিটি (0, 0) থেকে (a, b)-এর পথ, আর “A এগিয়ে” মানে প্রতিটি বিন্দুতে x > y.

1. প্রথম ভোটটি A-এর হতেই হবে, তাই ভালো পথগুলো (1, 0) থেকে (a, b)-এর এমন পথ, যারা কখনো y = x রেখা ছোঁয় না। (1, 0) থেকে সব পথ C(a + b − 1, b)টি। — উপপাদ্য ১.২
2. (1, 0) থেকে যে পথ y = x ছোঁয়, তার প্রথম ছোঁয়ার আগের অংশ y = x-এর সাপেক্ষে প্রতিফলিত করুন (R ↔ U অদলবদল)। এতে শুরু হয় (0, 1) থেকে, আর এভাবে এমন পথগুলো (0, 1) থেকে (a, b)-এর সব পথের সঙ্গে এক-এক মেলে। — প্রতিফলন
3. (0, 1) থেকে (a, b)-এর প্রতিটি পথ অবশ্যই y = x ছোঁয়, কারণ শুরুতে y > x আর শেষে x > y; এদের সংখ্যা C(a + b − 1, b − 1). — মধ্যবর্তী মান, উপপাদ্য ১.২
4. বিয়োগ করে প্রথম রূপ; বীজগণিতে সরল করলে ((a − b)/(a + b)) · C(a + b, a). ∎ — complement

উদাহরণ: a = 5, b = 3 হলে C(7, 3) − C(7, 2) = 35 − 21 = 14, আর সূত্রে (2/8) · 56 = 14. খেয়াল করুন, a = n + 1, b = n বসালে উত্তর C_n হয়: ballot আর Catalan একই পরিবারের সদস্য। নিচের ব্লক n = 4-এ প্রতিফলনটি সব খারাপ পথে চালিয়ে দেখে, আর ballot-এর ক্রমগুলো সরাসরি গোনে।

from itertools import combinations
from math import comb

def walk(steps):                  # R = one step right, U = one step up
    x, y, pts = 0, 0, []
    for s in steps:
        x, y = (x + 1, y) if s == "R" else (x, y + 1)
        pts.append((x, y))
    return pts

def reflect(steps):               # swap R and U after the first touch of y = x + 1
    for i, (x, y) in enumerate(walk(steps)):
        if y == x + 1:
            tail = "".join("U" if s == "R" else "R" for s in steps[i + 1:])
            return steps[:i + 1] + tail
    return None                   # a good path never touches the line

n = 4
paths = ["".join("U" if i in ups else "R" for i in range(2 * n))
         for ups in combinations(range(2 * n), n)]
bad = [p for p in paths if reflect(p) is not None]
images = {reflect(p) for p in bad}
print("all:", len(paths), " good:", len(paths) - len(bad), " bad:", len(bad))
print("distinct images:", len(images), " all end at (3, 5):",
      all(walk(q)[-1] == (n - 1, n + 1) for q in images))
print("C(8, 3) =", comb(8, 3), "  C(8, 4)/5 =", comb(8, 4) // 5)
print("example:", "RUURRUUR", "->", reflect("RUURRUUR"))
a, b = 5, 3                       # ballot: A must lead after every vote
seqs = ["".join("B" if i in bs else "A" for i in range(a + b))
        for bs in combinations(range(a + b), b)]
lead = [s for s in seqs if all(s[:k].count("A") > s[:k].count("B")
                               for k in range(1, a + b + 1))]
print("ballot:", len(lead), "of", len(seqs),
      "  formula:", (a - b) * comb(a + b, a) // (a + b))

all: 70  good: 14  bad: 56
distinct images: 56  all end at (3, 5): True
C(8, 3) = 56   C(8, 4)/5 = 14
example: RUURRUUR -> RUUUURRU
ballot: 14 of 56   formula: 14

৩ · কম্পিউটার বিজ্ঞানে Catalan — বন্ধনী, binary tree আর triangulation

Catalan সংখ্যার আসল জাদু হলো এটি একেবারে আলাদা চেহারার অনেক প্রশ্নের উত্তর। n = 3-এ পাঁচটি করে বস্তু নিচের সারণিতে; প্রতিটি সারিতে সংখ্যা 5 = C₃. আর এই মিলগুলো কাকতালীয় নয়: প্রতিটির পেছনে একটি bijection আছে।

বন্ধনী: “(” = R আর “)” = U পড়লে একটি বন্ধনী-সারি মেলানো হয় ঠিক তখন, যখন কোনো শুরুর অংশে “)” বেশি নেই, আর শেষে সমান সমান; এটি হুবহু Dyck path-এর শর্ত। পর্ব ১২-এ balanced parentheses-এর recursive সংজ্ঞা থেকে দৈর্ঘ্য 0, 2, 4, 6, 8-এ 1, 1, 2, 5, 14টি সারি পাওয়া গিয়েছিল; এখন তার সূত্র আর প্রমাণ দুটোই আপনার হাতে।

Catalan recurrence: একটি মেলানো সারি (n + 1 জোড়া) সবসময় “(” দিয়ে শুরু হয়; তার জোড়া “)” কোথায়, তা দিয়ে সারিটি অনন্যভাবে ভাঙে: ( A ) B, যেখানে A-তে i জোড়া আর B-তে n − i জোড়া, দুটিই মেলানো। i = 0, …, n-এর জন্য দুই অংশ স্বাধীন, তাই যোগ আর গুণের নিয়মে

C_n+1 = C₀C_n + C₁C_n−1 + … + C_nC₀, C₀ = 1

যেমন C₃ = C₀C₂ + C₁C₁ + C₂C₀ = 2 + 1 + 2 = 5. এই recurrence-এর পূর্ণ প্রমাণ অনুশীলনের প্রথম প্রশ্ন।

Binary tree: n node-এর একটি binary tree-এ root বাদে বাকি n − 1টি node বাঁ subtree-তে i-টি আর ডান subtree-তে n − 1 − i-টি ভাগ হয়; গোনাটি একই recurrence মানে, তাই সংখ্যা C_n. বন্ধনীর সঙ্গে সরাসরি মিল: tree T-কে লিখুন “( বাঁ subtree-র সারি ) ডান subtree-র সারি”. DSA কোর্সের পর্ব ২৬ আর পর্ব ২৭-এ এই সংখ্যাই আসে n চাবির সম্ভাব্য BST-এর আকার হিসেবে।

Triangulation: উত্তল (n + 2)-ভুজকে পরস্পর না কাটা কর্ণ দিয়ে ত্রিভুজে ভাগ করার উপায়কে বলে triangulation. একটি নির্দিষ্ট বাহু ধরুন; সেটি ঠিক একটি ত্রিভুজে থাকে, আর সেই ত্রিভুজের তৃতীয় শীর্ষবিন্দু বহুভুজটিকে দুটি ছোট বহুভুজে ভাগ করে। আবার একই recurrence. তাই ষড়ভুজে (n = 4) triangulation 14টি। Matrix chain multiplication-এ n-টি matrix-এর বন্ধনী বসানোর উপায়ও C_n−1, যার কারণে সব উপায় চেষ্টা করা অসম্ভব আর DP লাগে (DSA কোর্সের পর্ব ৫৪)।

৪ · Bijective proof — subset, bit string আর composition

এ পর্যন্ত তিনবার একই কৌশল দেখলেন: পথ ↔ R/U শব্দ, খারাপ পথ ↔ অন্য বিন্দুর পথ, বন্ধনী ↔ Dyck path. মূল নীতিটি সহজ: দুটি সসীম সেটের মধ্যে একটি bijection থাকলে তাদের আকার সমান। এর শক্তি হলো, কঠিন সেটটি গোনার দরকারই পড়ে না।

Subset ↔ bit string

S = {1, 2, …, n}-এর প্রতিটি subset A-কে একটি n-দৈর্ঘ্যের bit string-এ পাঠান: i-তম bit 1 যদি i ∈ A, নইলে 0. যেমন n = 4-এ {1, 3} ↦ 1010. উল্টো দিকে প্রতিটি bit string একটি subset ঠিক করে, তাই এটি bijection, আর bit string 2ⁿটি বলে subset-ও 2ⁿটি। এটি পর্ব ১৪-এর |P(S)| = 2ⁿ-এর আরেকটি প্রমাণ, আর প্রোগ্রামিংয়ে bitmask দিয়ে subset ঘোরানোর ভিত্তি।

Composition গোনা

n-এর একটি composition হলো ধনাত্মক পূর্ণসংখ্যার একটি ক্রমসহ তালিকা, যার যোগফল n. যেমন 4-এর composition: 4, 3 + 1, 1 + 3, 2 + 2, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1, মোট ৮টি। বাজারঘরের ভাষায়: ৪ দিনের একটি ডেলিভারি সূচি কয়টি ধাপে ভাগ করা যায়, যেখানে প্রতিটি ধাপ অন্তত এক দিনের আর ধাপগুলোর ক্রম গুরুত্বপূর্ণ।

প্রমাণ (bijection দিয়ে): n-টি তারা এক সারিতে রাখুন: ★ ★ ★ ★. পরপর দুই তারার মাঝে n − 1টি ফাঁক, যাদের নাম দিন 1, 2, …, n − 1.

1. f: ফাঁকের যেকোনো subset K ⊆ {1, …, n − 1} নিন, আর K-এর প্রতিটি ফাঁকে একটি দেয়াল বসান। দেয়ালগুলো সারিটিকে |K| + 1টি খণ্ডে ভাগ করে, প্রতিটিতে অন্তত একটি তারা (দুই দেয়াল একই ফাঁকে বসে না)। খণ্ডগুলোর তারার সংখ্যা বাঁ থেকে ডানে একটি composition. — f সুসংজ্ঞায়িত
2. g: composition (c₁, …, c_k)-এর চলমান যোগফল c₁, c₁ + c₂, …, c₁ + … + c_k−1 নিন; এরা {1, …, n − 1}-এর k − 1টি আলাদা সংখ্যা, কারণ প্রতিটি cᵢ ≥ 1. — g সুসংজ্ঞায়িত
3. দেয়ালের অবস্থান ঠিক চলমান যোগফল, তাই g(f(K)) = K আর f(g(c)) = c; f একটি bijection. — দুই দিকে inverse
4. {1, …, n − 1}-এর subset 2ⁿ⁻¹টি, আর k − 1 আকারের subset C(n − 1, k − 1)টি। ∎ — পর্ব ১৪, combination

দ্বিতীয় অংশটি পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই — stars and bars আর multinomial”-এর x₁ + … + x_k = n, xᵢ ≥ 1-এর C(n − 1, k − 1)টি সমাধান; সেখানে যে bijective প্রমাণের প্রতিশ্রুতি ছিল, এটিই সেই প্রমাণ। নিচের ব্লক n = 4-এর সব ৮টি মিল ছাপে, আর n = 12 পর্যন্ত bijection-টি পরীক্ষা করে।

from itertools import combinations

def comp_from_cuts(n, cuts):
    """cut the row of n stars after each position in cuts (a subset of 1..n-1)"""
    parts, last = [], 0
    for c in sorted(cuts) + [n]:
        parts.append(c - last)
        last = c
    return parts

def cuts_from_comp(parts):        # inverse: the running sums, except the last
    sums, s = set(), 0
    for p in parts[:-1]:
        s += p
        sums.add(s)
    return sums

n = 4
for k in range(n):
    for cuts in combinations(range(1, n), k):
        bits = "".join("1" if i in cuts else "0" for i in range(1, n))
        parts = comp_from_cuts(n, list(cuts))
        print(bits, set(cuts) or "{}", "->", " + ".join(map(str, parts)))

ok = True
for n in range(1, 13):
    seen = set()
    for k in range(n):
        for cuts in combinations(range(1, n), k):
            parts = comp_from_cuts(n, list(cuts))
            ok = ok and sum(parts) == n and cuts_from_comp(parts) == set(cuts)
            seen.add(tuple(parts))
    ok = ok and len(seen) == 2 ** (n - 1)
print("bijection and 2^(n-1) compositions for n = 1..12:", ok)

000 {} -> 4
100 {1} -> 1 + 3
010 {2} -> 2 + 2
001 {3} -> 3 + 1
110 {1, 2} -> 1 + 1 + 2
101 {1, 3} -> 1 + 2 + 1
011 {2, 3} -> 2 + 1 + 1
111 {1, 2, 3} -> 1 + 1 + 1 + 1
bijection and 2^(n-1) compositions for n = 1..12: True

৫ · Double counting — একই জিনিস দুইভাবে গোনা

পরীক্ষার হলে শিক্ষক উপস্থিতি মেলান দুইভাবে: প্রতিটি বেঞ্চে কয়জন বসেছে যোগ করে, আর প্রতিটি সারির খাতায় কয়টি সই আছে যোগ করে। দুই যোগফল একই হতেই হবে, কারণ দুটিই একই মানুষদের গোনে। এই সাধারণ বুদ্ধিই double counting: একটি সেটকে দুইভাবে গুনুন, তারপর দুই রাশি সমান বসান। প্রায়ই এক দিকের রাশিটি জানা, আর অন্য দিকে একটি নতুন সমতা বা অসম্ভবতার প্রমাণ বেরিয়ে আসে।

প্রমাণ:

1. একটি টেবিল আঁকুন যার সারি A-এর উপাদান, কলাম B-এর; (a, b) ∈ R হলে ঘরে 1, নইলে 0. এটিকে বলে incidence matrix. টেবিলের সব 1-এর সংখ্যা |R|. — সংজ্ঞা
2. সারি ধরে যোগ: a-এর সারিতে 1 আছে r(a)টি, আর সারিগুলো R-কে পরস্পর বিচ্ছিন্ন অংশে ভাগ করে; তাই সব সারির যোগ |R|. — যোগের নিয়ম
3. কলাম ধরে যোগেও একই যুক্তি: সব কলামের যোগ |R|. দুটি সমান বসালে উপপাদ্য। ∎ — যোগের নিয়ম

1      ঢাকা খুলনা রাজশাহী2R1     1    1     0   │ 23R2     0    1     1   │ 24R3     1    1     1   │ 35R4     1    0     0   │ 16       3    3     2

প্রয়োগ ১: Handshake — degree-র যোগফল জোড়

একটি অনুষ্ঠানে কয়েকজন মানুষ কয়েকবার করমর্দন করলেন। প্রত্যেকে কয়বার করমর্দন করেছেন, তার যোগফল সবসময় জোড়, কারণ প্রতিটি করমর্দনে ঠিক দুজন থাকেন। টেবিলের ভাষায়: সারি = মানুষ, কলাম = করমর্দন, প্রতিটি কলামে ঠিক দুটি 1. কলাম ধরে যোগ = 2 × (করমর্দনের সংখ্যা), সারি ধরে যোগ = প্রত্যেকের সংখ্যার যোগফল। গ্রাফের ভাষায় এটি handshake lemma: সব vertex-এর degree-র যোগফল = 2|E|, ফলে বিজোড় degree-র vertex সবসময় জোড় সংখ্যক। গ্রাফ নিয়ে পূর্ণ আলোচনা পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”-এ; এখানে লক্ষ করুন, প্রমাণটি পুরোপুরি double counting.

একটি তাৎক্ষণিক ফল: ৯ জনের একটি দলে প্রত্যেকে ঠিক ৫ জনের সঙ্গে করমর্দন করবেন, এমন ব্যবস্থা অসম্ভব, কারণ যোগফল 9 × 5 = 45 বিজোড়। আর ১০ জনের প্রত্যেকে বাকি সবার সঙ্গে একবার করে করমর্দন করলে সারি ধরে 10 × 9 = 90, তাই করমর্দন 90/2 = 45 = C(10, 2).

প্রয়োগ ২: অধিনায়কসহ দল — k · C(n, k) = n · C(n − 1, k − 1)

n জন খেলোয়াড় থেকে k জনের একটি দল বানাবেন, আর দলের ভেতর থেকে একজন অধিনায়ক। (দল, অধিনায়ক) জোড়া দুইভাবে গোনা যায়।

1. আগে দল, তারপর অধিনায়ক: দল C(n, k) উপায়ে, প্রতিটি দলে অধিনায়ক k উপায়ে; গুণের নিয়মে k · C(n, k). — প্রথম গোনা
2. আগে অধিনায়ক, তারপর বাকি দল: অধিনায়ক n উপায়ে, বাকি n − 1 জন থেকে k − 1 জন C(n − 1, k − 1) উপায়ে; মোট n · C(n − 1, k − 1). — দ্বিতীয় গোনা
3. দুটিই একই সেটের আকার, তাই সমান। ∎ — double counting

উদাহরণ: ৬ জন থেকে ৪ জনের দল, অধিনায়কসহ: 4 × 15 = 60 আর 6 × 10 = 60. বীজগণিতে factorial খুলেও প্রমাণ করা যায়, কিন্তু double counting প্রমাণটি বলে কেন সমতাটি সত্য। এই সমতা k দিয়ে যোগ করলে পর্ব ৩৪-এর ∑ k · C(n, k) = n · 2ⁿ⁻¹ আসে। এ ধরনের যুক্তিকে সাধারণভাবে বলে combinatorial proof.

৬ · Complement, ক্ষেত্রভাগ আর recurrence দিয়ে গোনা

বাজারঘর ডেলিভারির সময়সূচি bit string-এ রাখে: 1 মানে সেদিন রাইডার কাজে, 0 মানে ছুটি। শ্রম-নীতি অনুযায়ী (কাল্পনিক নিয়ম) পরপর দুই দিন ছুটি দেওয়া যাবে না, অর্থাৎ string-এ “00” থাকবে না। n দিনের কতগুলো বৈধ সূচি আছে? সরাসরি সূত্র চোখে পড়ে না; কিন্তু ছোট ক্ষেত্র ভাগ করে ভাবলে একটি recurrence বেরিয়ে আসে।

প্রমাণ:

1. শুরুর মান: দৈর্ঘ্য 1-এ 0, 1 দুটিই বৈধ; দৈর্ঘ্য 2-এ 01, 10, 11 বৈধ, 00 নয়। — তালিকা
2. n ≥ 3 হলে বৈধ string-গুলোকে শেষ bit অনুযায়ী দুই পরস্পর বিচ্ছিন্ন দলে ভাগ করুন। শেষ bit 1: আগের n − 1 bit যেকোনো বৈধ string, আর শেষে 1 যোগ করলে নতুন “00” তৈরি হয় না; তাই a_n−1টি। — ক্ষেত্র ১
3. শেষ bit 0: তার আগের bit অবশ্যই 1 (নইলে শেষে “00”), তাই string-টি “…10”, আর আগের n − 2 bit যেকোনো বৈধ string; তাই a_n−2টি। — ক্ষেত্র ২
4. যোগের নিয়মে a_n = a_n−1 + a_n−2. — যোগের নিয়ম
5. F₃ = 2 = a₁, F₄ = 3 = a₂, আর দুই ধারা একই recurrence মানে; পর্ব ১১-এর strong induction-এ সব n-এ a_n = F_n+2. ∎ — strong induction

“অন্তত একবার পরপর দুই দিন ছুটি” আছে এমন string গোনার প্রশ্ন এলে সরাসরি গোনা কঠিন (কোথায় প্রথম “00”, কয়বার, ওভারল্যাপ…)। Complement-এ এক লাইনে উত্তর: 2ⁿ − a_n. এটিই “অন্তত একটি” প্রশ্নের সোনালি নিয়ম। Recurrence বানানো আর সমাধান করার পূর্ণ কৌশল পর্ব ৪৪ “Recurrence দিয়ে মডেল — Fibonacci, Hanoi আর bit string” থেকে শুরু হবে; আর পর্ব ১২-এ Fibonacci-র বৃদ্ধির হার দেখেছেন। নিচের ব্লক brute force, recurrence আর Fibonacci তিনটি কলাম পাশাপাশি রাখে।

from itertools import product

def no00(n):                       # brute force over all 2^n strings
    return sum(1 for s in product("01", repeat=n) if "00" not in "".join(s))

def split(n):                      # cases: ends in 1, or ends in 10
    good = ["".join(s) for s in product("01", repeat=n)
            if "00" not in "".join(s)]
    return (sum(s.endswith("1") for s in good),
            sum(s.endswith("10") for s in good))

a = {1: 2, 2: 3}                   # a(n) = a(n-1) + a(n-2)
for n in range(3, 13):
    a[n] = a[n - 1] + a[n - 2]
fib = [0, 1]
while len(fib) < 16:
    fib.append(fib[-1] + fib[-2])

print(" n  brute  recur  F(n+2)  with 00")
for n in range(1, 13):
    b = no00(n)
    print(f"{n:2} {b:6} {a[n]:6} {fib[n + 2]:7} {2 ** n - b:8}")
print("n = 6 split (ends 1, ends 10):", split(6), " a(5), a(4) =", a[5], a[4])

 n  brute  recur  F(n+2)  with 00
 1      2      2       2        0
 2      3      3       3        1
 3      5      5       5        3
 4      8      8       8        8
 5     13     13      13       19
 6     21     21      21       43
 7     34     34      34       94
 8     55     55      55      201
 9     89     89      89      423
10    144    144     144      880
11    233    233     233     1815
12    377    377     377     3719
n = 6 split (ends 1, ends 10): (13, 8)  a(5), a(4) = 13 8

৭ · কোন কৌশল কখন — সিদ্ধান্তের ছক আর ইন্টারভিউ ধাঁধা

গণনার প্রশ্নে সবচেয়ে কঠিন ধাপ প্রায়ই সূত্র নয়, কৌশল বাছাই। প্রশ্নের ভাষায় কিছু সংকেত থাকে; নিচের ছকটি সেগুলো এক জায়গায় আনে।

Pigeonhole-এর সারির জন্য পর্ব ৩২ দেখুন; শেষ সারিটি পর্ব ৪৯-এ আসবে। এবার কয়েকটি ইন্টারভিউ ধাঁচের ধাঁধা, প্রতিটির উত্তর scratch-এ brute force দিয়ে মেলানো।

ধাঁধা ১: ৪ × 3 গ্রিডে কয়টি আয়তক্ষেত্র?

৪ ঘর চওড়া আর ৩ ঘর উঁচু একটি গ্রিড (যেমন একটি তাক)। এর রেখা ধরে আঁকা যায় এমন সব আয়তক্ষেত্র (বর্গসহ) কয়টি? Bijection: প্রতিটি আয়তক্ষেত্র ঠিক হয় দুটি উল্লম্ব রেখা আর দুটি আনুভূমিক রেখা দিয়ে। উল্লম্ব রেখা ৫টি, আনুভূমিক ৪টি, তাই C(5, 2) × C(4, 2) = 10 × 6 = 60.

ধাঁধা ২: ১০ ধাপের সিঁড়ি, একবারে ১ বা ২ ধাপ

উপায়গুলো ১ আর ২ দিয়ে 10-এর composition. শেষ পদক্ষেপ ১ হলে বাকি 9 ধাপ, ২ হলে বাকি 8; তাই s_n = s_n−1 + s_n−2, s₀ = s₁ = 1, আর s₁₀ = F₁₁ = 89. খেয়াল করুন, এটি “00” ছাড়া string-এর মতো একই recurrence; দুটির মাঝে একটি bijection খোঁজা একটি ভালো অনুশীলন।

ধাঁধা ৩: উত্তল অষ্টভুজের কর্ণগুলো ভেতরে কয়টি বিন্দুতে কাটে?

শর্ত: কোনো তিনটি কর্ণ এক বিন্দুতে মেলে না। তখন ভেতরের প্রতিটি ছেদবিন্দু ঠিক দুটি কর্ণের, আর দুটি পরস্পর ছেদী কর্ণের চারটি প্রান্ত আলাদা শীর্ষবিন্দু। উল্টো দিকে যেকোনো ৪টি শীর্ষবিন্দু একটি উত্তল চতুর্ভুজ বানায়, যার দুই কর্ণ ঠিক একবার কাটে। Bijection: ছেদবিন্দু ↔ ৪ শীর্ষবিন্দুর সেট, তাই C(8, 4) = 70. শর্তটি জরুরি: নিয়মিত অষ্টভুজে চারটি লম্বা কর্ণ কেন্দ্রে একসঙ্গে মেলে, তাই সেখানে ছেদবিন্দু 70-এর কম। উপপাদ্যের শর্ত বাদ দিলে সূত্র ভুল হয়ে যায়, এটি তার একটি পরিষ্কার উদাহরণ।

ধাঁধা ৪: একটি ছোট দলে কি সবাই বিজোড় সংখ্যক বন্ধু রাখতে পারেন?

৭ জনের একটি দলে প্রত্যেকের বন্ধুসংখ্যা (দলের ভেতরে, বন্ধুত্ব দুই দিকে) বিজোড়, এটি সম্ভব কি? না: degree-র যোগফল হতো সাতটি বিজোড় সংখ্যার যোগ, যা বিজোড়, অথচ double counting বলে এটি 2 × (বন্ধুত্বের সংখ্যা), জোড়। কোনো উদাহরণ খোঁজার দরকারই নেই; গণনা নিজেই অসম্ভবতা প্রমাণ করে।

৮ · পরীক্ষার অঙ্ক আর গণনার একটি ভুল প্রমাণ

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় এই পর্বের ধাঁচে যে অঙ্ক আসে, তার কয়েকটি পূর্ণ সমাধান। প্রতিটি সংখ্যা scratch-এ Python দিয়ে brute force-এ মেলানো।

অঙ্ক ১: ভোট গোনা

একটি ক্লাব নির্বাচনে A পেয়েছেন ৬ ভোট, B পেয়েছেন ৪ ভোট। কতগুলো গোনার ক্রমে A প্রতিটি ভোটের পর কঠোরভাবে এগিয়ে, আর সব ক্রম সমান সম্ভাব্য হলে তার সম্ভাবনা কত?

1. সব ক্রম: ১০টি জায়গার কোন ৪টিতে B, তাই C(10, 4) = 210.
2. Ballot theorem: ((6 − 4)/(6 + 4)) · 210 = 42; বা C(9, 4) − C(9, 3) = 126 − 84 = 42.
3. সম্ভাবনা 42/210 = 1/5 = (a − b)/(a + b).

অঙ্ক ২: একটি মোড় দিয়ে যেতেই হবে, আরেকটি এড়াতে হবে

(0, 0) থেকে (6, 4)-এর কতগুলো lattice path P = (2, 1) দিয়ে যায় কিন্তু Q = (4, 2) দিয়ে যায় না?

1. P দিয়ে যাওয়া পথ: C(3, 1) × C(7, 3) = 3 × 35 = 105.
2. P আর Q দুটি দিয়েই: (0, 0) → P → Q → (6, 4) = C(3, 1) × C(3, 1) × C(4, 2) = 3 × 3 × 6 = 54. (Q থেকে P-তে যাওয়া যায় না, তাই ক্রম একটিই।)
3. উত্তর 105 − 54 = 51.

অঙ্ক ৩: Composition

10-কে ঠিক ৪টি ধনাত্মক অংশে ক্রমসহ কতভাবে লেখা যায়, আর মোট কয়টি composition আছে? উত্তর C(9, 3) = 84 আর 2⁹ = 512.

প্রমাণের ভুল ধরুন: “অর্ধেক পথ কর্ণের নিচে”

একজন লিখলেন: “দাবি: (0, 0) থেকে (n, n)-এর যে পথ কখনো কর্ণের ওপরে যায় না, তা C(2n, n)/2টি। প্রমাণ: প্রতিটি পথের R আর U অদলবদল করলে কর্ণের সাপেক্ষে তার প্রতিফলন পাওয়া যায়। এই প্রতিফলন কর্ণের নিচের পথকে ওপরের পথে নেয়, আর উল্টোটাও। তাই নিচের আর ওপরের পথ সমান সংখ্যক, প্রত্যেকে মোটের অর্ধেক। ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: প্রমাণটি ধরে নিয়েছে যে প্রতিটি পথ হয় পুরো নিচে, নয়তো পুরো ওপরে। আসলে বেশিরভাগ পথ দুই দিকেই যায়, যেমন RUUR প্রথমে কর্ণের নিচে, তারপর কর্ণের ওপরে, শেষে আবার কর্ণে ফেরে। পুরো প্রতিফলন “নিচের পথ” আর “ওপরের পথ”-কে ঠিকই মেলায়, কিন্তু এই দুই দল মিলে সব পথ হয় না; মাঝখানে বড় একটি তৃতীয় দল থেকে যায়। Counterexample: n = 3-এ দাবি বলে 20/2 = 10, কিন্তু আসল সংখ্যা 5 (stepper ২ আর Python ব্লকে যাচাই করা)। n = 1-এ দাবিটি কাকতালীয়ভাবে ঠিক (2/2 = 1), তাই শুধু সবচেয়ে ছোট ক্ষেত্রে মিলিয়ে নিশ্চিন্ত হওয়া বিপজ্জনক। ঠিক কৌশল হলো reflection principle: পুরো পথ নয়, শুধু প্রথম ছোঁয়ার পরের অংশ উল্টানো, আর রেখা y = x নয়, y = x + 1.

৯ · AI-এর যুগে — গণনার প্রমাণ আর উত্তর যাচাই

গণনার প্রশ্নে AI সহকারী প্রায়ই আত্মবিশ্বাসী আর সুন্দর একটি উত্তর দেয়, যার ভুল লুকিয়ে থাকে মডেলে বা একটি ছোট ধাপে। এই পর্বের বিষয়ে কয়েকটি ভুল নিয়মিত দেখা যায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• ছোট n-এ (0 থেকে 4) উত্তরটি brute force দিয়ে মিলিয়েছি, শুধু n = 1-এ নয়
• প্রতিটি “bijection”-এর দুই দিকের ফাংশন আর inverse নিজে পরীক্ষা করেছি
• Reflection-এ রেখাটি আর “প্রথম ছোঁয়া” ঠিক আছে কি না দেখেছি
• কোনো ভাগ বা বিয়োগ থাকলে বুঝেছি কোন ফল বাদ পড়ল আর কোনটি দুবার গোনা হলো
• প্রতিটি উপপাদ্যের শর্ত প্রশ্নে সত্যি খাটে কি না মিলিয়েছি
• উদ্ধৃত ইতিহাস, সাল বা বইয়ের নাম বিশ্বস্ত উৎসে মিলিয়েছি

গণনার প্রমাণ পরীক্ষার সবচেয়ে সস্তা উপায় হলো ছোট ক্ষেত্রে সব বস্তু তালিকা করা। AI যত সুন্দর যুক্তিই দিক, n = 3 বা 4-এ এক সেকেন্ডের brute force প্রায় প্রতিটি ভুল ধরে ফেলে; আর যেখানে মেলে না, সেখানেই প্রমাণের দুর্বল ধাপটি খুঁজুন।