বিশেষ সংখ্যা — Catalan, Stirling আর partition

১ · বল-বাক্সের অসমাপ্ত ঘর — কেন “বিশেষ” সংখ্যা

পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই — stars and bars আর multinomial”-এ n-টি বল k-টি বাক্সে রাখার ১২ রকম প্রশ্নের একটি সারণি দেখেছেন, যার নাম twelvefold way. ওপরের দুই সারিতে (বাক্সগুলো আলাদা) প্রতিটি ঘরে একটি পরিষ্কার সূত্র ছিল: kⁿ, C(n + k − 1, n), C(k, n) ইত্যাদি। নিচের দুই সারিতে (বাক্সগুলো একই রকম) লেখা ছিল শুধু “পর্ব ৫০”. এই পর্বে সেই ঘরগুলো পূরণ হবে।

তিনটি প্রশ্ন, তিনটি সংখ্যা-পরিবার। প্রথমটির উত্তর 7, দ্বিতীয় ধরনের Stirling সংখ্যা S(4, 2) (§৩)। দ্বিতীয়টির উত্তর 11, প্রথম ধরনের Stirling সংখ্যা c(4, 2) (§৫)। তৃতীয়টির উত্তর 2, ৪-এর ঠিক দুই অংশের partition (§৬)। তিনটির কোনোটিরই C(n, k)-এর মতো একটি সরল গুণফল-সূত্র নেই, কারণ “নামহীন দল” মানে ভাগ (division rule, পর্ব ৩১) দিয়ে সরল করা যায় না: সব দলের আকার সমান না হলে একটি ভাগ কতবার গোনা হলো, তা ভাগভেদে আলাদা।

তাহলে পথ কী? প্রতিটি পরিবারের জন্য একটি recurrence, যা একটি নির্দিষ্ট উপাদানকে (“শেষ গ্রাহক”, “সবচেয়ে ছোট অংশ”) আলাদা করে ধরে ছোট প্রশ্নে নামায়, আর তার একটি combinatorial proof. পর্ব ৪৪ থেকে ৪৮ পর্যন্ত recurrence মডেল করা আর সমাধানের যে কৌশল শিখেছেন, এখানে উল্টো ছবি: অনেক সময় closed form নেই, তাই recurrence-ই সংখ্যাটির সবচেয়ে কাজের সংজ্ঞা। সারণি বানাতে হয় dynamic programming-এর মতো ঘর ধরে ধরে।

এই পর্বের পথ। প্রথমে পুরোনো বন্ধু Catalan (§২), তারপর দলে ভাগ: S(n, k) আর Bell সংখ্যা (§৩–৪), তারপর cycle আর গোল টেবিল (§৫), তারপর partition, Ferrers diagram আর pentagonal উপপাদ্য (§৬–৭)। শেষে সব মিলিয়ে twelvefold way-এর পূর্ণ সারণি (§৮) আর পরীক্ষার অঙ্ক (§৯)।

২ · Catalan ফিরে দেখা — একই সংখ্যা, নতুন চেহারা

Catalan সংখ্যা C_n এর আগে দুইবার এসেছে। পর্ব ৩৭ “গণনার কৌশল — lattice path, bijection আর double counting”-এ reflection principle দিয়ে কর্ণ না পেরোনো পথ গুনে প্রমাণ হয়েছে C_n = C(2n, n) − C(2n, n + 1) = C(2n, n)/(n + 1), আর মেলানো বন্ধনী, binary tree আর বহুভুজের triangulation একই সংখ্যায় গোনা যায় দেখানো হয়েছে। পর্ব ৪৮ “Generating function — গণনাকে বীজগণিতে রূপান্তর”-এ C(x) = 1 + xC(x)² সমীকরণ থেকে একই সূত্র বীজগণিতে এসেছে। সেই প্রমাণগুলো এখানে আবার করা হবে না। এই অংশে তিনটি নতুন জিনিস: একটি ধারাবাহিক গুণের সূত্র, দুটি নতুন চেহারা, আর একটি চেনার কৌশল।

1. C_n+1 = (2n + 2)!/((n + 1)!(n + 1)!(n + 2)) আর C_n = (2n)!/(n! n! (n + 1)). — closed form
2. ভাগ করলে C_n+1/C_n = (2n + 2)(2n + 1)(n + 1)/((n + 1)(n + 1)(n + 2)). — factorial কাটাকাটি
3. 2n + 2 = 2(n + 1), তাই অনুপাত = 2(2n + 1)/(n + 2). ∎ — সরল করা

এই সূত্রে C_n বের করতে শুধু n-টি গুণ-ভাগ লাগে, convolution-এর n² নয়: C₅ = 2 · 9 · 14/6 = 42. অনুপাত 2(2n + 1)/(n + 2) বড় n-এ 4-এর দিকে যায়, তাই C_n মোটামুটি 4ⁿ-এর মতো বাড়ে (পর্ব ৪৮-এর “আরও গভীরে” অংশে এর নিখুঁত রূপ আছে)। প্রতিটি ধাপে ভাগফল পূর্ণসংখ্যা হবেই, কারণ বাঁ পাশ একটি গণনা।

নতুন চেহারা ১: না-কাটা করমর্দন। বাজারঘরের বার্ষিক সভায় একটি গোল টেবিলে 2n জন বসেছেন। সবাই একসঙ্গে ঠিক একজনের সঙ্গে হাত মেলাবেন, আর টেবিলের ওপর দিয়ে কোনো দুটি হাত একে অন্যকে কাটবে না। কয় উপায়ে? n = 3-এ (৬ জন) উত্তর ৫।

1. ১ নম্বর আসন যাঁর সঙ্গে হাত মেলান, তিনি আসন m. ১ আর m-এর হাত টেবিলকে দুই ভাগ করে; একদিকের কেউ অন্যদিকের কারও সঙ্গে হাত মেলালে হাত কাটবে। — জ্যামিতি
2. তাই দুই পাশের প্রতিটিতে জোড় সংখ্যক মানুষ থাকতে হবে: m = 2j, একপাশে 2(j − 1) জন, অন্যপাশে 2(n − j) জন। — প্রত্যেকের একজন সঙ্গী
3. দুই পাশ স্বাধীনভাবে একই প্রশ্নের ছোট রূপ, তাই উপায় h_j−1h_n−j. j = 1…n যোগ করলে h_n = ∑ h_j−1h_n−j, h₀ = 1. — যোগ ও গুণের নিয়ম
4. এটি হুবহু Catalan-এর recurrence, আর শুরুর মান একই, তাই strong induction অনুযায়ী (পর্ব ১১) h_n = C_n. ∎ — একই recurrence, একই শুরু

নতুন চেহারা ২: matrix গুণের বন্ধনী। A₁A₂⋯A_n+1 গুণফলে বন্ধনী বসানোর উপায় C_n: শেষ গুণটি কোথায় হয়, তা ধরে ভাঙলে বাঁ অংশে i + 1টি আর ডান অংশে n − iটি matrix, আবার একই recurrence. ৪টি matrix-এ C₃ = 5 রকম বন্ধনী, যার প্রতিটির খরচ আলাদা হতে পারে; সবচেয়ে সস্তাটি খোঁজার DP পাবেন DSA কোর্সের পর্ব ৫৪-এ। সব বন্ধনী একে একে পরীক্ষা করা অচল, কারণ C_n প্রায় 4ⁿ-এর হারে বাড়ে।

চেনার কৌশল। একটি নতুন গণনার প্রশ্নে প্রথম কয়েকটি মান 1, 1, 2, 5, 14 এলে Catalan সন্দেহ করুন, তারপর প্রমাণ খুঁজুন: “প্রথম বস্তুটি কার সঙ্গে জোড়া” ধরে ভাঙলে কি দুটি স্বাধীন, একই ধরনের ছোট অংশ থাকে? থাকলে recurrence মিলবে। শুধু প্রথম চারটি মান মেলা প্রমাণ নয়: 1, 1, 2, 5-এর পরে 14 না এসে 15 আসে Bell সংখ্যায় (§৪)। এই ফাঁদটি §৯-এ আবার আসবে।

৩ · দ্বিতীয় ধরনের Stirling সংখ্যা — নামহীন দলে ভাগ

ছোট মানগুলো হাতে বের হয়। S(n, 1) = 1 (সবাই এক দলে), S(n, n) = 1 (প্রত্যেকে একা)। S(n, n − 1)-এ ঠিক একটি দলে দুজন, বাকিরা একা, তাই S(n, n − 1) = C(n, 2). আর S(n, 2): প্রতিটি উপাদানকে “দল A” বা “দল B”-তে দেওয়ার 2ⁿ উপায় থেকে দুটি একতরফা বাদ দিয়ে, নাম মুছতে 2 দিয়ে ভাগ: (2ⁿ − 2)/2 = 2ⁿ⁻¹ − 1. এখানে ভাগ বৈধ, কারণ দুটি দলই অশূন্য আর ভিন্ন, তাই প্রতিটি ভাগ ঠিক দুবার গোনা হয়। চার প্যাকারের প্রশ্নে S(4, 2) = 2³ − 1 = 7.

1. {1, …, n}-এর k-অংশের সব partition নিন, আর শেষ উপাদান n কোথায় আছে দেখুন। দুটি পরস্পর বিচ্ছিন্ন ক্ষেত্র: n একা একটি অংশে, অথবা n অন্তত আরেকজনের সঙ্গে। — যোগের নিয়ম
2. n একা থাকলে তাকে সরিয়ে দিলে বাকি {1, …, n − 1}-এর একটি (k − 1)-অংশের partition থাকে, আর উল্টো দিকে যেকোনো এমন partition-এ {n} যোগ করে ফেরত আসা যায়। এটি একটি bijection, তাই এই ক্ষেত্রে S(n − 1, k − 1) উপায়। — bijection
3. n অন্যদের সঙ্গে থাকলে n-কে সরালে {1, …, n − 1}-এর একটি k-অংশের partition থাকে (n-এর অংশটি খালি হয় না)। উল্টো দিকে এমন যেকোনো partition-এর k-টি অংশের যেকোনো একটিতে n ঢোকানো যায়, আর ভিন্ন অংশে ঢোকালে ভিন্ন ফল। — ফেরত পথ
4. অংশগুলোর নাম না থাকলেও (n − 1)-এর partition-টি স্থির হলে তার k-টি অংশ আলাদা সেট, তাই “কোন অংশে n” প্রশ্নের ঠিক k-টি উত্তর। এই ক্ষেত্রে k · S(n − 1, k) উপায়। — গুণের নিয়ম
5. দুই ক্ষেত্র যোগ করলে সূত্রটি পাওয়া যায়। ∎ — যোগের নিয়ম

ধাপ ৪-এর যুক্তিটি সূক্ষ্ম, আর §৯-এর ভুল প্রমাণটি ঠিক এখানেই হোঁচট খায়: “নামহীন দল” মানে সব দল মিলে একটি সেট, কিন্তু একবার partition ঠিক হয়ে গেলে প্রতিটি দলকে তার সদস্য দিয়ে চেনা যায়। নিচের stepper সারণিটি সারি ধরে বানায়।

1S(n,1) = 1, S(n,n) = 12সারি 2: S(2,1)=1, S(2,2)=13S(3,2) = 2·S(2,2) + S(2,1)4S(4,2) = 2·S(3,2) + S(3,1)5অর্থ: 4 একা, বা দলে ঢোকে6তালিকা: ৭টি ভাগ ✓

Onto ফাংশনের সঙ্গে সম্পর্ক। n-টি আলাদা অর্ডার k জন নামসহ রাইডারের মধ্যে ভাগ, প্রত্যেকে অন্তত একটি: আগে নামহীন k দলে ভাগ (S(n, k)), তারপর দলগুলো k জনকে k! উপায়ে দেওয়া। তাই onto ফাংশনের সংখ্যা k! · S(n, k). পর্ব ১৬-এ এই গণনা পরে করার কথা ছিল; পর্ব ৪৯ “Inclusion–exclusion আর derangement”-এ এর ∑(−1)^jC(k, j)(k − j)ⁿ সূত্র প্রমাণ হচ্ছে, তাই S(n, k)-এর একটি স্পষ্ট সূত্রও আছে, শুধু তাতে বিকল্প চিহ্নের যোগফল।

1. x একটি ধনাত্মক পূর্ণসংখ্যা হলে বাঁ পাশ {1, …, n} থেকে {1, …, x}-এ সব ফাংশনের সংখ্যা। — গুণের নিয়ম (পর্ব ১৬)
2. প্রতিটি ফাংশনের “একই মানে যাওয়া উপাদানগুলো” মিলে {1, …, n}-এর একটি partition, ধরুন k অংশের; ফাংশনটি জানা মানে এই partition আর k-টি অংশকে k-টি ভিন্ন মান দেওয়া। — ফাংশনকে ভাঙা
3. k-টি অংশকে ভিন্ন মান দেওয়ার উপায় falling factorial x(x − 1)⋯(x − k + 1), তাই k অনুযায়ী যোগ করে দুই পাশ সমান। — যোগ ও গুণের নিয়ম
4. দুই পাশই degree n-এর polynomial, আর অসীম সংখ্যক x-এ সমান, তাই তাদের পার্থক্যের অসীম মূল; শূন্য ছাড়া কোনো polynomial-এর তা থাকে না। ∎ — polynomial-এর মূলের সংখ্যা

উদাহরণ x = 5, n = 4: 1 · 5 + 7 · 20 + 6 · 60 + 1 · 120 = 625 = 5⁴. এই অভেদ কাজে লাগে ∑k^m ধরনের যোগফলে: falling factorial-এর যোগফল সহজ (hockey-stick ধাঁচে), তাই আগে x^m-কে falling factorial-এ ভাঙা হয়।

৪ · Bell সংখ্যা — সব রকম দলভাগ

দলের সংখ্যা নির্দিষ্ট না থাকলে? বাজারঘর পাঁচজন নতুন গ্রাহককে “পছন্দ মিলে এমন” দলে ভাগ করবে, কয়টি দল তা আগে থেকে ঠিক নেই। সব k-এর জন্য যোগ করলে পাওয়া যায় Bell সংখ্যা:

B(n) = ∑_k=0ⁿ S(n, k): 1, 1, 2, 5, 15, 52, 203, 877, 4140, …

B(4) = 1 + 7 + 6 + 1 = 15, আর B(5) = 1 + 15 + 25 + 10 + 1 = 52. সারণি না বানিয়েও B(n) বের করার একটি নিজস্ব recurrence আছে।

1. {1, …, n + 1}-এর একটি partition নিন, আর n + 1 যে অংশে আছে, তাকে বলুন “বিশেষ অংশ”. — একটি উপাদান আলাদা করে ধরা
2. বিশেষ অংশের বাইরে থাকা উপাদানের সংখ্যা k ধরুন (0 ≤ k ≤ n). কোন k-টি উপাদান বাইরে, তা {1, …, n} থেকে C(n, k) উপায়ে বাছা যায়; বাকি n − k-টি n + 1-এর সঙ্গে বিশেষ অংশে। — বাছাই
3. বাইরের k-টি উপাদান নিজেরা যেকোনোভাবে ভাগ হতে পারে: B(k) উপায় (k = 0 হলে B(0) = 1, “কিছু ভাগ না করা”)। — সংজ্ঞা
4. বাছাই আর ভাগ মিলে partition-টি অনন্যভাবে ফেরত আসে, তাই k অনুযায়ী যোগ করে সূত্রটি পাওয়া যায়। ∎ — যোগ ও গুণের নিয়ম

যাচাই: B(4) = C(3, 0)B(0) + C(3, 1)B(1) + C(3, 2)B(2) + C(3, 3)B(3) = 1 + 3 + 6 + 5 = 15. খেয়াল করুন, Catalan-এর recurrence-এ দুটি ছোট অংশ “গুণ” হয়, এখানে একটি বাছাই আর একটি ছোট অংশ; তাই Bell সংখ্যা Catalan-এর চেয়ে অনেক দ্রুত বাড়ে (C₁₀ = 16796, কিন্তু B(10) = 115975).

এখন দুটি সারণিই brute force দিয়ে যাচাই করা যাক। একটি partition হাতে বানানোর বদলে নিচের কোড {0, …, n − 1} থেকে নিজের মধ্যে সব ফাংশন নেয়, আর প্রতিটির “একই মানে যাওয়া উপাদানগুলো” দিয়ে partition বানায় (উপপাদ্য ৩.৩-এর প্রমাণের ধাপ ২)। একই partition অনেক ফাংশন থেকে আসে, তাই একটি সেটে জমিয়ে আলাদাগুলো গোনা হয়। n = 6-এ 6⁶ = 46656টি ফাংশন; এর বেশি নিলে ব্রাউজারে ধীর হবে, brute force-এর সীমা এখানেই। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
from math import comb

N = 10
S = [[0] * (N + 1) for _ in range(N + 1)]
S[0][0] = 1
for n in range(1, N + 1):
    for k in range(1, n + 1):
        S[n][k] = k * S[n - 1][k] + S[n - 1][k - 1]
for n in range(1, 7):
    print(f"n={n}:", S[n][1:n + 1])

def brute(n):                # every map {0..n-1} -> {0..n-1}
    seen = set()             # its fibres form a set partition
    for f in product(range(n), repeat=n):
        blocks = {}
        for i, v in enumerate(f):
            blocks.setdefault(v, []).append(i)
        seen.add(frozenset(tuple(b) for b in blocks.values()))
    count = [0] * (n + 1)
    for p in seen:
        count[len(p)] += 1
    return count

bf = {n: brute(n) for n in range(1, 7)}
print("brute == table for n <= 6:",
      all(bf[n] == S[n][:n + 1] for n in range(1, 7)))

B = [1]
for n in range(N):           # B(n+1) = sum C(n,k) B(k)
    B.append(sum(comb(n, k) * B[k] for k in range(n + 1)))
print("Bell by recurrence:", B)
print("Bell = row sums   :", [sum(S[n]) for n in range(N + 1)])
print("brute force Bell  :", [sum(bf[n]) for n in range(1, 7)])

n=1: [1]
n=2: [1, 1]
n=3: [1, 3, 1]
n=4: [1, 7, 6, 1]
n=5: [1, 15, 25, 10, 1]
n=6: [1, 31, 90, 65, 15, 1]
brute == table for n <= 6: True
Bell by recurrence: [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]
Bell = row sums   : [1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975]
brute force Bell  : [1, 2, 5, 15, 52, 203]

৫ · প্রথম ধরনের Stirling সংখ্যা — cycle আর গোল টেবিল

একটি permutation σ-কে তীর হিসেবে আঁকুন: i থেকে σ(i)-তে তীর। প্রতিটি উপাদান থেকে ঠিক একটি তীর বের হয় আর একটি ঢোকে, তাই তীর ধরে হাঁটলে একসময় শুরুর জায়গায় ফেরত আসতেই হয়। এভাবে উপাদানগুলো কয়েকটি বৃত্তে ভাগ হয়, প্রতিটিকে বলে একটি cycle. যেমন {1, …, 6}-এ σ = (1 3 5)(2 6)(4) মানে 1 → 3 → 5 → 1, 2 → 6 → 2, আর 4 নিজের জায়গায় (একটি fixed point, পর্ব ৪০)। একটি cycle হলো একটি গোল টেবিল: (1 3 5) আর (3 5 1) একই বসার ব্যবস্থা, কারণ প্রত্যেকের ডানের মানুষ একই।

ছোট মান: c(n, n) = 1 (প্রত্যেকে একা, identity permutation). c(n, 1) = (n − 1)!: একটি গোল টেবিলে n জন, ১ নম্বরকে স্থির ধরে বাকিদের (n − 1)! বিন্যাস (পর্ব ৩১-এর circular permutation). আর ∑_k c(n, k) = n!, কারণ প্রতিটি permutation-এর কোনো একটি cycle-সংখ্যা আছে। চার প্যাকারের দুই গোল টেবিল: c(4, 2) = 11 (তিনজন এক টেবিলে: 4 × 2 = 8 রকম, দুজন-দুজন: 3 রকম)।

1. শেষ অতিথি n-কে দেখুন: হয় তিনি একা একটি টেবিলে (n একটি fixed point), নয়তো অন্যদের সঙ্গে। — যোগের নিয়ম
2. একা হলে তাঁকে সরালে বাকি n − 1 জনের k − 1 টেবিলের একটি ব্যবস্থা; এটি bijection, তাই c(n − 1, k − 1) উপায়। — bijection
3. অন্যদের সঙ্গে থাকলে n-কে উঠিয়ে দিন (তাঁর বাঁয়ের মানুষ এখন সরাসরি তাঁর ডানের মানুষের পাশে); বাকি n − 1 জনের k টেবিলের একটি ব্যবস্থা থাকে। — cycle থেকে উপাদান মোছা
4. উল্টো দিকে n-কে বসানো যায় বাকি n − 1 জনের যেকোনো একজনের ঠিক ডানে, আর প্রতিটি পছন্দ ভিন্ন ব্যবস্থা দেয়: n − 1 উপায়। তাই এই ক্ষেত্রে (n − 1) · c(n − 1, k). — গুণের নিয়ম
5. দুই ক্ষেত্র যোগ করলে সূত্রটি আসে। ∎ — যোগের নিয়ম

S(n, k)-এর recurrence-এর সঙ্গে তুলনা করুন: সেখানে গুণক k (কোন দলে ঢুকবে), এখানে n − 1 (কোন মানুষের পাশে বসবে)। দল শুধু সদস্য দিয়ে চেনা যায়, টেবিলে বসার ক্রমও গোনে।

1. বাঁ পাশকে R_n(x) বলুন; R₀ = 1 আর R_n(x) = R_n−1(x) · (x + n − 1). — সংজ্ঞা
2. R_n−1-এর x^k-এর সহগ c(n − 1, k) ধরে (induction hypothesis), R_n-এর x^k-এর সহগ = c(n − 1, k − 1) (x দিয়ে গুণ থেকে) + (n − 1)c(n − 1, k) (n − 1 দিয়ে গুণ থেকে)। — polynomial গুণ
3. উপপাদ্য ৫.২ অনুযায়ী এটি c(n, k), আর ভিত্তি n = 0 সত্য। ∎ — induction (পর্ব ১০)

উদাহরণ: x(x + 1)(x + 2)(x + 3) = x⁴ + 6x³ + 11x² + 6x, সহগগুলো c(4, ·) = 6, 11, 6, 1. x-এর জায়গায় −x বসালে চিহ্নসহ (signed) Stirling সংখ্যা আসে, যা উপপাদ্য ৩.৩-এর উল্টো দিক: falling factorial-কে ঘাতে ভাঙে। Knuth-এর বইয়ে c(n, k)-কে বন্ধনীর ভেতরে n-এর নিচে k লিখে প্রকাশ করা হয়; বই ভেদে প্রতীক বদলায়, তাই কোন বই unsigned আর কোন বই signed অর্থে লিখছে, তা দেখে নিন।

Harmonic number ফিরে আসে। পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”-এ harmonic number H_n = 1 + 1/2 + ⋯ + 1/n এসেছিল record-এর প্রত্যাশিত সংখ্যা আর coupon collector-এ। এখানে দুটি নতুন রূপ:

1. c(n + 1, 2) = n! · H_n. R_n+1(x) = x · (x + 1)⋯(x + n)-এ x²-এর সহগ = (x + 1)⋯(x + n)-এ x-এর সহগ, অর্থাৎ প্রতিটি গুণনীয়ক থেকে একবার x নিয়ে বাকিদের ধ্রুবক গুণ: ∑_j=1ⁿ n!/j = n! H_n. যেমন c(4, 2) = 6 · 11/6 = 11.
2. এলোমেলো permutation-এ গড় cycle-সংখ্যা H_n. গড় = ∑ k c(n, k)/n! = R_n′(1)/R_n(1). R_n(1) = n!, আর গুণফলের derivative-এর নিয়মে R_n′(1)/R_n(1) = ∑_j=0ⁿ⁻¹ 1/(1 + j) = H_n. ১০০০ জনের permutation-এ গড়ে মাত্র ৭.৫টির মতো cycle.

পর্ব ৪০-এর record আর এখানকার cycle-এর গড় একই H_n হওয়া কাকতালীয় নয়: k-টি record আছে এমন permutation-এর সংখ্যাও c(n, k), যা একটি সুন্দর bijection (Foata-র নামে পরিচিত) দেখায়। প্রমাণটি এখানে বাদ রাখা হলো।

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

N = 8
c = [[0] * (N + 1) for _ in range(N + 1)]
c[0][0] = 1
for n in range(1, N + 1):
    for k in range(1, n + 1):
        c[n][k] = (n - 1) * c[n - 1][k] + c[n - 1][k - 1]
def cycles(p):                       # number of cycles of a permutation
    seen, count = set(), 0
    for start in range(len(p)):
        count += start not in seen   # a new cycle starts here
        j = start
        while j not in seen:
            seen.add(j)
            j = p[j]
    return count
for n in range(1, 7):
    cnt = [0] * (n + 1)
    for p in permutations(range(n)):
        cnt[cycles(p)] += 1
    print(f"n={n} brute {cnt[1:]}  recurrence {c[n][1:n + 1]}")

poly = [1]                           # x(x+1)...(x+5), lowest power first
for j in range(6):                   # multiply by (x + j)
    poly = [(poly[i - 1] if i else 0) + j * (poly[i] if i < len(poly) else 0)
            for i in range(len(poly) + 1)]
print("coefficients of x(x+1)...(x+5):", poly[1:])

for n in (4, 6, 8):
    H = sum(Fraction(1, j) for j in range(1, n + 1))
    mean = Fraction(sum(k * c[n][k] for k in range(n + 1)), factorial(n))
    print(f"n={n}: mean number of cycles {mean}, H_n = {H}")

n=1 brute [1]  recurrence [1]
n=2 brute [1, 1]  recurrence [1, 1]
n=3 brute [2, 3, 1]  recurrence [2, 3, 1]
n=4 brute [6, 11, 6, 1]  recurrence [6, 11, 6, 1]
n=5 brute [24, 50, 35, 10, 1]  recurrence [24, 50, 35, 10, 1]
n=6 brute [120, 274, 225, 85, 15, 1]  recurrence [120, 274, 225, 85, 15, 1]
coefficients of x(x+1)...(x+5): [120, 274, 225, 85, 15, 1]
n=4: mean number of cycles 25/12, H_n = 25/12
n=6: mean number of cycles 49/20, H_n = 49/20
n=8: mean number of cycles 761/280, H_n = 761/280

৬ · Integer partition আর Ferrers diagram

এবার বলগুলোও অভিন্ন। বাজারঘরের গুদামে n কেজি চাল যেকোনো মাপের প্যাকেটে ভরা হবে, আর প্যাকেটগুলো একই রকম দেখতে; শুধু কোন কোন মাপের প্যাকেট, সেটিই তথ্য। এটি n-এর একটি partition: n-কে ধনাত্মক পূর্ণসংখ্যার যোগফলে লেখা, যেখানে ক্রম গুরুত্বহীন। প্রথা হিসেবে অংশগুলো বড় থেকে ছোট ক্রমে লেখা হয়, যেমন 5 + 3 + 1. সব partition-এর সংখ্যা p(n): p(4) = 5, p(7) = 15. পর্ব ৪৮-এ দেখেছেন ∑p(n)xⁿ = ∏1/(1 − x^k), আর Euler-এর “আলাদা অংশ = বিজোড় অংশ” উপপাদ্যের generating function প্রমাণ; সেগুলো এখানে আবার হবে না। এই অংশের হাতিয়ার একটি ছবি।

1λ = 5+3+1, সারি আঁকা2কলাম 1: কয়টি অংশ ≥ 1?3কলাম 2, 3: অংশ ≥ 2, ≥ 34কলাম 4, 5: অংশ ≥ 4, ≥ 55λ′ = 3+2+2+1+1, λ″ = λ

1. Conjugation একটি partition-কে n-এরই আরেকটি partition-এ নেয়, কারণ ছবি উল্টালে বিন্দুর সংখ্যা বদলায় না। — বিন্দু গোনা
2. λ-এর অংশের সংখ্যা = ছবির সারির সংখ্যা = প্রথম কলামের দৈর্ঘ্য = λ′-এর সবচেয়ে বড় অংশ। — সংজ্ঞা ৬.১
3. দুবার উল্টালে মূল ছবি, তাই conjugation নিজের inverse, অর্থাৎ bijection. — involution
4. তাই “বড়জোর k অংশ”-এর সেটকে conjugation এক-এক ও সম্পূর্ণভাবে “সবচেয়ে বড় অংশ ≤ k”-এর সেটে নেয়; দুই সেটের আকার সমান। ∎ — bijective proof

উদাহরণ n = 8, k = 3: বড়জোর ৩ অংশের partition ১০টি, আর ১, ২, ৩ দিয়ে তৈরি partition-ও ১০টি (§৯-এ তালিকা)। Generating function-এর ভাষায় এর অর্থ: অংশ ≤ k-এর partition গোনে ∏_j=1^k 1/(1 − x^j), অর্থাৎ শুধু ১, ২, …, k টাকার কয়েনে খুচরো (পর্ব ৪৮)। তাই “বড়জোর k অংশ”-এর প্রশ্নও একই কয়েন-গণনা।

ঠিক k অংশের recurrence. p_k(n) = n-এর ঠিক k অংশের partition-এর সংখ্যা ধরুন। তাহলে n ≥ k ≥ 1-এ

p_k(n) = p_k−1(n − 1) + p_k(n − k)

প্রমাণ দুই ক্ষেত্রে: সবচেয়ে ছোট অংশ যদি 1 হয়, সেটি মুছলে n − 1-এর ঠিক k − 1 অংশের partition (bijection). নইলে সব অংশ ≥ 2, তখন প্রতিটি অংশ থেকে 1 করে বাদ দিলে (ছবির প্রথম কলাম মুছলে) n − k-এর ঠিক k অংশের partition, আর উল্টো দিকে প্রতিটি অংশে 1 যোগ করে ফেরত। শুরুর মান p₀(0) = 1, আর n < k হলে p_k(n) = 0. উদাহরণ: p₃(7) = p₂(6) + p₃(4) = 3 + 1 = 4 (5+1+1, 4+2+1, 3+3+1, 3+2+2). ∎

৭ · Pentagonal উপপাদ্য আর p(n)-এর দ্রুত হিসাব

p(n)-এর কোনো সরল closed form নেই, আর brute force-এ তালিকা বানানো দ্রুত অচল হয়: p(100) প্রায় ১৯ কোটি। পর্ব ৪৮-এর গুণফল ∏1/(1 − x^k) দিয়ে x^N পর্যন্ত হিসাবে মোটামুটি N² কাজ লাগে। Euler এর চেয়েও দ্রুত একটি পথ দেন, যা আসে গুণফলের উল্টো থেকে।

নামটি এসেছে এখান থেকে: j = 1, 2, 3-এ j(3j − 1)/2 = 1, 5, 12, যা পঞ্চভুজ আকারে সাজানো বিন্দুর সংখ্যা। ঋণাত্মক j থেকে আসে 2, 7, 15. প্রমাণটি এখানে বাদ রাখা হলো; বাম পাশ খুললে xⁿ-এর সহগ = (জোড় সংখ্যক আলাদা অংশে n-এর partition) − (বিজোড় সংখ্যক আলাদা অংশে n-এর partition), আর F. Franklin-এর ১৮৮১ সালের একটি bijection দেখায় যে এই দুই দল প্রায় সবসময় সমান আকারের, শুধু pentagonal n-এ একটি বাড়তি থাকে। বক্তব্যটি আমরা n ≤ 40-এ যাচাই করব। এখন উপপাদ্য থেকে recurrence:

1. P(x) = ∑p(n)xⁿ = ∏1/(1 − x^k), তাই P(x) · ∏(1 − x^k) = 1. — পর্ব ৪৮-এর partition generating function
2. উপপাদ্য ৭.১ বসালে P(x) · (1 − x − x² + x⁵ + x⁷ − ⋯) = 1. — pentagonal উপপাদ্য
3. n ≥ 1-এ ডান পাশের xⁿ-এর সহগ 0, আর বাঁ পাশে convolution: p(n) − p(n − 1) − p(n − 2) + p(n − 5) + p(n − 7) − ⋯ = 0. — সহগ মেলানো
4. p(n) বাদে বাকি পদ ডানে নিলে সূত্রটি আসে। ∎ — পক্ষান্তর

চিহ্নের ধাঁচ মনে রাখুন: দুটি যোগ, দুটি বিয়োগ, আবার দুটি যোগ (+ + − − + + − −)। প্রতি জোড়ায় j আর −j-এর দুটি pentagonal সংখ্যা। n-এর নিচে generalized pentagonal সংখ্যা মোটামুটি √n-এর মতো, তাই প্রতিটি p(n)-এ প্রায় √n-টি পদ, আর p(0…N) মিলে প্রায় N^1.5 কাজ।

1p(n) = ∑ ± p(n − g)2g ≤ 7: 1, 2, 5, 73+p(6) + p(5) = 11 + 74−p(2) − p(0) = −2 − 15p(7) = 18 − 3 = 156১৫টি partition তালিকা ✓

নিচের ব্লক recurrence দিয়ে p(0…200) বের করে, n ≤ 40-এ প্রতিটি partition তালিকা করে মেলায় (p(40) = 37338টি তালিকা, brute force-এর সীমা প্রায় এখানেই), উপপাদ্য ৬.২ n ≤ 15-এ সব k-তে যাচাই করে, আর Hardy–Ramanujan-এর আনুমানিক সূত্রের সঙ্গে তুলনা করে।

from math import exp, pi, sqrt

def p_pentagonal(N):
    p = [1] + [0] * N
    for n in range(1, N + 1):
        k, total = 1, 0
        while k * (3 * k - 1) // 2 <= n:
            sign = 1 if k % 2 else -1          # + + - - + + - - ...
            for g in (k * (3 * k - 1) // 2, k * (3 * k + 1) // 2):
                if g <= n:
                    total += sign * p[n - g]
            k += 1
        p[n] = total
    return p

def brute(n, largest):                       # list every partition
    if n == 0:
        return [[]]
    return [[k] + rest for k in range(min(n, largest), 0, -1)
            for rest in brute(n - k, k)]

p = p_pentagonal(200)
print("p(0..15):", p[:16])
print("pentagonal == brute for n <= 40:",
      all(p[n] == len(brute(n, n)) for n in range(41)))
ok = all(sum(len(q) <= k for q in brute(n, n)) == len(brute(n, k))
         for n in range(1, 16) for k in range(1, n + 1))
print("<= k parts == parts <= k (n <= 15):", ok)
print("p(100) =", p[100], "  p(200) =", p[200])
for n in (10, 100, 200):
    hr = exp(pi * sqrt(2 * n / 3)) / (4 * n * sqrt(3))
    print(f"n={n}: Hardy-Ramanujan {hr:.4g}, ratio {hr / p[n]:.4f}")
print("p(5k+4) % 5 == 0 for 5k+4 <= 200:",
      all(p[n] % 5 == 0 for n in range(4, 201, 5)))

p(0..15): [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176]
pentagonal == brute for n <= 40: True
<= k parts == parts <= k (n <= 15): True
p(100) = 190569292   p(200) = 3972999029388
n=10: Hardy-Ramanujan 48.1, ratio 1.1453
n=100: Hardy-Ramanujan 1.993e+08, ratio 1.0457
n=200: Hardy-Ramanujan 4.1e+12, ratio 1.0320
p(5k+4) % 5 == 0 for 5k+4 <= 200: True

৮ · কোন সংখ্যা কী গোনে — twelvefold way সম্পূর্ণ

এখন পর্ব ৩৫-এর সারণির ফাঁকা ঘরগুলো পূরণ করা যায়। প্রতিটি ঘরের পাশে n = 5 বল আর k = 3 বাক্সের মান দেওয়া হলো (scratch-এ brute force দিয়ে প্রতিটি মেলানো)।

গাঢ় চারটি ঘর এই পর্বের। নিচের-বাঁ ঘর 5 = 5, 4+1, 3+2, 3+1+1, 2+2+1 (বড়জোর ৩ অংশ), আর নিচের-ডান 2 = 3+1+1, 2+2+1. আরেকটি জিনিস লক্ষ করুন: একই বাক্সের ঘর থেকে আলাদা বাক্সের ঘরে যেতে k! দিয়ে গুণ কাজ করে শুধু “≥ ১টি” কলামে, কারণ সেখানে সব বাক্স অশূন্য বলে আলাদা; “যেকোনোভাবে” কলামে খালি বাক্সগুলো অদলবদলে নতুন কিছু হয় না, তাই সেখানে এই গুণ ভুল (41 × 6 ≠ 243).

পুরো মডিউলের “বিশেষ সংখ্যা” এক জায়গায়:

Derangement-এর recurrence আর তার প্রমাণ পর্ব ৪৯-এর বিষয়; এখানে শুধু সারণি সম্পূর্ণ করতে রাখা হলো। একটি নতুন প্রশ্ন এলে প্রথমে জিজ্ঞেস করুন: বস্তুগুলো আলাদা কি না, দল বা বাক্সের নাম আছে কি না, আর দলের ভেতরে ক্রম (গোল টেবিল) গোনে কি না। এই তিন উত্তর প্রায় সবসময় সারণির একটি সারি দেখিয়ে দেয়।

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

অঙ্ক ১: দল আর রাইডার

বাজারঘরের ৬টি আলাদা অর্ডারকে (ক) তিনটি নামহীন অশূন্য ব্যাচে ভাগ করার উপায়, আর (খ) তিনজন নামসহ রাইডারের মধ্যে ভাগের উপায় (প্রত্যেকে অন্তত একটি) কত?

1. (ক) S(6, 3). সারি ৫ থেকে: S(6, 3) = 3 · S(5, 3) + S(5, 2) = 3 · 25 + 15 = 90.
2. (খ) ব্যাচগুলো তিনজনকে 3! উপায়ে: 6 · 90 = 540.
3. যাচাই (inclusion–exclusion, পর্ব ৪৯): 3⁶ − 3 · 2⁶ + 3 · 1⁶ = 729 − 192 + 3 = 540. দুই পথ মিলেছে।

অঙ্ক ২: দুটি গোল টেবিল

৬ জন অতিথিকে দুটি একই রকম গোল টেবিলে বসাতে হবে, কোনো টেবিল খালি নয়; শুধু কে কার ডানে বসলেন তা গুরুত্বপূর্ণ। কয় উপায়ে?

1. এটি c(6, 2). Recurrence: c(6, 2) = 5 · c(5, 2) + c(5, 1) = 5 · 50 + 24 = 274.
2. যাচাই harmonic রূপে: c(6, 2) = 5! · H₅ = 120 · 137/60 = 274.
3. আরেক যাচাই, টেবিলের আকার ধরে: (5, 1)-এ 6 · 4! = 144, (4, 2)-এ C(6, 2) · 3! · 1! = 90, (3, 3)-এ C(6, 3) · 2! · 2!/2 = 40; মোট 274. (3, 3)-এ 2 দিয়ে ভাগ, কারণ সমান আকারের দুই টেবিল অদলবদলে নতুন ব্যবস্থা হয় না।

অঙ্ক ৩: বড়জোর তিন অংশ

৮ কেজি চাল বড়জোর ৩টি অভিন্ন বস্তায় (পূর্ণসংখ্যা কেজিতে, কোনো বস্তা খালি নয়) কয় রকমে ভরা যায়?

1. এটি ৮-এর বড়জোর ৩ অংশের partition; উপপাদ্য ৬.২ অনুযায়ী = ৮-এর যে partition-এর সব অংশ ≤ 3.
2. অংশ ≤ 3-এর তালিকা: 3+3+2, 3+3+1+1, 3+2+2+1, 3+2+1+1+1, 3+1×5, 2+2+2+2, 2+2+2+1+1, 2+2+1×4, 2+1×6, 1×8: ১০টি।
3. সরাসরি যাচাই: 1 অংশ (8): ১টি; 2 অংশ (7+1, 6+2, 5+3, 4+4): ৪টি; 3 অংশ: ৫টি (6+1+1, 5+2+1, 4+3+1, 4+2+2, 3+3+2). 1 + 4 + 5 = 10.

অঙ্ক ৪: Bell সংখ্যা recurrence-এ

B(0…4) = 1, 1, 2, 5, 15 জানা থাকলে B(5) বের করুন। উত্তর: B(5) = C(4, 0) · 1 + C(4, 1) · 1 + C(4, 2) · 2 + C(4, 3) · 5 + C(4, 4) · 15 = 1 + 4 + 12 + 20 + 15 = 52, আর সারি ৫-এর যোগ 1 + 15 + 25 + 10 + 1-ও 52.

যুক্তির ভুল ধরুন: “S(n, k)-এর recurrence”

একজন লিখলেন: “উপাদান n হয় একা থাকে, তখন S(n − 1, k − 1) উপায়; নয়তো আগের k দলের সঙ্গে যোগ দেয়, তখন S(n − 1, k) উপায়। দলগুলোর নাম নেই, তাই কোন দলে যোগ দিল তা গোনার দরকার নেই। অতএব S(n, k) = S(n − 1, k) + S(n − 1, k − 1).”

ভুল কোথায়: “নাম নেই” মানে partition-গুলোর মধ্যে দলের ক্রম নেই, কিন্তু (n − 1)-এর একটি নির্দিষ্ট partition-এ k-টি দল সদস্য দিয়েই আলাদা চেনা যায়, আর n কোন দলে গেল তার প্রতিটি পছন্দ ভিন্ন partition দেয়। তাই গুণক k লাগবে। ছোট মানে ধরা পড়ে: ভুল সূত্রে S(3, 2) = S(2, 2) + S(2, 1) = 2, অথচ তালিকায় তিনটি ({1}{23}, {2}{13}, {3}{12})। এই ভুল সূত্রটি আসলে Pascal-এর সূত্র, যা C(n, k) দেয়, Stirling সংখ্যা নয়। শিক্ষা: প্রতিটি recurrence-এর ফল n = 3 বা 4-এ পূর্ণ তালিকার সঙ্গে মেলান।

১০ · AI-এর যুগে — বিশেষ সংখ্যার দাবি যাচাই

এই সংখ্যাগুলোর নাম আর প্রতীক বই ভেদে বদলায়, প্রথম কয়েকটি মান অনেক পরিবারে মিলে যায়, আর একটি চিহ্ন বা গুণকের ভুল সহজে চোখ এড়ায়। AI সহকারী এসব হিসাব আত্মবিশ্বাসের সঙ্গে লেখে, কিন্তু কয়েকটি ভুল নিয়মিত দেখা যায়:

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

• n = 3 বা 4-এ সব বিন্যাস হাতে বা Python-এ তালিকা করে উত্তরের সঙ্গে মিলিয়েছি
• recurrence-এর গুণক (k না n − 1) আর শুরুর মান S(0, 0) = 1 ঠিক আছে কি না দেখেছি
• সংখ্যা-পরিবার চেনার সময় অন্তত ছয়টি মান মিলিয়েছি, চারটি নয়
• k! দিয়ে গুণ বা ভাগ শুধু তখনই করা হয়েছে যখন সব দল অশূন্য, তা যাচাই করেছি
• চিহ্নসহ নাকি চিহ্নহীন Stirling সংখ্যা, তা স্পষ্ট কি না দেখেছি
• উদ্ধৃত সাল, নাম আর সূত্র বিশ্বস্ত উৎসে মিলিয়েছি

এই পর্বের প্রতিটি সংখ্যার পেছনে একই কৌশল: একটি বিশেষ উপাদান বা অংশ আলাদা করে ধরা, ক্ষেত্রগুলো ভাগ করা, আর প্রতিটি ক্ষেত্রকে একটি bijection দিয়ে ছোট প্রশ্নে নামানো। AI-এর দেওয়া recurrence পড়ার সময় জিজ্ঞেস করুন, কোন উপাদান আলাদা হলো আর প্রতিটি ক্ষেত্রে ফেরত পথ (inverse) আছে কি না। তারপর দশ লাইনের brute force দিয়ে ছোট n-এ মিলিয়ে নিন।