Binomial coefficient, Pascal-এর ত্রিভুজ আর combinatorial identity

১ · Binomial coefficient — “n টি থেকে k টি বাছাই” আবার

বাজারঘরের মিরপুর হাবে আজ পাঁচজন ডেলিভারি রাইডার আছেন। দুপুরের ভিড়ে দুজনকে একসঙ্গে উত্তরা পাঠাতে হবে। কতভাবে দুজন বাছা যায়? এখানে ক্রম গুরুত্বহীন: “আসিফ আর বাবলু” আর “বাবলু আর আসিফ” একই দল। উত্তর 10, আর এই সংখ্যাটির নাম C(5, 2). পর্ব ৩৩ “Permutation আর combination”-এ এই সংখ্যার সূত্র এসেছে; এই পর্বে আমরা সংখ্যাগুলোর ভেতরের গঠন দেখব। দেখা যাবে, একটি সাধারণ সংখ্যার টেবিলে অসংখ্য সুন্দর সম্পর্ক লুকিয়ে আছে, আর সেগুলো প্রমাণ করার সবচেয়ে পরিষ্কার উপায় হলো “গল্প বলে গোনা”।

এখানে “সেট” শব্দটি জরুরি: subset-এ ক্রম নেই, আর একই উপাদান দুইবার নেই (পর্ব ১৪)। একই সংখ্যা আরও কয়েকভাবে দেখা যায়, আর এই বিকল্প চেহারাগুলোই পরে প্রমাণে কাজে লাগবে:

• Bit string: দৈর্ঘ্য n-এর যে bit string-এ ঠিক k টি 1 আছে, তাদের সংখ্যা C(n, k). কারণ 1-গুলোর অবস্থানের সেটটিই একটি k-subset, আর উল্টোটাও। যেমন দৈর্ঘ্য 8-এ তিনটি 1-ওয়ালা string 56টি।
• শব্দ: x আর y দিয়ে n অক্ষরের যে শব্দে ঠিক k টি y, তাদের সংখ্যা C(n, k). এটিই binomial theorem-এর চাবি।
• পথ: একটি গ্রিডে n ধাপের যে পথে ঠিক k ধাপ ওপরে আর বাকি ডানে, তাদের সংখ্যা C(n, k). এই lattice path-এর গল্প পর্ব ৩৭ “গণনার কৌশল — lattice path, bijection আর double counting”-এ বিস্তারিত।

(ক)-এর প্রমাণ পর্ব ৩৩-এ: n টি থেকে k টি ক্রমসহ সাজানোর উপায় n!/(n − k)!, আর প্রতিটি k-subset ঠিক k! রকম ক্রমে আসে, তাই ভাগ করতে হয়। এখানে factorial n! = 1 · 2 · … · n, আর 0! = 1. (খ)-এর জন্য সূত্রে n − k বসালেই চলে, কিন্তু একটি গোনার প্রমাণ আরও শিক্ষণীয়:

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

1. S একটি n-উপাদানের সেট। প্রতিটি k-subset A-কে তার পরিপূরক S − A-তে পাঠাই; S − A-তে n − k টি উপাদান।
2. এই নিয়ম one-to-one: S − A = S − B হলে A = B, কারণ দুটিই “S থেকে একই জিনিস বাদ দিলে যা থাকে”।
3. এটি onto: যেকোনো (n − k)-subset B-এর পরিপূরক S − B একটি k-subset, যার পরিপূরক B.
4. তাই k-subset আর (n − k)-subset-এর মধ্যে একটি bijection আছে (পর্ব ১৬), আর দুই সেটের আকার সমান। ∎

দৈনন্দিন ভাষায়: পাঁচজন থেকে দুজনকে উত্তরা পাঠানো মানে একই সঙ্গে তিনজনকে মিরপুরে রেখে দেওয়া। একটি বাছাই আরেকটিকে পুরোপুরি ঠিক করে দেয়। তাই C(5, 2) = C(5, 3) = 10, আর C(100, 98) হিসাব করতে C(100, 2) = 4950 নিলেই চলে।

হিসাবের কৌশল: factorial পুরোটা লাগে না

C(n, k) = n(n − 1)…(n − k + 1)/k!, অর্থাৎ ওপরে k টি ক্রমহ্রাসমান উৎপাদক, নিচে k! যেমন C(10, 4) = (10 · 9 · 8 · 7)/(4 · 3 · 2 · 1) = 5040/24 = 210. বাজারঘর ১০টি পণ্য থেকে ৪টি নিয়ে “কম্বো প্যাক” বানাতে চাইলে 210 রকম প্যাক সম্ভব। প্রোগ্রামে বড় n-এ পুরো n! হিসাব না করে এই গুণফল ধাপে ধাপে করা নিরাপদ; Python-এ math.comb(n, k) নির্ভুল int দেয়, আর C/Java-র মতো ভাষায় overflow এড়াতে প্রতি ধাপে ভাগ করার কৌশল লাগে।

২ · Combinatorial proof — একই জিনিস দুইভাবে গোনা

একটি সমতা প্রমাণের দুই রকম পথ আছে। বীজগণিতের পথে সূত্র বসিয়ে দুই পাশ সরল করে মেলাতে হয়। গোনার পথে একটি প্রশ্ন বানাতে হয় (“এই সেটে কয়টি জিনিস?”), তারপর দেখাতে হয় যে বাঁ পাশ আর ডান পাশ দুটিই সেই প্রশ্নের সঠিক উত্তর। দুটি সঠিক উত্তর সমান হতে বাধ্য।

উপপাদ্য ১.১(খ)-এর প্রমাণ ছিল দ্বিতীয় ধরনের। প্রথম ধরনের একটি ছোট উদাহরণ:

প্রমাণ (double counting):

1. প্রশ্ন: n জন রাইডার থেকে k জনের একটি দল বানিয়ে দলের ভেতর থেকে একজন দলনেতা ঠিক করার উপায় কয়টি? X হলো সব (দল, দলনেতা) জোড়ার সেট।
2. প্রথম উপায়: আগে দল (C(n, k) রকম), তারপর দলের k জনের একজন নেতা (k রকম)। গুণের নিয়মে |X| = k · C(n, k).
3. দ্বিতীয় উপায়: আগে নেতা (n রকম), তারপর বাকি n − 1 জন থেকে দলের বাকি k − 1 জন (C(n − 1, k − 1) রকম)। তাই |X| = n · C(n − 1, k − 1).
4. দুই উপায় একই সেট X গোনে, প্রতিটি জোড়া ঠিক একবার; তাই দুই রাশি সমান। ∎

যাচাই n = 5, k = 2: বাঁ পাশ 2 · 10 = 20, ডান পাশ 5 · C(4, 1) = 20. গুণ আর যোগের নিয়ম পর্ব ৩১ “গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ”-এ আসে; এখানে আমরা সেগুলো ব্যবহার করছি।

৩ · Pascal-এর identity আর Pascal-এর ত্রিভুজ

C(n, k)-এর মানগুলো একটি ত্রিভুজে সাজানো যায়: সারি n-এ বাঁ থেকে ডানে C(n, 0), C(n, 1), …, C(n, n). সারি 0 শুধু 1. প্রতিটি সারির দুই প্রান্তে 1, আর ভেতরের প্রতিটি সংখ্যা তার ঠিক ওপরের দুটি সংখ্যার যোগফল। এই নিয়মের পেছনের উপপাদ্যটি এরকম:

প্রমাণ (combinatorial):

1. S একটি n-উপাদানের সেট, আর a ∈ S একটি নির্দিষ্ট উপাদান। প্রশ্ন: S-এর k-subset কয়টি? উত্তর সংজ্ঞায় C(n, k).
2. প্রতিটি k-subset হয় a ধারণ করে, নয় করে না; দুটি একসঙ্গে হয় না। তাই k-subset-গুলো দুটি পৃথক দলে ভাগ হয়, আর যোগের নিয়ম খাটে।
3. a ধারণ করে এমন subset: a আগেই আছে, বাকি k − 1 টি আসে S − {a}-এর n − 1 টি উপাদান থেকে, C(n − 1, k − 1) রকম।
4. a ধারণ করে না এমন subset: k টি উপাদানই S − {a} থেকে, C(n − 1, k) রকম।
5. যোগ করে C(n, k) = C(n − 1, k − 1) + C(n − 1, k). ∎

বীজগণিতের প্রমাণও আছে: দুটি ভগ্নাংশের হর (k − 1)!(n − k)! … মিলিয়ে যোগ করলে n!/(k!(n − k)!) আসে। সেটি সঠিক, কিন্তু কেন সত্য তা বলে না। নিচের stepper-এ পাঁচজন রাইডার A, B, C, D, E নিয়ে গোনার প্রমাণটি দেখুন; A হলো আসিফ, আমাদের “নির্দিষ্ট উপাদান”। “পরে” চাপুন:

1S = {A, B, C, D, E}, k = 22A আছে: AB AC AD AE3A নেই: BC BD BE CD CE DE410 = 4 + 65C(n,k)=C(n−1,k−1)+C(n−1,k)

ত্রিভুজ বানানো — একটি সারি থেকে পরের সারি

Pascal-এর identity আর দুই প্রান্তের 1 মিলে একটি recurrence: আগের সারি জানলে পরের সারি বের হয়, কোনো factorial ছাড়াই। এটি পর্ব ১২-এর recursive সংজ্ঞার মতো। সারি 0 থেকে 6 পর্যন্ত ধাপে ধাপে দেখুন:

1r = [1]2for n in range(1, 7):3  new = [1]4  for k in range(1, n):5    new.append(r[k-1]+r[k])6  r = new + [1]

এই সংখ্যার টেবিলকে বলে Pascal-এর ত্রিভুজ। এখনই কয়েকটি নকশা চোখে পড়ে: সারির যোগফল 2ⁿ; বাঁ দিকের দ্বিতীয় তির্যক 1, 2, 3, 4, …; তৃতীয় তির্যক 1, 3, 6, 10, 15, যা পর্ব ১৭-এর ত্রিভুজ সংখ্যা, কারণ C(n, 2) = n(n − 1)/2; আর সারি 0 থেকে 4 পড়লে 1, 11, 121, 1331, 14641, অর্থাৎ 11-এর ঘাত (সারি 5-এ হাতে-রাখা অঙ্কের কারণে নকশাটি ভাঙে: 11⁵ = 161051).

এবার ত্রিভুজটি সারি 30 পর্যন্ত Pascal-এর identity দিয়েই বানিয়ে math.comb-এর সঙ্গে মেলাই, আর এই পর্বের সব বড় identity একসঙ্গে পরীক্ষা করি। একটি মিথ্যা দাবিও রাখা হয়েছে: “n বিজোড় হলে সারি n-এর সব সংখ্যা বিজোড়”, যা n = 1 আর 3-এ সত্য দেখায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from math import comb

rows = [[1]]                          # row 0
for n in range(1, 31):                # Pascal's identity builds row n
    prev = rows[-1]
    rows.append([1] + [prev[k - 1] + prev[k] for k in range(1, n)] + [1])

for n in range(7):
    print(" ".join(map(str, rows[n])).center(24))

ok = dict.fromkeys(["=comb", "sum=2^n", "alt=0", "k*C=n*2^(n-1)",
                    "squares=C(2n,n)", "hockey", "vandermonde"], True)
for n, row in enumerate(rows):
    ok["=comb"] &= row == [comb(n, k) for k in range(n + 1)]
    ok["sum=2^n"] &= sum(row) == 2 ** n
    if n > 0:
        ok["alt=0"] &= sum((-1) ** k * c for k, c in enumerate(row)) == 0
        ok["k*C=n*2^(n-1)"] &= sum(k * c for k, c in enumerate(row)) == n * 2 ** (n - 1)
    ok["squares=C(2n,n)"] &= sum(c * c for c in row) == comb(2 * n, n)
    for r in range(n):
        ok["hockey"] &= sum(comb(i, r) for i in range(r, n + 1)) == comb(n + 1, r + 1)
for m in range(16):
    for n in range(16):
        for r in range(m + n + 1):
            v = sum(comb(m, k) * comb(n, r - k) for k in range(r + 1))
            ok["vandermonde"] &= v == comb(m + n, r)
for name, good in ok.items():
    print(f"{name:16} {'holds' if good else 'FAILS'} for n = 0..30")

bad = [n for n in range(1, 31, 2) if any(c % 2 == 0 for c in rows[n])]
print("odd n with an even entry, first:", bad[0])
print("C(30,15) =", rows[30][15])

           1
          1 1
         1 2 1
        1 3 3 1
       1 4 6 4 1
     1 5 10 10 5 1
    1 6 15 20 15 6 1
=comb            holds for n = 0..30
sum=2^n          holds for n = 0..30
alt=0            holds for n = 0..30
k*C=n*2^(n-1)    holds for n = 0..30
squares=C(2n,n)  holds for n = 0..30
hockey           holds for n = 0..30
vandermonde      holds for n = 0..30
odd n with an even entry, first: 5
C(30,15) = 155117520

৪ · Binomial theorem — দুটি প্রমাণ

স্কুলে শিখেছেন (x + y)² = x² + 2xy + y². ঘাত বাড়ালে (x + y)³ = x³ + 3x²y + 3xy² + y³, (x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴. সহগগুলো চেনা লাগছে? 1 2 1, 1 3 3 1, 1 4 6 4 1: Pascal-এর ত্রিভুজের সারি। এটি কাকতালীয় নয়।

“Binomial” মানে দুই পদের রাশি, x + y. ∑ চিহ্নের নিয়ম পর্ব ১৭-এ। শর্ত xy = yx কেন লাগে, তা প্রমাণের পরে দেখব।

প্রমাণ ১ (combinatorial):

1. (x + y)ⁿ = (x + y)(x + y)…(x + y), n টি বন্ধনী। বিতরণ নিয়মে (distributive law) গুণফল খুললে প্রতিটি বন্ধনী থেকে x বা y একটি করে বেছে গুণ করে পাওয়া সব পদের যোগফল আসে।
2. প্রতিটি বাছাইকে x আর y-এর n অক্ষরের একটি শব্দ হিসেবে লেখা যায়, যেমন n = 4-এ xyyx মানে প্রথম আর চতুর্থ বন্ধনী থেকে x, মাঝের দুটি থেকে y. মোট 2ⁿটি শব্দ, প্রতিটি একবার।
3. যে শব্দে ঠিক k টি y, তার গুণফল x^n−ky^k (এখানে xy = yx লাগছে, যাতে অক্ষরগুলো সাজিয়ে একত্র করা যায়)।
4. ঠিক k টি y-ওয়ালা শব্দ কয়টি? n টি অবস্থান থেকে y-এর k টি অবস্থান বাছার উপায়, অর্থাৎ C(n, k).
5. তাই x^n−ky^k পদটি ঠিক C(n, k) বার আসে, আর k = 0..n যোগ করলে উপপাদ্য। ∎

প্রমাণ ২ (n-এর ওপর mathematical induction): P(n): (x + y)ⁿ = ∑_k=0ⁿ C(n, k)x^n−ky^k.

1. Basis n = 0: বাঁ পাশ (x + y)⁰ = 1, ডান পাশ C(0, 0)x⁰y⁰ = 1.
2. ধরি কোনো n ≥ 0-এর জন্য P(n) সত্য (inductive hypothesis).
3. (x + y)ⁿ⁺¹ = (x + y)(x + y)ⁿ = ∑_k=0ⁿ C(n, k)x^n+1−ky^k + ∑_k=0ⁿ C(n, k)x^n−ky^k+1, hypothesis আর বিতরণ নিয়মে।
4. দ্বিতীয় যোগফলে j = k + 1 বসাই (index shift): ∑_j=1ⁿ⁺¹ C(n, j − 1)x^n+1−jy^j. প্রথম যোগফলেও সূচকের নাম j.
5. j = 1..n-এর পদগুলো একত্র করলে সহগ C(n, j) + C(n, j − 1) = C(n + 1, j), Pascal-এর identity (উপপাদ্য ৩.১)।
6. বাকি থাকে প্রথম যোগফলের j = 0 পদ xⁿ⁺¹ = C(n + 1, 0)xⁿ⁺¹ আর দ্বিতীয়টির j = n + 1 পদ yⁿ⁺¹ = C(n + 1, n + 1)yⁿ⁺¹.
7. সব মিলিয়ে (x + y)ⁿ⁺¹ = ∑_j=0ⁿ⁺¹ C(n + 1, j)x^n+1−jy^j, অর্থাৎ P(n + 1). ∎

দুই প্রমাণের তুলনা শিক্ষণীয়। Induction-এর প্রমাণে Pascal-এর identity হলো ইঞ্জিন: (x + y)-এর সঙ্গে গুণ করলে প্রতিটি সহগ ওপরের দুই প্রতিবেশীর যোগফল হয়, ঠিক ত্রিভুজের নিয়ম। Combinatorial প্রমাণ সরাসরি বলে কেন সহগটি C(n, k). Induction-এর ছাঁচ পর্ব ১০-এ।

এখন যন্ত্রে মিলিয়ে নিই। নিচের ব্লক (ax + by)ⁿ-কে একটি একটি বন্ধনী করে গুণ করে খোলে, ঠিক প্রমাণ ১-এর মতো: প্রতিটি বন্ধনী থেকে “ax নাও” অথবা “by নাও”। তারপর সব 16টি শব্দ তালিকা করে y-এর সংখ্যা অনুযায়ী ভাগ করে। অভিধান {k: সহগ}-এ k হলো y-এর ঘাত।

from collections import Counter
from itertools import product
from math import comb

def expand(a, b, n):
    """(a*x + b*y)^n as {power of y: coefficient}, one bracket at a time"""
    poly = {0: 1}
    for _ in range(n):
        new = Counter()
        for k, c in poly.items():
            new[k] += c * a           # take a*x from this bracket
            new[k + 1] += c * b       # take b*y from this bracket
        poly = new
    return dict(sorted(poly.items()))

print("(x+y)^4  :", expand(1, 1, 4))
p = expand(2, -3, 8)
print("(2x-3y)^8, x^5 y^3:", p[3], "| formula:", comb(8, 3) * 2**5 * (-3)**3)
q = expand(1, 2, 6)                   # (x + 2/x)^6: y = 1/x, power of x = 6-2k
print("(x+2/x)^6, constant term:", q[3], "| formula:", comb(6, 3) * 2**3)
print("sum of coefficients of (2x-3y)^8:", sum(p.values()), "= (2-3)^8")

words = ["".join(w) for w in product("xy", repeat=4)]
by_y = Counter(w.count("y") for w in words)
print(len(words), "words from 4 brackets, by number of y:", dict(sorted(by_y.items())))
print("words with two y:", [w for w in words if w.count("y") == 2])
print("11^n:", [11 ** n for n in range(6)])

(x+y)^4  : {0: 1, 1: 4, 2: 6, 3: 4, 4: 1}
(2x-3y)^8, x^5 y^3: -48384 | formula: -48384
(x+2/x)^6, constant term: 160 | formula: 160
sum of coefficients of (2x-3y)^8: 1 = (2-3)^8
16 words from 4 brackets, by number of y: {0: 1, 1: 4, 2: 6, 3: 4, 4: 1}
words with two y: ['xxyy', 'xyxy', 'xyyx', 'yxxy', 'yxyx', 'yyxx']
11^n: [1, 11, 121, 1331, 14641, 161051]

৫ · General term আর coefficient বের করা — পরীক্ষার হিসাব

বিশ্ববিদ্যালয় আর চাকরির লিখিত পরীক্ষায় binomial theorem সবচেয়ে বেশি আসে একটি নির্দিষ্ট পদ খোঁজার প্রশ্নে। পুরো রাশি খোলার দরকার নেই; একটি সাধারণ পদ লিখে শর্ত বসালেই চলে।

হিসাব ১: (2x − 3y)⁸-এ x⁵y³-এর সহগ কত? a = 2x, b = −3y, n = 8. y³ চাই, তাই k = 3, আর তখন x-এর ঘাত 8 − 3 = 5, মিলে গেছে। পদ C(8, 3)(2x)⁵(−3y)³ = 56 · 32 · (−27) x⁵y³. সহগ 56 · 32 = 1792, তারপর 1792 · (−27) = −48384. চিহ্নের ভুল খুব সাধারণ: (−3)³ ঋণাত্মক, কারণ ঘাত বিজোড়।

হিসাব ২ (ধ্রুবক পদ): (x² − 1/x)⁶-এর যে পদে x নেই, সেটি কত? সাধারণ পদ C(6, k)(x²)^6−k(−1/x)^k = C(6, k)(−1)^k x^12−2k−k = C(6, k)(−1)^k x^12−3k. x-এর ঘাত শূন্য চাই: 12 − 3k = 0, তাই k = 4. ধ্রুবক পদ C(6, 4)(−1)⁴ = 15. কোনো পূর্ণসংখ্যা k না মিললে (যেমন 12 − 3k = 1) এমন পদ নেই, উত্তর 0.

হিসাব ৩ (মাঝের পদ): (a + b)¹⁰-এ পদ ১১টি, মাঝের পদ ৬ষ্ঠ, k = 5: C(10, 5)a⁵b⁵ = 252a⁵b⁵. n জোড় হলে মাঝের পদ একটি, k = n/2; n বিজোড় হলে দুটি। সারি n-এর সবচেয়ে বড় সংখ্যাও মাঝখানে: C(n, k) k = ⌊n/2⌋ পর্যন্ত বাড়ে, তারপর কমে, কারণ C(n, k + 1)/C(n, k) = (n − k)/(k + 1), যা k < (n − 1)/2 হলে 1-এর বেশি। এই মাঝের সংখ্যা C(2m, m)-কে বলে central binomial coefficient: 2, 6, 20, 70, 252, 924, …

হিসাব ৪ (আসন্ন মান): (1.01)¹⁰ কত, ক্যালকুলেটর ছাড়া? (1 + 0.01)¹⁰ = 1 + 10(0.01) + 45(0.0001) + 120(0.000001) + … = 1 + 0.1 + 0.0045 + 0.00012 + … ≈ 1.10462. আসল মান 1.104622…; প্রথম চারটি পদেই পাঁচ দশমিক ঘর পর্যন্ত ঠিক। বাজারঘরের কোনো সূচক মাসে ১% করে দশ মাস বাড়লে মোট বৃদ্ধি প্রায় ১০.৫%, শুধু ১০% নয়; বাড়তিটুকু আসে C(10, 2) আর পরের পদ থেকে।

৬ · সারির যোগফল: 2ⁿ, একান্তর যোগফল আর ∑k·C(n, k)

Binomial theorem একটি সূত্র নয়, সূত্র বানানোর একটি যন্ত্র: x আর y-তে নানা মান বসিয়ে নতুন identity পাওয়া যায়। প্রতিটির একটি combinatorial গল্পও আছে।

প্রমাণ ক (বীজগণিত): binomial theorem-এ x = y = 1 বসালে (1 + 1)ⁿ = ∑C(n, k) · 1 · 1. ∎

প্রমাণ খ (double counting):

1. X = n-উপাদানের সেট S-এর সব subset-এর সেট, অর্থাৎ power set.
2. আকার অনুযায়ী ভাগ করি: আকার k-এর subset C(n, k)টি, k = 0..n, প্রতিটি subset ঠিক একটি আকারে। তাই |X| = ∑C(n, k).
3. অন্যভাবে: প্রতিটি উপাদানের জন্য দুটি সিদ্ধান্ত, “নেব” বা “নেব না”; n টি স্বাধীন সিদ্ধান্ত, গুণের নিয়মে 2ⁿ. এটি পর্ব ১৪-এর |P(S)| = 2ⁿ.
4. দুটি সমান। ∎

প্রমাণ (বীজগণিত): x = 1, y = −1 বসালে (1 − 1)ⁿ = 0, যা n ≥ 1-এ শূন্য। (n = 0-এ 0⁰ = 1, তাই শর্তটি লাগে।) ∎

প্রমাণ (bijection): S-এ একটি নির্দিষ্ট উপাদান a নিন (n ≥ 1 বলে a আছে)। প্রতিটি subset A-কে পাঠান A △ {a}-তে: a থাকলে সরিয়ে দিন, না থাকলে যোগ করুন। একই কাজ দুইবার করলে A ফিরে আসে, তাই এটি নিজেই নিজের inverse, একটি bijection; আর এটি সবসময় আকার এক বাড়ায় বা কমায়, তাই জোড় আকারকে বিজোড়ে আর বিজোড়কে জোড়ে পাঠায়। দুই দল সমান। ∎ n = 5-এ জোড় আকারের subset 1 + 10 + 5 = 16 = 2⁴.

প্রমাণ (double counting):

1. X = সব (দল, দলনেতা) জোড়া, যেখানে দল n জনের যেকোনো subset আর নেতা সেই দলের একজন (ফাঁকা দলের কোনো নেতা নেই)।
2. দল আগে: আকার k-এর দল C(n, k)টি, প্রতিটিতে k রকম নেতা; যোগ করে |X| = ∑k·C(n, k).
3. নেতা আগে: n রকম; তারপর বাকি n − 1 জনের প্রত্যেকে দলে থাকবেন কি না, 2ⁿ⁻¹ রকম। তাই |X| = n · 2ⁿ⁻¹. ∎

অন্য পথ: উপপাদ্য ২.১ থেকে k·C(n, k) = n·C(n − 1, k − 1); k = 1..n যোগ করলে n·∑C(n − 1, j) = n·2ⁿ⁻¹. Calculus জানলে (1 + x)ⁿ-কে x-এ অন্তরীকরণ করে x = 1 বসালেও আসে। অর্থ: n টি পণ্যের তালিকা থেকে এলোমেলো একটি subset নিলে তাতে গড়ে n·2ⁿ⁻¹/2ⁿ = n/2টি পণ্য থাকে; সম্ভাবনার এই ভাষা পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”-তে।

আরেকটি কৌশল: x = 1, y = 2 বসালে ∑C(n, k)2^k = 3ⁿ. গল্প: n জন রাইডারের প্রত্যেককে তিনটি কাজের একটি দিন, “ছুটি”, “ঢাকা” বা “চট্টগ্রাম”। মোট 3ⁿ রকম। আবার, যাঁরা ছুটিতে নেই তাঁদের সেট আগে বাছুন (আকার k, C(n, k) রকম), তারপর তাঁদের প্রত্যেককে দুই শহরের একটি (2^k রকম)। n = 10-এ দুই পাশ 59049.

৭ · Vandermonde আর hockey-stick identity

বাজারঘরের একটি বিশেষ অভিযানে দুই শহরের রাইডার মিলিয়ে দল বানাতে হবে। ঢাকায় m জন, চট্টগ্রামে n জন রাইডার; মোট r জনের দল কতভাবে? সরাসরি উত্তর C(m + n, r). কিন্তু দলে ঢাকার কতজন, তা দিয়ে ভাগ করেও গোনা যায়।

প্রমাণ (double counting):

1. X = ঢাকার m জন আর চট্টগ্রামের n জন মিলিয়ে (দুই দল পৃথক) m + n জন থেকে r জনের সব দল। সংজ্ঞায় |X| = C(m + n, r).
2. প্রতিটি দলে ঢাকার রাইডারের সংখ্যা k, যেখানে 0 ≤ k ≤ r; প্রতিটি দলের k একটিই, তাই দলগুলো k অনুযায়ী পৃথক ভাগে পড়ে।
3. ঠিক k জন ঢাকার দল: ঢাকা থেকে k জন (C(m, k) রকম) আর চট্টগ্রাম থেকে বাকি r − k জন (C(n, r − k) রকম); গুণের নিয়মে C(m, k)·C(n, r − k).
4. k = 0..r যোগ করলে আবার |X|. k > m বা r − k > n হলে পদটি 0, প্রথা অনুযায়ী, তাই অসম্ভব ক্ষেত্রগুলো আপনা থেকে বাদ পড়ে। ∎

ছোট সংখ্যায় দেখুন: m = 3 (D1, D2, D3), n = 2 (C1, C2), r = 2.

1ঢাকা: D1 D2 D3      m = 32চট্টগ্রাম: C1 C2   n = 23k=0: C(3,0)·C(2,2) = 14k=1: C(3,1)·C(2,1) = 65k=2: C(3,2)·C(2,0) = 36মোট 10 = C(5,2)

নামটি ফরাসি গণিতবিদ Alexandre-Théophile Vandermonde-এর (১৭৭২ সালের দিকের কাজ); তবে চীনা গণিতবিদ Zhu Shijie-র ১৩০৩ সালের বইয়ে এই সম্পর্ক আগেই ছিল বলে ইতিহাসবিদরা উল্লেখ করেন।

প্রমাণ (double counting):

1. X = {1, 2, …, n + 1} থেকে r + 1 টি সংখ্যার সব subset; |X| = C(n + 1, r + 1).
2. প্রতিটি এমন subset-এর একটি সবচেয়ে বড় উপাদান আছে; তাকে i + 1 বলি। যেহেতু subset-এ r + 1 টি সংখ্যা, i + 1 ≥ r + 1, তাই r ≤ i ≤ n. প্রতিটি subset-এর i একটিই।
3. সবচেয়ে বড় উপাদান i + 1 নির্দিষ্ট হলে বাকি r টি সংখ্যা আসে {1, …, i} থেকে, C(i, r) রকম।
4. i = r..n যোগ করলে |X| = ∑C(i, r). ∎

ছবি ৩.১-এর কমলা রেখা এর আয়না-রূপ: C(i, r) = C(i, i − r) বলে 1 + 3 + 6 + 10 = C(2, 2) + C(3, 2) + C(4, 2) + C(5, 2) = C(6, 3) = 20. r = 1 নিলে পরিচিত ফল: 1 + 2 + … + n = C(n + 1, 2) = n(n + 1)/2, পর্ব ১৭-এর Gauss-এর যোগফল। r = 2 নিলে ত্রিভুজ সংখ্যার যোগফল C(n + 1, 3), যা বাজারঘরের তিন স্তরের লুপের পুনরাবৃত্তি গোনে। Induction দিয়েও প্রমাণ সহজ: ধাপে C(n + 1, r + 1) + C(n + 1, r) = C(n + 2, r + 1), আবার Pascal-এর identity.

একটি পুরোনো ঋণ শোধ: বৃত্ত কয়টি অংশে ভাগ হয়

পর্ব ১৭-এ দেখেছিলেন, বৃত্তের ওপর n টি বিন্দুর প্রতি জোড়া সরলরেখায় যুক্ত করলে (কোনো তিনটি রেখা ভেতরের একই বিন্দুতে না মিললে) অংশের সংখ্যা 1, 2, 4, 8, 16, তারপর 31. সূত্র 1 + C(n, 2) + C(n, 4). যুক্তির রূপরেখা: শুরুতে একটি অংশ। রেখাগুলো একটি একটি করে আঁকুন; যে রেখা আগের c টি রেখাকে ভেতরে কাটে, সেটি c + 1 টুকরোয় ভাগ হয়, আর প্রতিটি টুকরো একটি অংশকে দুই ভাগ করে, তাই অংশ বাড়ে c + 1. সব রেখা শেষে মোট বৃদ্ধি = (রেখার সংখ্যা) + (ভেতরের ছেদবিন্দুর সংখ্যা)। রেখা C(n, 2)টি; আর প্রতিটি ছেদবিন্দু ঠিক চারটি বিন্দু থেকে আসে (দুটি রেখার চার প্রান্ত), আর প্রতিটি চার বিন্দুর সেট ঠিক একটি ভেতরের ছেদবিন্দু দেয়, তাই ছেদবিন্দু C(n, 4)টি, একটি bijection. n = 6-এ 1 + 15 + 15 = 31.

এবার এই অংশের তিনটি গোনার প্রমাণ যন্ত্রে তালিকা করে দেখি: Pascal-এর ভাগ, Vandermonde-এর ভাগ, আর (দল, দলনেতা) জোড়া, প্রতিটি itertools.combinations দিয়ে সত্যিকারের দল বানিয়ে।

from itertools import combinations
from math import comb

riders = "ABCDE"                      # rider A is the special one
pairs = list(combinations(riders, 2))
with_a = ["".join(p) for p in pairs if "A" in p]
without_a = ["".join(p) for p in pairs if "A" not in p]
print("Pascal:", len(pairs), "=", len(with_a), "+", len(without_a))
print("  with A   :", with_a)
print("  without A:", without_a)

dhaka, ctg = ["D1", "D2", "D3"], ["C1", "C2"]
by_k = {}
for team in combinations(dhaka + ctg, 2):
    k = sum(r in dhaka for r in team)  # how many from Dhaka
    by_k.setdefault(k, []).append("+".join(team))
for k in sorted(by_k):
    print(f"k={k}: {len(by_k[k])} = C(3,{k})*C(2,{2-k})", by_k[k])

n = 5                                 # committee with a chair, two ways
count = sum(1 for k in range(n + 1)
            for team in combinations(range(n), k) for chair in team)
print("committee+chair:", count, "| sum k*C(5,k):",
      sum(k * comb(n, k) for k in range(n + 1)), "| n*2^(n-1):", n * 2 ** (n - 1))

Pascal: 10 = 4 + 6
  with A   : ['AB', 'AC', 'AD', 'AE']
  without A: ['BC', 'BD', 'BE', 'CD', 'CE', 'DE']
k=0: 1 = C(3,0)*C(2,2) ['C1+C2']
k=1: 6 = C(3,1)*C(2,1) ['D1+C1', 'D1+C2', 'D2+C1', 'D2+C2', 'D3+C1', 'D3+C2']
k=2: 3 = C(3,2)*C(2,0) ['D1+D2', 'D1+D3', 'D2+D3']
committee+chair: 80 | sum k*C(5,k): 80 | n*2^(n-1): 80

৮ · Pascal mod 2, Sierpinski আর Lucas — আর সামনে কী আছে

Pascal-এর ত্রিভুজের প্রতিটি সংখ্যার জায়গায় শুধু লিখুন সেটি জোড় না বিজোড়। Pascal-এর identity mod 2-তেও খাটে (পর্ব ২২): বিজোড় + বিজোড় = জোড়, বিজোড় + জোড় = বিজোড়, অর্থাৎ নিচের ঘরের parity ওপরের দুই ঘরের XOR. ফল একটি বিস্ময়কর নকশা: ত্রিভুজের ভেতরে ত্রিভুজ, তার ভেতরে আরও ছোট ত্রিভুজ। এটি Sierpinski ত্রিভুজ, পোলিশ গণিতবিদ Wacław Sierpiński-র নামে (১৯১৫ সালের দিকে তিনি এটি নিয়ে লেখেন)।

উপপাদ্যটি ফরাসি গণিতবিদ Édouard Lucas ১৮৭৮ সালে প্রকাশ করেন। প্রমাণ (1 + x)^p ≡ 1 + x^p (mod p) থেকে আসে, অংশ ৪-এর freshman's dream; আমরা এখানে তা বাদ রাখছি। উদাহরণ: C(10, 3) mod 3. 10 = 101₃, 3 = 010₃; মাঝের অঙ্কে C(0, 1) = 0, তাই C(10, 3) ≡ 0 (mod 3). সত্যিই C(10, 3) = 120 = 3 · 40. আর C(12, 5) জোড় না বিজোড়? 12 = 1100₂, 5 = 0101₂; 5-এর শেষ অঙ্কের 1-এর জায়গায় 12-তে 0, তাই জোড় (C(12, 5) = 792). প্রোগ্রামিং কনটেস্টে বড় n-এ C(n, k) mod p বের করার কৌশল DSA কোর্সের পর্ব ৬২-এ।

from math import comb

for n in range(16):                   # '#' = odd entry, '.' = even entry
    row = " ".join("#" if comb(n, k) % 2 else "." for k in range(n + 1))
    print(f"{n:2} " + " " * (15 - n) + row)

def lucas(n, k, p):                   # C(n,k) mod p from base-p digits
    r = 1
    while n or k:
        r = r * comb(n % p, k % p) % p    # comb(a, b) = 0 when b > a
        n, k = n // p, k // p
    return r

print("C(n,k) odd  <=>  k & n == k :",
      all((comb(n, k) % 2 == 1) == (k & n == k)
          for n in range(128) for k in range(n + 1)))
print("odd entries in row n = 2^(ones in n):",
      all(sum(comb(n, k) % 2 for k in range(n + 1)) == 2 ** bin(n).count("1")
          for n in range(128)))
for m in (3, 5, 7):
    odd = sum(comb(n, k) % 2 for n in range(2 ** m) for k in range(n + 1))
    print(f"rows 0..{2**m - 1}: {odd} odd of {2**m * (2**m + 1) // 2}, 3^{m} = {3**m}")
print("Lucas holds for p = 3, 5, 7, n < 200:",
      all(lucas(n, k, p) == comb(n, k) % p
          for p in (3, 5, 7) for n in range(200) for k in range(n + 1)))
print("C(10,3) =", comb(10, 3), "| mod 3 by Lucas:", lucas(10, 3, 3))

 0                #
 1               # #
 2              # . #
 3             # # # #
 4            # . . . #
 5           # # . . # #
 6          # . # . # . #
 7         # # # # # # # #
 8        # . . . . . . . #
 9       # # . . . . . . # #
10      # . # . . . . . # . #
11     # # # # . . . . # # # #
12    # . . . # . . . # . . . #
13   # # . . # # . . # # . . # #
14  # . # . # . # . # . # . # . #
15 # # # # # # # # # # # # # # # #
C(n,k) odd  <=>  k & n == k : True
odd entries in row n = 2^(ones in n): True
rows 0..7: 27 odd of 36, 3^3 = 27
rows 0..31: 243 odd of 528, 3^5 = 243
rows 0..127: 2187 odd of 8256, 3^7 = 2187
Lucas holds for p = 3, 5, 7, n < 200: True
C(10,3) = 120 | mod 3 by Lucas: 0

সামনে: তিন বা বেশি পদ, আর সম্ভাবনা

(x + y + z)ⁿ খুললে কী হয়? একই যুক্তিতে n টি বন্ধনী থেকে x, y বা z বাছাই; x^ay^bz^c (a + b + c = n) পদটি আসে n!/(a! b! c!) বার। যেমন (x + y + z)⁴-এ x²yz-এর সহগ 4!/(2! 1! 1!) = 12. এটিই multinomial theorem, যার পূর্ণ প্রমাণ আর stars and bars-এর সঙ্গে সম্পর্ক পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই — stars and bars আর multinomial”-এ।

সম্ভাবনায়: একটি ন্যায্য মুদ্রা n বার ছুড়লে ঠিক k বার হেড আসার সম্ভাবনা C(n, k)/2ⁿ, কারণ 2ⁿটি ফল সমান সম্ভাব্য আর তাদের C(n, k)টিতে ঠিক k টি হেড। সাফল্যের সম্ভাবনা p হলে C(n, k)p^k(1 − p)^n−k, আর binomial theorem বলে সব k-এর যোগফল (p + (1 − p))ⁿ = 1. এই হিসাব পর্ব ৩৮ “বিচ্ছিন্ন সম্ভাবনা — sample space, event আর Laplace-এর সংজ্ঞা”-য় শুরু হবে; binomial distribution আর simulation AI ফাউন্ডেশনস কোর্সের পর্ব ৩৬-এ।

৯ · AI-এর যুগে — AI-এর দেওয়া identity আর coefficient যাচাই

“(x + y)ⁿ-এর সূত্র কী?” এমন প্রশ্নে AI সহকারী সাধারণত ঠিক উত্তর দেয়। কিন্তু নির্দিষ্ট coefficient, নতুন identity বা combinatorial proof চাইলে ভুলের ঝুঁকি বাড়ে, আর ভুলগুলো আত্মবিশ্বাসী ভাষায় আসে। এই বিষয়ে চেনা ছাঁচগুলো:

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

• ছোট n-এ (0, 1, 2, 3) দুই পাশ নিজে হিসাব করে মিলিয়েছি
• Combinatorial proof-এ গোনা সেটটি স্পষ্ট, আর প্রতিটি ভাগ পৃথক ও সম্পূর্ণ
• Coefficient-এ ধ্রুবকের ঘাত আর চিহ্ন ধরেছি, আর সব variable = 1 বসিয়ে যোগফল মিলিয়েছি
• Python-এ math.comb বা itertools দিয়ে অনেক n-এ তুলনা করেছি
• প্রতিটি উপপাদ্যের শর্ত (n ≥ 1, xy = yx, p মৌলিক) লেখা আছে
• ইতিহাস বা বইয়ের উদ্ধৃতি থাকলে নিজে উৎস খুঁজে দেখেছি