Generating function — গণনাকে বীজগণিতে রূপান্তর

১ · ধারাকে একটি থলেতে ভরা — formal power series

এই মডিউলে এ পর্যন্ত একটি ধারা মানে ছিল আলাদা আলাদা সংখ্যা: H(0), H(1), H(2), …, আর তাদের মাঝে একটি recurrence. পর্ব ৪৪ “Recurrence দিয়ে মডেল — Fibonacci, Hanoi আর bit string”-এ মডেল বানানো, পর্ব ৪৫ “Linear recurrence সমাধান — characteristic equation” আর পর্ব ৪৬ “Non-homogeneous recurrence আর particular solution”-এ সমাধান। এবার একটি সম্পূর্ণ ভিন্ন কৌশল: পুরো ধারাটিকে একসঙ্গে একটি বস্তু হিসেবে ধরা, আর সেই বস্তুর ওপর বীজগণিত চালানো।

দুটি ছোট উদাহরণ। বাজারঘরের তিনটি পণ্য থেকে কয়েকটি বাছাইয়ের উপায় ধারা 1, 3, 3, 1 (k-টি বাছাই C(3, k) উপায়ে), তাই generating function 1 + 3x + 3x² + x³ = (1 + x)³: প্রতিটি পণ্যের জন্য একটি গুণনীয়ক (1 + x), “নেব না” বা “নেব”. আর দৈর্ঘ্য n-এর bit string-এর সংখ্যা 2ⁿ-এর generating function 1 + 2x + 4x² + ⋯, যার একটি ছোট রূপ একটু পরেই পাবেন। প্রথমটি সসীম polynomial, দ্বিতীয়টি অসীম series; দুটিই এই পর্বের বস্তু।

“Formal” কেন। ক্যালকুলাসে 1 + x + x² + ⋯ = 1/(1 − x) শুধু |x| < 1 হলে সত্য, কারণ সেখানে x একটি সংখ্যা আর যোগফলটি একটি limit. এখানে আমরা কখনো x-এ সংখ্যা বসাই না। গুণফলের প্রতিটি সহগ ∑_k=0ⁿ a_kb_n−k মাত্র n + 1টি পদের সসীম যোগ। তাই যেকোনো সহগ সসীম হিসাবে বের হয়, আর “অসীম যোগ মেলে কি না” প্রশ্নটি অপ্রাসঙ্গিক। n! xⁿ-এর মতো series, যা কোনো x ≠ 0-তে মেলে না, তা-ও একটি বৈধ formal power series. তাহলে 1/(1 − x) লেখার মানে কী? উত্তর উল্টানোর সংজ্ঞায়।

1. AB = 1-এর মানে [x⁰]: a₀b₀ = 1, আর n ≥ 1-এ [xⁿ]: ∑_k=0ⁿ a_kb_n−k = 0. — গুণের সংজ্ঞা, সহগ মেলানো
2. a₀ = 0 হলে প্রথম সমীকরণ 0 = 1 হয়ে যায়, তাই B নেই। — বিরোধ
3. a₀ ≠ 0 হলে b₀ = 1/a₀, আর n ≥ 1-এ b_n = −(1/a₀) ∑_k=1ⁿ a_kb_n−k: ডান পাশে শুধু আগের b, তাই প্রতিটি b_n একভাবেই নির্ধারিত। — strong induction (পর্ব ১১)
4. এভাবে বানানো B সব সমীকরণ মেটায়, আর প্রতিটি ধাপে বিকল্প ছিল না, তাই B অনন্য। ∎ — নির্মাণ

উদাহরণ: A = 1 − x হলে b₀ = 1, আর b_n = −(−1 · b_n−1) = b_n−1, তাই সব b_n = 1. অর্থাৎ 1/(1 − x) = 1 + x + x² + ⋯ একটি বীজগাণিতিক সত্য, কোনো limit ছাড়াই। সরাসরি যাচাই: (1 − x)(1 + x + x² + ⋯)-এ xⁿ-এর সহগ 1 − 1 = 0 (n ≥ 1). এই ধারাটি geometric series (পর্ব ১৭ “Sequence আর summation — closed form আর বিখ্যাত যোগফল”), তবে এবার সসীম যোগফলের সূত্র নয়, পুরো অসীম ধারাটিই একটি বস্তু।

এই পর্বের পথ। প্রথমে দেখব series-এর গুণ কী গোনে (§২), তারপর শর্তসহ বণ্টন আর খুচরো টাকা (§৩–৪), recurrence আর Catalan (§৫–৬), partition (§৭), আর শেষে লেবেলযুক্ত বস্তুর জন্য আরেক ধরনের থলে (§৮)। প্রতিটি জায়গায় একই ছন্দ: গণনার প্রশ্নকে একটি series-এর সমীকরণে লেখা, বীজগণিতে সরল করা, তারপর একটি সহগ পড়া।

২ · অপারেশন আর convolution — গুণফলের আসল অর্থ

ধারার ওপর যা করতে চান, generating function-এ তার একটি সরল রূপ আছে। A(x) = ∑a_nxⁿ ধরে:

Formal derivative-ও সংজ্ঞায়: A′(x) = ∑ na_nxⁿ⁻¹, কোনো limit নেই। “বাঁয়ে সরানো”-তে x দিয়ে ভাগ বৈধ, কারণ A(x) − a₀-এর ধ্রুবক পদ 0. সারণির শেষ সারিটিই সবচেয়ে গুরুত্বপূর্ণ; তার convolution নামটি এই পর্বে বারবার আসবে।

1. আকার n-এর জোড়াগুলোকে বাঁ অংশের আকার k অনুযায়ী ভাগ করুন, k = 0, 1, …, n. ভাগগুলো পরস্পর বিচ্ছিন্ন আর মিলে সব জোড়া। — যোগের নিয়ম (পর্ব ৩১)
2. বাঁ আকার k হলে ডান আকার ঠিক n − k; বাঁ অংশ a_k উপায়ে আর ডান অংশ স্বাধীনভাবে b_n−k উপায়ে। — গুণের নিয়ম
3. তাই c_n = ∑_k a_kb_n−k, যা সংজ্ঞা ১.১ অনুযায়ী [xⁿ]A(x)B(x). ∎ — গুণের সংজ্ঞা

বীজগণিতের দিক থেকে এটি শুধু x^k · x^n−k = xⁿ: ঘাতগুলো যোগ হয়, আর গণনায় আকারও যোগ হয়। এটিই পুরো পদ্ধতির চাবি। এর প্রথম বড় ফল:

1. 1/(1 − x)ⁿ হলো n-টি একই series (1 + x + x² + ⋯)-এর গুণফল; i-তম গুণনীয়ক থেকে x^e_i পদটি বাছলে মোট ঘাত e₁ + ⋯ + e_n. — উপপাদ্য ২.১ বারবার
2. তাই [x^k] = e₁ + ⋯ + e_n = k-এর অঋণাত্মক পূর্ণসংখ্যা সমাধানের সংখ্যা। — প্রতিটি পদের সহগ 1
3. পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই — stars and bars আর multinomial”-এর stars and bars অনুযায়ী সেই সংখ্যা C(n + k − 1, k). ∎ — stars and bars

এখান থেকে একটি ছোট সারণি পাওয়া যায়, যা মুখস্থ রাখলে বেশিরভাগ অঙ্ক হয়ে যায়:

একটি পুরোনো যোগফল নতুন পথে। 1² + 2² + ⋯ + n²-এর closed form পর্ব ১৭-এ induction দিয়ে প্রমাণ হয়েছে। Generating function দিয়ে সূত্রটি খুঁজে পাওয়া যায়, আগে থেকে জানা ছাড়াই:

1. ধারা k-এর generating function x/(1 − x)² (সারণি)। “n দিয়ে গুণ” নিয়মে আরেকবার: x · d/dx[x/(1 − x)²] = x(1 + x)/(1 − x)³, যা ধারা k²-এর generating function.
2. আংশিক যোগফল নিতে 1/(1 − x) দিয়ে গুণ: ∑_n (∑_k≤n k²) xⁿ = x(1 + x)/(1 − x)⁴ = x/(1 − x)⁴ + x²/(1 − x)⁴.
3. উপপাদ্য ২.২-এ n = 4: [x^m](1 − x)⁻⁴ = C(m + 3, 3). তাই উত্তর C(n + 2, 3) + C(n + 1, 3) = n(n + 1)(2n + 1)/6.
4. যাচাই n = 4: C(6, 3) + C(5, 3) = 20 + 10 = 30 = 1 + 4 + 9 + 16. (Scratch-এ n ≤ 7 পর্যন্ত মেলানো।)

শেষ সমতায় দুটি C(·, 3) যোগ করে সরল করা হয়েছে; এই বীজগণিত আপনি নিজে করে দেখতে পারেন। মূল কথা: derivative, shift আর 1/(1 − x) মিলে যোগফলের প্রশ্নকে সারণি পড়ার প্রশ্নে বদলে দেয়।

৩ · সহগ বের করা আর শর্তসহ বণ্টন

পর্ব ৩৫-এ x₁ + x₂ + x₃ = n ধরনের সমীকরণ গুনেছেন। নিম্নসীমা সরল প্রতিস্থাপনে সরে যেত, ঊর্ধ্বসীমায় বাদ দেওয়ার হিসাব লাগত। Generating function-এ প্রতিটি চলকের শর্ত তার নিজের গুণনীয়কে ঢোকে, আর গুণফল বাকি কাজ করে: প্রতিটি চলকের জন্য একটি গুণনীয়ক, প্রতিটি অনুমোদিত মানের জন্য একটি পদ।

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

1. রাজশাহী: 1 + x² + x⁴ + ⋯ = 1/(1 − x²). সিলেট: 1 + x + x² + x³. খুলনা: x + x² + ⋯ = x/(1 − x).
2. উত্তর = [xⁿ] G(x), যেখানে G(x) = (1 + x + x² + x³) · x / ((1 − x²)(1 − x)).
3. সরল করুন: 1 + x + x² + x³ = (1 + x)(1 + x²) আর 1 − x² = (1 − x)(1 + x). তাই G(x) = x(1 + x²)/(1 − x)².
4. x/(1 − x)²-এর সহগ k (সারণি), তাই x³/(1 − x)²-এর xⁿ-এর সহগ n − 2. যোগ করে n ≥ 3 হলে উত্তর n + (n − 2) = 2n − 2.
5. n = 10: ১৮টি উপায়। Scratch-এ তিনটি nested loop দিয়ে গুনে মেলানো; নিচের প্রথম Python ব্লকও এটি দেখায়।

খেয়াল করুন, একটি রাশি (2n − 2) সব n-এর উত্তর একসঙ্গে দিল। এটিই generating function-এর বড় সুবিধা: একটি প্রশ্ন নয়, প্রশ্নের পুরো পরিবার।

ঊর্ধ্বসীমা বীজগণিতে। চারজন গ্রাহকের প্রত্যেকে একটি প্রচারণায় ০ থেকে ৩টি পর্যন্ত পণ্য নিতে পারেন; মোট ১০টি পণ্য কয় উপায়ে যেতে পারে? উত্তর [x¹⁰](1 + x + x² + x³)⁴ = [x¹⁰](1 − x⁴)⁴/(1 − x)⁴. লবকে binomial theorem-এ খুলে 1 − 4x⁴ + 6x⁸ − ⋯, আর হরের সহগ C(k + 3, 3) নিলে convolution দেয়

C(13, 3) − 4 · C(9, 3) + 6 · C(5, 3) = 286 − 336 + 60 = 10

x¹²-এর পদ লাগে না, কারণ 12 > 10. যোগ-বিয়োগের এই ধাঁচ পর্ব ৩৫-এর ঊর্ধ্বসীমার হিসাবের সঙ্গে হুবহু মেলে; আসলে এটি inclusion–exclusion, যার সাধারণ রূপ আর প্রমাণ পরের পর্ব ৪৯ “Inclusion–exclusion আর derangement”-এ। Generating function চিহ্নগুলো নিজে থেকেই ঠিক রাখে।

৪ · খুচরো টাকার প্রশ্ন — ১, ২ আর ৫ টাকার কয়েন

বাজারঘরের ডেলিভারি রাইডারের থলেতে ১, ২ আর ৫ টাকার অনেক কয়েন। একজন গ্রাহককে n টাকা খুচরো ফেরত দিতে হবে। কয়েনের সংগ্রহ কয় রকম হতে পারে (কোন কয়েন আগে দেওয়া হলো তা গোনা হবে না)? এটি একটি coin change প্রশ্ন, আর এর সমীকরণ a + 2b + 5c = n, যেখানে a, b, c অঋণাত্মক। ভিন্ন ওজন থাকায় stars and bars এখানে সরাসরি খাটে না।

1. শুধু ৫ টাকার কয়েনে আকার (টাকা) 5c-এর ঠিক একটি সংগ্রহ: generating function 1 + x⁵ + x¹⁰ + ⋯ = 1/(1 − x⁵). ২ আর ১ টাকার জন্যও একইভাবে 1/(1 − x²) আর 1/(1 − x). — সারণি
2. একটি সংগ্রহ = (১ টাকার অংশ, ২ টাকার অংশ, ৫ টাকার অংশ), আর মোট টাকা তিন অংশের টাকার যোগ। — সংগ্রহের গঠন
3. উপপাদ্য ২.১ দুবার খাটালে মোট generating function তিনটির গুণফল। ∎ — উপপাদ্য ২.১

এখন x¹⁰-এর সহগ হাতে বের করি, গুণনীয়কগুলো একটি একটি করে গুণ করে।

1G = 1/((1−x)(1−x²)(1−x⁵))2শুধু ১ টাকা: aₙ = 13× 1/(1−x²): bₙ = ⌊n/2⌋ + 14× 1/(1−x⁵): b₁₀+b₅+b₀5c₁₀ = 6 + 3 + 1 = 106তালিকা করে মেলানো ✓

শর্ত বদলালে। যদি রাইডারকে অন্তত একটি ৫ টাকার কয়েন দিতেই হয়, ৫ টাকার গুণনীয়ক হয় x⁵/(1 − x⁵), তাই উত্তর c_n−5: ১০ টাকায় c₅ = 4, stepper-এর তালিকার “একটি বা দুটি ৫ টাকা” অংশের 3 + 1. আর ২ টাকার কয়েন যদি শেষ হয়ে যায় আর বড়জোর ২টি থাকে, গুণনীয়ক 1 + x² + x⁴. প্রতিটি নতুন শর্ত শুধু একটি গুণনীয়ক বদলায়; বাকি হিসাব একই থাকে।

হাতের হিসাব ১০ পর্যন্ত চলে; তারপর কম্পিউটার। Series-কে Python-এ একটি list হিসেবে রাখা যায়: list-এর k-তম ঘর = x^k-এর সহগ। নিচের ব্লক একটি mul function দিয়ে গুণ করে (শুধু x^N পর্যন্ত রাখে, কারণ উঁচু ঘাত নিচের সহগে কখনো প্রভাব ফেলে না), তারপর brute force-এর সঙ্গে মেলায়, আর শেষে §৩-এর ভাউচারের প্রশ্নটি করে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def mul(a, b, N):                     # product of two series, cut at x^N
    c = [0] * (N + 1)
    for i, x in enumerate(a):
        if x:
            for j in range(N + 1 - i):
                c[i + j] += x * b[j]
    return c

def coin(v, N):                       # 1 + x^v + x^2v + ... = 1/(1 - x^v)
    return [1 if k % v == 0 else 0 for k in range(N + 1)]

N = 100
G = [1] + [0] * N                     # the series "1"
for v in (1, 2, 5):                   # 1, 2 and 5 taka coins
    G = mul(G, coin(v, N), N)
print("ways to pay 0..20 taka:", G[:21])

def brute(n):                         # choose #5s and #2s; 1s fill the rest
    return sum(1 for c in range(n // 5 + 1)
                 for b in range((n - 5 * c) // 2 + 1))
print("GF == brute force for all n <= 100:",
      all(G[n] == brute(n) for n in range(N + 1)))
print("10 taka:", G[10], "  50 taka:", G[50], "  100 taka:", G[100])

# vouchers: branch A even, branch B at most 3, branch C at least 1
A = [1 if k % 2 == 0 else 0 for k in range(N + 1)]
B = [1, 1, 1, 1] + [0] * (N - 3)
C = [0] + [1] * N
V = mul(mul(A, B, N), C, N)
print("vouchers n = 0..12:", V[:13])
print("2n - 2 for n = 3..12:", [2 * n - 2 for n in range(3, 13)])

ways to pay 0..20 taka: [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16, 18, 20, 22, 24, 26, 29]
GF == brute force for all n <= 100: True
10 taka: 10   50 taka: 146   100 taka: 541
vouchers n = 0..12: [0, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22]
2n - 2 for n = 3..12: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22]

৫ · Recurrence সমাধান — Fibonacci থেকে partial fraction

পর্ব ৪৫-এ characteristic equation দিয়ে linear recurrence সমাধান হয়। Generating function একই উত্তরে পৌঁছায় অন্য পথে, আর সেই পথ এমন অনেক recurrence-এও চলে যেখানে characteristic equation-এর ধাঁচ খাটে না (Catalan, §৬)। পদ্ধতিটি সবসময় চার ধাপের:

1. A(x) = ∑a_nxⁿ ধরুন।
2. Recurrence যে n-গুলোতে খাটে, তাদের প্রতিটিতে দুই পাশে xⁿ গুণ করে যোগ করুন।
3. প্রতিটি যোগফলকে A(x) আর শুরুর মান দিয়ে লিখুন (shift-এর নিয়ম), তারপর A(x) বের করুন।
4. A(x)-কে partial fraction-এ ভেঙে প্রতিটি অংশের সহগ সারণি থেকে পড়ুন।

1F(x) = ∑ Fₙxⁿ, F₀=0, F₁=12(1 − x − x²)F(x)-এর সহগ3F(x) = x/(1 − x − x²)41 − x − x² = (1−φx)(1−ψx)5A = 1/√5, B = −1/√56Fₙ = (φⁿ − ψⁿ)/√5

আরেকটি উদাহরণ: Hanoi. H₀ = 0 আর n ≥ 1-এ H_n = 2H_n−1 + 1. ধাপ ২-এ শুধু n ≥ 1-এ যোগ করুন: ∑_n≥1 H_nxⁿ = 2x∑_n≥1 H_n−1xⁿ⁻¹ + ∑_n≥1 xⁿ, অর্থাৎ H(x) − H₀ = 2xH(x) + x/(1 − x). তাই H(x) = x/((1 − x)(1 − 2x)) = 1/(1 − 2x) − 1/(1 − x), আর H_n = 2ⁿ − 1. শেষ অংশটি x/(1 − x), 1/(1 − x) নয়: “+1” শুধু n ≥ 1-এ যোগ হয়েছে। এই সূক্ষ্মতাটি ভুলে গেলে কী হয়, তা অনুশীলন ৪-এ দেখবেন।

Non-homogeneous recurrence-এও (পর্ব ৪৬) পদ্ধতি একই: ডান পাশের অতিরিক্ত পদ F(n) নিজের generating function নিয়ে আসে (Hanoi-তে x/(1 − x)), আর তা হরে একটি নতুন উৎপাদক যোগ করে। পর্ব ৪৬-এ particular solution-এর “অনুমান” যেখানে লাগে, এখানে তা partial fraction-এর একটি অংশ হিসেবে নিজেই আসে; শুধু হিসাব একটু লম্বা।

নিচের ব্লক উপপাদ্য ১.২-এর প্রমাণটিকেই algorithm বানায়: হরের ধ্রুবক পদ 1 হলে num/den-এর সহগ এক এক করে বের হয়। তারপর §৬-এর Catalan সমীকরণ C = 1 + xC²-কে বারবার নিজের মধ্যে বসিয়ে তার সহগও বের করে।

from math import comb

def divide(num, den, N):              # coefficients of num/den, den[0] = 1
    a = []
    for n in range(N + 1):
        s = num[n] if n < len(num) else 0
        for k in range(1, min(n, len(den) - 1) + 1):
            s -= den[k] * a[n - k]
        a.append(s)                   # from (den * a)[n] = num[n]
    return a

N = 15
print("x/(1-x-x^2)     :", divide([0, 1], [1, -1, -1], N))
print("x/((1-x)(1-2x)) :", divide([0, 1], [1, -3, 2], 8))
print("2^n - 1         :", [2 ** n - 1 for n in range(9)])
print("(1-x)/(1-5x+6x^2):", divide([1, -1], [1, -5, 6], 7))
print("2*3^n - 2^n      :", [2 * 3 ** n - 2 ** n for n in range(8)])

def mul(a, b, N):
    return [sum(a[i] * b[n - i] for i in range(n + 1)) for n in range(N + 1)]

C = [1] + [0] * N                     # start from C(x) = 1
for step in range(N + 1):             # repeat C <- 1 + x * C(x)^2
    C = [1] + mul(C, C, N)[:N]
print("C = 1 + xC^2 :", C[:12])
print("C(2n,n)/(n+1):", [comb(2 * n, n) // (n + 1) for n in range(12)])

x/(1-x-x^2)     : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
x/((1-x)(1-2x)) : [0, 1, 3, 7, 15, 31, 63, 127, 255]
2^n - 1         : [0, 1, 3, 7, 15, 31, 63, 127, 255]
(1-x)/(1-5x+6x^2): [1, 4, 14, 46, 146, 454, 1394, 4246]
2*3^n - 2^n      : [1, 4, 14, 46, 146, 454, 1394, 4246]
C = 1 + xC^2 : [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786]
C(2n,n)/(n+1): [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786]

৬ · Catalan-এর generating function — একটি দ্বিঘাত সমীকরণ

পর্ব ৩৭ “গণনার কৌশল — lattice path, bijection আর double counting”-এ reflection দিয়ে Catalan সংখ্যা C_n = C(2n, n)/(n + 1) প্রমাণ হয়েছে, আর বন্ধনীর প্রথম জোড়া ধরে ভেঙে recurrence C₀ = 1, C_n+1 = ∑_i=0ⁿ C_iC_n−i পাওয়া গেছে। এই recurrence linear নয় (C·C গুণফল), তাই characteristic equation এখানে অচল। কিন্তু ডান পাশটি দেখতে হুবহু একটি convolution.

1. [xⁿ]C(x)² = ∑_i=0ⁿ C_iC_n−i = C_n+1, তাই xC(x)² = ∑_n≥0 C_n+1xⁿ⁺¹ = C(x) − C₀ = C(x) − 1. — convolution, shift
2. তাই xC² − C + 1 = 0. দ্বিঘাত সূত্রের মতো (2xC − 1)² = 1 − 4x: বাঁ পাশ খুললে 4x²C² − 4xC + 1 = 4x(xC² − C + 1) + 1 − 4x. — বর্গ পূর্ণ করা
3. যে series-এর বর্গ 1 − 4x আর ধ্রুবক পদ 1, তাকে √(1 − 4x) লিখি (উপপাদ্য ১.২-এর মতো সহগ এক এক করে নির্ধারিত হয়, ধ্রুবক পদের চিহ্ন বেছে নিলে অনন্য)। 2xC − 1-এর ধ্রুবক পদ −1, তাই 2xC − 1 = −√(1 − 4x). — চিহ্ন বাছাই
4. অতএব 2xC(x) = 1 − √(1 − 4x). Generalized binomial theorem (নিচে) অনুযায়ী √(1 − 4x) = 1 − ∑_k≥1 (2/k) C(2k − 2, k − 1) x^k. — Newton-এর ধারা
5. তাই 2xC(x) = ∑_k≥1 (2/k) C(2k − 2, k − 1) x^k; দুই পাশ 2x দিয়ে ভাগ করে n = k − 1 বসালে C_n = C(2n, n)/(n + 1). ∎ — সহগ মেলানো

চিহ্ন কেন বিয়োগ। দ্বিঘাত সূত্র দুটি “মূল” দেয়: (1 ± √(1 − 4x))/(2x). যোগ চিহ্ন নিলে লবের ধ্রুবক পদ 2, আর 2/(2x) = 1/x কোনো power series নয় (x-এর ঋণাত্মক ঘাত)। বিয়োগ চিহ্নে লবের ধ্রুবক পদ 0, তাই x দিয়ে ভাগ বৈধ। এটি পরীক্ষায় প্রায়ই জিজ্ঞাসিত একটি যুক্তি।

প্রমাণ এখানে বাদ (সহগের polynomial identity, Vandermonde-এর ধাঁচে); Newton ১৬৬০-এর দশকে এটি খুঁজে পান বলে জানা যায় (পর্ব ৩৪-এর “আরও গভীরে”)। α = 1/2, x-এর জায়গায় −4x বসালে C(1/2, k)(−4)^k = −(2/k)C(2k − 2, k − 1) (k ≥ 1), যা ধাপ ৪-এ লেগেছে; প্রথম কয়েকটি পদ √(1 − 4x) = 1 − 2x − 2x² − 4x³ − 10x⁴ − ⋯ (scratch-এ Fraction দিয়ে k = 1…14 মেলানো)। 2, 2, 4, 10 = 2C₀, 2C₁, 2C₂, 2C₃: ধাপ ৫ চোখের সামনেই।

খেয়াল করুন, এই প্রমাণে reflection বা কোনো ছবি লাগেনি: “প্রথম অংশে ভাঙা” থেকে পাওয়া recurrence একটি দ্বিঘাত সমীকরণ হলো, আর বাকিটা বীজগণিত। একই কৌশল সব “একটি root আর দুটি ছোট একই ধরনের অংশ” গঠনে খাটে, যেমন n-টি node-এর binary tree, আর পর্ব ৫০-এ Catalan পরিবারের অন্য সদস্যদের জন্যও এটি কাজে লাগবে।

৭ · Partition-এর generating function আর Euler-এর উপপাদ্য

একটি পূর্ণসংখ্যা n-এর partition মানে n-কে ধনাত্মক পূর্ণসংখ্যার যোগফলে লেখা, যেখানে ক্রম গুরুত্বহীন: 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1, তাই p(4) = 5. বাজারঘরের ভাষায়: যেকোনো মাপের প্যাকেট আছে, n কেজি চাল কয় রকম প্যাকেট-সংগ্রহে ভরা যায়? এটি আসলে সব মানের কয়েনের খুচরো প্রশ্ন, তাই উপপাদ্য ৪.১-এর মতোই

∑_n≥0 p(n)xⁿ = ∏_k≥1 1/(1 − x^k)

অসীম গুণফল কীভাবে বৈধ? xⁿ-এর সহগে শুধু k ≤ n-এর গুণনীয়কগুলো প্রভাব ফেলে, কারণ k > n-এর গুণনীয়ক 1 + x^k + ⋯ থেকে 1 ছাড়া যেকোনো পদ ঘাতকে n-এর ওপরে নিয়ে যায়। তাই প্রতিটি সহগ একটি সসীম গুণফল থেকে আসে। একই যুক্তিতে, প্রতিটি অংশ বড়জোর একবার ব্যবহারের partition (আলাদা অংশ) গোনে ∏(1 + x^k), আর শুধু বিজোড় অংশের partition গোনে ∏_{k বিজোড়} 1/(1 − x^k). Partition-এর বিস্তারিত (Ferrers diagram, pentagonal number theorem) পর্ব ৫০ “বিশেষ সংখ্যা — Catalan, Stirling আর partition”-এ আসবে।

গুণনীয়ক 1 + x^k-কে একটি হ্যাঁ/না প্রশ্ন হিসেবে পড়ুন: “অংশ k কি আছে?” না হলে 1, হ্যাঁ হলে x^k. যেমন n = 5-এ (1 + x)(1 + x²)(1 + x³)(1 + x⁴)(1 + x⁵) খুললে x⁵ আসে তিনভাবে: x⁵, x⁴ · x, x³ · x². অর্থাৎ 5, 4+1, 3+2: q(5) = 3. বিজোড় অংশে: 5, 3+1+1, 1+1+1+1+1, এখানেও তিনটি। কাকতালীয়? নিচের উপপাদ্য বলে, না।

1Q = ∏(1+xᵏ), O: বিজোড়21 + xᵏ = (1 − x²ᵏ)/(1 − xᵏ)3Q = ∏(1−x²ᵏ) / ∏(1−xᵏ)4জোড় হর কাটে ⇒ Q = O5n = 6: q = o = 46Glaisher: 3+3 → 6

শেষ ধাপের জোড়াটি J. W. L. Glaisher ১৮৮৩ সালে দেন বলে জানা যায়; এটি একটি bijective proof. Generating function প্রমাণ চার লাইনের, কিন্তু কোন partition কোনটির সঙ্গে জোড়া, তা বলে না; bijection বলে। দুটি প্রমাণ একে অন্যের পরিপূরক। নিচের ব্লক n ≤ 30-এ তিনটি গুণফল হিসাব করে, আর n = 12-এ সব partition তালিকা করে গোনে।

def mul(a, b, N):
    c = [0] * (N + 1)
    for i, x in enumerate(a):
        if x:
            for j in range(N + 1 - i):
                c[i + j] += x * b[j]
    return c

N = 30
distinct = odd = allp = [1] + [0] * N
for k in range(1, N + 1):
    plus = [1] + [0] * N
    plus[k] = 1                                          # 1 + x^k
    geo = [1 if j % k == 0 else 0 for j in range(N + 1)]  # 1/(1 - x^k)
    distinct = mul(distinct, plus, N)
    allp = mul(allp, geo, N)
    if k % 2 == 1:
        odd = mul(odd, geo, N)
print("n:", list(range(16)))
print("q:", distinct[:16])
print("o:", odd[:16])
print("q == o for every n <= 30:", distinct == odd)
print("q(30) =", distinct[30], "  p(30) =", allp[30])

def brute(n, largest):                # partitions of n, parts <= largest
    if n == 0:
        return [[]]
    return [[k] + rest for k in range(min(n, largest), 0, -1)
            for rest in brute(n - k, k)]
P = brute(12, 12)
print("brute force n = 12: all", len(P),
      " distinct", sum(len(set(p)) == len(p) for p in P),
      " odd", sum(all(x % 2 for x in p) for p in P))

n: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
q: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27]
o: [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27]
q == o for every n <= 30: True
q(30) = 296   p(30) = 5604
brute force n = 12: all 77  distinct 15  odd 15

৮ · Exponential generating function — লেবেলযুক্ত বস্তু

খুচরো টাকায় দুটি ৫ টাকার কয়েন অভিন্ন; কোনটি “প্রথম” তা অর্থহীন। কিন্তু অনেক প্রশ্নে বস্তুগুলোর নাম আছে: n জন গ্রাহক, n-টি অর্ডার নম্বর। তখন দুটি অংশ জোড়া লাগাতে শুধু আকার যোগ হয় না, কোন লেবেল কোন অংশে গেল তা-ও বাছতে হয়। এর জন্য আরেক রকম থলে।

1. [xⁿ]ÂB̂ = ∑_k (a_k/k!)(b_n−k/(n − k)!). — সাধারণ গুণের সংজ্ঞা
2. n! দিয়ে গুণ করলে প্রতিটি পদে n!/(k!(n − k)!) = C(n, k) আসে। ∎ — binomial coefficient-এর সূত্র

গণনায় অর্থ: n-টি লেবেলের মধ্যে কোন k-টি বাঁ অংশে যাবে তা C(n, k) উপায়ে বাছুন, তারপর বাঁ অংশে a_k আর ডান অংশে b_n−k রকম গঠন। এই “binomial convolution” লেবেলযুক্ত বস্তুর জন্য উপপাদ্য ২.১-এর ভূমিকা নেয়। দুটি মৌলিক EGF: সব a_n = 1 হলে Â = ∑xⁿ/n! = e^x (প্রতিটি সেটে “কিছু না করার” একটিই উপায়), আর a_n = n! (সব permutation) হলে Â = ∑xⁿ = 1/(1 − x). এখানে e^x একটি formal power series-এর নাম, কোনো সংখ্যার ঘাত নয়; e^x · e^−x = 1 সহগ মিলিয়ে যাচাই করা যায় (∑_k C(n, k)(−1)^k = 0, n ≥ 1, পর্ব ৩৪)।

Derangement, এক নজরে। একটি derangement হলো এমন permutation যাতে কোনো উপাদান নিজের জায়গায় নেই, যেমন বাজারঘরের n জন কর্মীর উপহার-বিনিময়ে কেউ নিজের নামের প্যাকেট পান না। পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”-এ দেখেছেন, fixed point-এর প্রত্যাশিত সংখ্যা 1. এখন গোনা: প্রতিটি permutation অনন্যভাবে ভাঙে “কোন k-টি উপাদান স্থির” (একভাবেই বসানো) আর “বাকি n − k-টির একটি derangement”-এ। তাই n! = ∑_k C(n, k) · 1 · D_n−k, আর উপপাদ্য ৮.২ অনুযায়ী EGF-এ

1/(1 − x) = e^x · D̂(x) ⇒ D̂(x) = e^−x/(1 − x) ⇒ D_n = n! ∑_k=0ⁿ (−1)^k/k!

শেষ ধাপে e^−x-এর সহগ (−1)^k/k! আর 1/(1 − x)-এর সব 1-এর convolution আংশিক যোগফল দেয় (§২-এর সারণি)। একই সূত্রের inclusion–exclusion প্রমাণ আর D_n/n! → 1/e পর্ব ৪৯-এ আসবে; এখানে শুধু দেখুন EGF কত দ্রুত সেখানে পৌঁছায়।

আরেকটি ছোট উদাহরণ। n-টি আলাদা অর্ডার দুজন রাইডারের মধ্যে ভাগ করতে হবে, প্রত্যেকে অন্তত একটি পাবেন। একজন রাইডারের ভাগে k-টি অর্ডার নেওয়ার একটিই উপায় (k ≥ 1), তাই তার EGF ∑_k≥1 x^k/k! = e^x − 1. উপপাদ্য ৮.২ অনুযায়ী দুজনের EGF (e^x − 1)² = e^2x − 2e^x + 1, আর n ≥ 1-এ উত্তর 2ⁿ − 2: সব 2ⁿ ভাগ থেকে “সব একজনের কাছে” এমন দুটি বাদ। এটি n-টি থেকে ২-টিতে onto ফাংশনের সংখ্যা (পর্ব ১৬)। k জন রাইডারে (e^x − 1)^k, আর তার সহগ থেকে পর্ব ৪৯-এর onto সূত্র আর পর্ব ৫০-এর Stirling সংখ্যা বেরিয়ে আসে।

from fractions import Fraction
from math import factorial
from itertools import permutations

N = 8
e_minus = [Fraction((-1) ** k, factorial(k)) for k in range(N + 1)]  # e^(-x)
geo = [Fraction(1)] * (N + 1)                                        # 1/(1-x)
prod = [sum(e_minus[i] * geo[n - i] for i in range(n + 1))
        for n in range(N + 1)]
D = [prod[n] * factorial(n) for n in range(N + 1)]   # a_n = n! [x^n]
print("D_n from e^(-x)/(1-x):", [int(d) for d in D])

def brute(n):                          # permutations with no fixed point
    return sum(all(p[i] != i for i in range(n))
               for p in permutations(range(n)))
print("brute force, n <= 7  :", [brute(n) for n in range(8)])
print("D_8 / 8! =", D[8] / factorial(8), "=", float(D[8] / factorial(8)))

ex = [Fraction(1, factorial(k)) for k in range(N + 1)]               # e^x
sq = [sum(ex[i] * ex[n - i] for i in range(n + 1)) * factorial(n)
      for n in range(N + 1)]
print("n! [x^n] e^x * e^x  :", [int(s) for s in sq])

D_n from e^(-x)/(1-x): [1, 0, 1, 2, 9, 44, 265, 1854, 14833]
brute force, n <= 7  : [1, 0, 1, 2, 9, 44, 265, 1854]
D_8 / 8! = 2119/5760 = 0.36788194444444444
n! [x^n] e^x * e^x  : [1, 2, 4, 8, 16, 32, 64, 128, 256]

৯ · পরীক্ষার অঙ্ক আর একটি ভুল যুক্তি

অঙ্ক ১: ঊর্ধ্বসীমাসহ বণ্টন

x₁ + x₂ + x₃ + x₄ = 10, প্রতিটি 0 ≤ x_i ≤ 3. পূর্ণসংখ্যা সমাধান কয়টি?

1. উত্তর [x¹⁰](1 + x + x² + x³)⁴ = [x¹⁰](1 − x⁴)⁴ · (1 − x)⁻⁴.
2. (1 − x⁴)⁴ = 1 − 4x⁴ + 6x⁸ − 4x¹² + x¹⁶; (1 − x)⁻⁴-এর x^m-এর সহগ C(m + 3, 3).
3. Convolution: C(13, 3) − 4C(9, 3) + 6C(5, 3) = 286 − 336 + 60 = 10.
4. সহজ যাচাই: ৪টি চলকের সর্বোচ্চ যোগ 12, তাই 10 মানে “12 থেকে মোট 2 কম”: হয় একটি চলক 1 (৪ উপায়), নয়তো দুটি চলক 2 (C(4, 2) = 6 উপায়)। মোট ১০। উত্তর: ১০টি।

অঙ্ক ২: Generating function দিয়ে recurrence

a₀ = 1, a₁ = 4, আর n ≥ 2-এ a_n = 5a_n−1 − 6a_n−2. Closed form বের করুন।

1. (1 − 5x + 6x²)A(x)-এর সহগ: x⁰-এ a₀ = 1, x¹-এ a₁ − 5a₀ = −1, n ≥ 2-এ 0. তাই A(x) = (1 − x)/(1 − 5x + 6x²) = (1 − x)/((1 − 2x)(1 − 3x)).
2. 1 − x = P(1 − 3x) + Q(1 − 2x). x = 1/2 বসালে 1/2 = −P/2, তাই P = −1; x = 1/3 বসালে 2/3 = Q/3, তাই Q = 2.
3. A(x) = −1/(1 − 2x) + 2/(1 − 3x), তাই a_n = 2 · 3ⁿ − 2ⁿ. যাচাই: a₂ = 18 − 4 = 14 = 5 · 4 − 6 · 1. (দ্বিতীয় Python ব্লকে ৮টি পদ মেলানো।)

এখানে x = 1/2 বসানো কি “formal” নীতির বিরোধী? না: 1 − x = P(1 − 3x) + Q(1 − 2x) একটি polynomial-এর অভেদ, আর polynomial-এ মান বসানো সবসময় বৈধ। কোনো অসীম series-এ মান বসানো হয়নি।

অঙ্ক ৩: সহগ সরাসরি

[x¹²] x⁶/(1 − x)³ কত, আর এর গণনার অর্থ কী? উত্তর: [x⁶](1 − x)⁻³ = C(6 + 2, 2) = 28. অর্থ: তিন রকম পণ্য থেকে ১২টি বাছাই, প্রতিটি রকম অন্তত ২টি (প্রতিটি গুণনীয়ক x²/(1 − x)).

অঙ্ক ৪: পুনরাবৃত্ত মূল

a₀ = 1, a₁ = 6, আর n ≥ 2-এ a_n = 6a_n−1 − 9a_n−2. Closed form কী?

1. (1 − 6x + 9x²)A(x)-এর সহগ: x⁰-এ 1, x¹-এ a₁ − 6a₀ = 0, n ≥ 2-এ 0. তাই A(x) = 1/(1 − 6x + 9x²) = 1/(1 − 3x)².
2. উপপাদ্য ২.২-এ n = 2, তারপর x-এর জায়গায় 3x: [xⁿ](1 − 3x)⁻² = C(n + 1, n) · 3ⁿ = (n + 1)3ⁿ.
3. যাচাই: a₂ = 36 − 9 = 27 = 3 · 9, a₃ = 162 − 54 = 108 = 4 · 27. উত্তর: a_n = (n + 1)3ⁿ. (Scratch-এ n ≤ 7 মেলানো।)

পর্ব ৪৫-এর পুনরাবৃত্ত মূলের “n · rⁿ” পদটি এখানে আলাদা কোনো নিয়ম ছাড়াই এল: হরে (1 − 3x)-এর বর্গ মানেই সহগে n-এর একটি ঘাত। ভাবনার প্রশ্ন ৪-এ এর সাধারণ যুক্তি আছে।

যুক্তির ভুল ধরুন: “1/(1 − x)³-এর সহগ”

একজন লিখলেন: “উপপাদ্য ২.২-এ n = 3, তাই 1/(1 − x)³-এর x^k-এর সহগ C(k + 3, k). তাই x₁ + x₂ + x₃ = 5-এর অঋণাত্মক সমাধান C(8, 5) = 56টি।”

ভুল কোথায়: সূত্রটি C(n + k − 1, k), n + k নয়। n = 3-এ C(k + 2, k) = C(k + 2, 2), তাই সঠিক উত্তর C(7, 2) = 21. ছোট মানে পরীক্ষা করলেই ধরা পড়ে: k = 1-এ (1 + x + ⋯)³-এ x-এর সহগ 3 (কোন গুণনীয়ক থেকে x আসবে), কিন্তু ভুল সূত্র C(4, 1) = 4 দেয়। Off-by-one ভুল এড়াতে প্রতিটি সূত্র k = 0 আর k = 1-এ মিলিয়ে নিন।

১০ · AI-এর যুগে — generating function-এর হিসাব যাচাই

Generating function-এর হিসাবে অনেক ছোট বীজগাণিতিক ধাপ, আর প্রতিটিতে একটি চিহ্ন বা সূচক উল্টে যেতে পারে। AI সহকারী এসব হিসাব আত্মবিশ্বাসের সঙ্গে লেখে, কিন্তু কয়েকটি ভুল নিয়মিত দেখা যায়:

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

• পাওয়া generating function থেকে প্রথম ৫–১০টি সহগ বের করে recurrence বা brute force-এর সঙ্গে মিলিয়েছি
• প্রতিটি ভাগে হরের ধ্রুবক পদ অশূন্য কি না দেখেছি
• শুরুর মানগুলো, বিশেষত a₀, ঠিক জায়গায় ঢুকেছে কি না দেখেছি
• C(n + k − 1, k)-এর মতো সূত্র k = 0, 1-এ হাতে পরীক্ষা করেছি
• প্রশ্নে লেবেল আছে কি না দেখে OGF বা EGF বাছাই মিলিয়েছি
• উদ্ধৃত সাল আর নাম বিশ্বস্ত উৎসে মিলিয়েছি

এই পর্বের সব হিসাব আসলে দুটি নিয়মের ওপর দাঁড়িয়ে: গুণফল মানে convolution, আর ধ্রুবক পদ অশূন্য হলে ভাগ বৈধ। AI-এর উত্তর পড়ার সময় প্রতিটি ধাপে জিজ্ঞেস করুন এই দুটির কোনটি খাটানো হলো, আর তারপর একটি ছোট Python list দিয়ে সহগগুলো মিলিয়ে নিন। দশ লাইনের কোড বেশিরভাগ ভুল ধরে ফেলে।