পুনরাবৃত্তিসহ বাছাই — stars and bars আর multinomial

১ · একই জিনিস বারবার — পুনরাবৃত্তিসহ বাছাই কেন আলাদা

কাল্পনিক অনলাইন দোকান বাজারঘর চার ফ্লেভারের চা বিক্রি করে: আদা, এলাচ, লেবু আর মসলা। একজন ক্রেতা একটি “পছন্দের ঝুড়ি”-তে ৬টি প্যাকেট নেবেন, যেকোনো ফ্লেভার যতবার খুশি। ঝুড়িতে প্যাকেটগুলোর কোনো ক্রম নেই: “২টি আদা, ৩টি লেবু, ১টি মসলা” একটিই ঝুড়ি, কোন প্যাকেট আগে তোলা হয়েছিল তাতে কিছু আসে যায় না। প্রশ্ন: মোট কতগুলো আলাদা ঝুড়ি সম্ভব?

প্রথম চেষ্টায় অনেকে লেখেন 4⁶ = 4096, কারণ প্রতিটি প্যাকেটের ৪টি পছন্দ। কিন্তু এটি গোনে প্যাকেট তোলার ক্রম: “আদা, তারপর লেবু” আর “লেবু, তারপর আদা” আলাদা হিসেবে আসে। তখন মনে হয় ক্রম বাদ দিতে 6! দিয়ে ভাগ করলেই হয়: 4096/720 ≈ 5.69, যা পূর্ণসংখ্যাই নয়! ভুলটি কোথায়, তা §৮-এ বিস্তারিত দেখবেন; আপাতত মনে রাখুন, এখানে একটি নতুন গণনার প্রশ্ন দাঁড়িয়েছে, আর তার জন্য নতুন কৌশল লাগবে।

গণনার চারটি মূল মডেল

n ধরনের (বা n-টি আলাদা) জিনিস থেকে r-টি বাছার প্রশ্নে দুটি হ্যাঁ-না প্রশ্ন আছে: ক্রম গুরুত্বপূর্ণ কি না, আর একই জিনিস একাধিকবার নেওয়া যায় কি না। চার সম্ভাবনার তিনটি আপনি আগেই দেখেছেন; চতুর্থটি এই পর্বের বিষয়।

প্রথম সারি পর্ব ৩১ “গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ”-এর গুণের নিয়ম (আর পর্ব ১৬-এ গোনা n^rটি ফাংশন), দ্বিতীয় আর তৃতীয় সারি পর্ব ৩৩ “Permutation আর combination”-এর বিষয়। শেষ সারিতে ছোট উদাহরণেই দেখা যায়, উত্তর 6 = C(4, 2), আর 3²/2! = 4.5 নয়। কারণ ক্রমসহ তালিকায় AB আর BA দুবার আসে, কিন্তু AA আসে মাত্র একবার; প্রতিটি ক্রমহীন বাছাই একই সংখ্যকবার গোনা হয়নি, তাই একটি সংখ্যা দিয়ে ভাগ করে ঠিক উত্তর আসে না।

শেষ বাক্যটি নিজেই একটি bijection (পর্ব ১৬): “S থেকে r আকারের multiset” আর “যোগফল r এমন n-টি অঋণাত্মক পূর্ণসংখ্যার তালিকা”, দুটি সেট সমান আকারের। বাজারঘরের ঝুড়িতে তালিকাটি (আদা, এলাচ, লেবু, মসলা) = (2, 0, 3, 1) এর মতো, যোগফল ৬. তাই প্রশ্নটি দাঁড়াল: x₁ + x₂ + x₃ + x₄ = 6-এর অঋণাত্মক পূর্ণসংখ্যা সমাধান কয়টি? এর উত্তর দেয় পরের অংশের একটি সুন্দর ছবি।

২ · Stars and bars — একটি ছবি, একটি bijection, একটি সূত্র

ধরুন তিন ফ্লেভারের (আদা, এলাচ, লেবু) ৫টি প্যাকেটের একটি ঝুড়ি: ২টি আদা, ০টি এলাচ, ৩টি লেবু. প্রতিটি প্যাকেটকে একটি তারা ★ দিয়ে আঁকুন, আর ফ্লেভারগুলোর মাঝে দুটি দেয়াল │ বসান: প্রথম দেয়ালের বাঁয়ে আদা, দুই দেয়ালের মাঝে এলাচ, দ্বিতীয় দেয়ালের ডানে লেবু. ঝুড়িটি হয়ে যায় ★★││★★★, সাত চিহ্নের একটি সারি। উল্টো দিকেও কাজ চলে: ★│★★★│★ সারিটি পড়লে পাই ১টি আদা, ৩টি এলাচ, ১টি লেবু. এই কৌশলের নাম stars and bars.

এখন গোনা সহজ। প্রতিটি সারিতে ঠিক ৭টি ঘর (৫টি তারা আর ২টি দেয়াল), আর সারিটি পুরো ঠিক হয়ে যায় দেয়াল দুটি কোন দুই ঘরে বসল তা দিয়ে। ৭টি ঘর থেকে ২টি বাছার উপায় C(7, 2) = 21 (পর্ব ৩৩-এর সাধারণ binomial coefficient দিয়ে)। তাই তিন ফ্লেভারের ৫ প্যাকেটের ঝুড়ি ২১টি। সাধারণ রূপটি এবার প্রমাণসহ।

প্রমাণ (bijection দিয়ে): ধরুন X = {(x₁, …, x_n) : প্রতিটি xᵢ অঋণাত্মক পূর্ণসংখ্যা, যোগফল r}, আর B = দৈর্ঘ্য n + r − 1-এর এমন সব সারি, যার ঠিক r-টি ঘরে ★ আর n − 1টি ঘরে │.

1. f: X → B সংজ্ঞায়িত করুন: f(x₁, …, x_n) = ★^x₁ │ ★^x₂ │ ⋯ │ ★^xₙ, যেখানে ★^k মানে পরপর k-টি তারা। এতে তারা আছে x₁ + … + x_n = r-টি আর দেয়াল n − 1টি, তাই f(x) ∈ B. — f সুসংজ্ঞায়িত
2. g: B → X সংজ্ঞায়িত করুন: একটি সারির n − 1টি দেয়াল তাকে বাঁ থেকে ডানে n-টি (হয়তো ফাঁকা) খণ্ডে ভাগ করে; i-তম খণ্ডের তারার সংখ্যা yᵢ ধরুন। yᵢ ≥ 0 আর মোট তারা r, তাই g(সারি) = (y₁, …, y_n) ∈ X. — g সুসংজ্ঞায়িত
3. g(f(x)) = x, কারণ f(x)-এর i-তম খণ্ডে ঠিক xᵢ-টি তারা বসানো হয়েছিল। আর f(g(s)) = s, কারণ খণ্ডের তারার সংখ্যা আর দেয়ালের অবস্থান মিলে সারিটি হুবহু ফিরে আসে। — দুই দিকেই inverse
4. যে ফাংশনের দুই দিকের inverse আছে, তা bijection, আর সসীম সেটে bijection মানে |X| = |B|. — পর্ব ১৬
5. B-এর একটি সারি পুরো ঠিক হয় n + r − 1টি ঘরের কোন n − 1টিতে দেয়াল বসল, তা দিয়ে; তাই |B| = C(n + r − 1, n − 1), আর C(m, k) = C(m, m − k) বলে এটি C(n + r − 1, r)-ও। ∎ — combination-এর সংজ্ঞা

খেয়াল করুন, প্রমাণে কোথাও “ভাগ করে ঠিক করা” নেই: আমরা অচেনা একটি সেটকে চেনা একটি সেটের সঙ্গে এক-এক জোড়ায় মিলিয়েছি। এটিই combinatorial proof-এর একটি রূপ, যা পর্ব ৩৭ “গণনার কৌশল — lattice path, bijection আর double counting”-এ আরও ব্যবহার হবে। বাজারঘরের ৪ ফ্লেভার আর ৬ প্যাকেটে n = 4, r = 6, তাই উত্তর C(9, 6) = C(9, 3) = 84, যা 4096-এর তুলনায় অনেক ছোট। নিচের stepper ছোট উদাহরণ x₁ + x₂ + x₃ = 5-এ প্রমাণের প্রতিটি দিক দেখায়।

1x₁ + x₂ + x₃ = 5, xᵢ ≥ 02(2, 0, 3) → ★★││★★★3★│★★★│★ → (1, 3, 1)4৫ তারা + ২ দেয়াল = ৭ ঘর5C(7, 2) = 216x₁ = 0..5: 6+5+4+3+2+1

Bijection-টি এবার Python-এ দেখা যাক। নিচের ব্লক x₁ + x₂ + x₃ = 5-এর সব সমাধান brute force-এ বের করে, প্রতিটিকে সারিতে রূপান্তর করে (তারার বদলে *, দেয়ালের বদলে |), উল্টো ফাংশন দিয়ে ফেরত আনে, আর শেষে দেখে যে দেয়াল বসানোর সব উপায় ঠিক এই সারিগুলোই। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product, combinations
from math import comb

def to_stars(x):                 # (2, 0, 3) -> "**||***"
    return "|".join("*" * xi for xi in x)

def from_stars(s):               # inverse: count the stars between bars
    return tuple(len(part) for part in s.split("|"))

n, r = 3, 5
solutions = [x for x in product(range(r + 1), repeat=n) if sum(x) == r]
strings = [to_stars(x) for x in solutions]
for x, s in list(zip(solutions, strings))[:5]:
    print(x, "->", s)
print("...")
print("solutions:", len(solutions), " distinct strings:", len(set(strings)))
print("inverse gives back every solution:",
      all(from_stars(s) == x for x, s in zip(solutions, strings)))

# other direction: every way to put n-1 bars into n+r-1 places
L = n + r - 1
placements = {"".join("|" if i in bars else "*" for i in range(L))
              for bars in combinations(range(L), n - 1)}
print("bar placements:", len(placements), " C(7, 2) =", comb(L, n - 1))
print("placements == images of solutions:", placements == set(strings))

(0, 0, 5) -> ||*****
(0, 1, 4) -> |*|****
(0, 2, 3) -> |**|***
(0, 3, 2) -> |***|**
(0, 4, 1) -> |****|*
...
solutions: 21  distinct strings: 21
inverse gives back every solution: True
bar placements: 21  C(7, 2) = 21
placements == images of solutions: True

৩ · পূর্ণসংখ্যা সমাধান — নিম্নসীমা আর অসমতা

বাস্তব প্রশ্নে প্রায়ই শর্ত থাকে। বাজারঘর ঈদের আগে ১০টি একই রকম উপহারের প্যাকেট ৪টি জেলার (ঢাকা, চট্টগ্রাম, রাজশাহী, খুলনা) গুদামে পাঠাবে, আর প্রতিটি জেলা অন্তত একটি পাবে। প্যাকেটগুলো একই রকম, তাই কোন প্যাকেট কোথায় গেল তা নয়, শুধু কোন জেলা কয়টি পেল তা গুরুত্বপূর্ণ: x₁ + x₂ + x₃ + x₄ = 10, প্রতিটি xᵢ ≥ 1. কৌশলটি দৈনন্দিন: আগে প্রত্যেক জেলাকে একটি করে প্যাকেট দিয়ে দিন, তারপর বাকিগুলো স্বাধীনভাবে ভাগ করুন।

প্রমাণ:

1. φ(x₁, …, x_n) = (x₁ − a₁, …, x_n − a_n) নিন। xᵢ ≥ aᵢ বলে প্রতিটি yᵢ = xᵢ − aᵢ ≥ 0, আর ∑yᵢ = r − A. — প্রতিস্থাপন
2. উল্টো দিকে ψ(y) = (y₁ + a₁, …, y_n + a_n) যেকোনো অঋণাত্মক সমাধান y-কে মূল সমস্যার একটি সমাধানে নেয়, আর ψ ∘ φ ও φ ∘ ψ দুটিই identity. তাই φ একটি bijection. — পর্ব ১৬
3. উপপাদ্য ২.১ অনুযায়ী y₁ + … + y_n = r − A-এর অঋণাত্মক সমাধান C(r − A + n − 1, n − 1)টি। A > r হলে ডান পাশ ঋণাত্মক, আর অঋণাত্মক সংখ্যার যোগফল ঋণাত্মক হতে পারে না। — উপপাদ্য ২.১
4. সব aᵢ = 1 হলে A = n, আর সংখ্যাটি C(r − n + n − 1, n − 1) = C(r − 1, n − 1). ∎ — বসানো

প্রতিটি xᵢ ≥ 1 এমন সমাধানের জন্য একটি সরাসরি ছবিও আছে: r-টি তারা এক সারিতে রাখুন; তাদের মাঝে r − 1টি ফাঁক। প্রতিটি দেয়াল একটি আলাদা ফাঁকে বসালে কোনো খণ্ড ফাঁকা থাকে না, তাই উত্তর হলো r − 1টি ফাঁক থেকে n − 1টি বাছাই, অর্থাৎ C(r − 1, n − 1). ক্রমসহ এমন যোগফলকে বলে r-এর একটি composition; যেমন 3-এর composition 3, 2 + 1, 1 + 2, 1 + 1 + 1, মোট 4 = 2³⁻¹টি (পর্ব ৩৭-এ এর bijective প্রমাণ আসবে)।

1x₁+x₂+x₃+x₄ = 10, xᵢ ≥ 12আগে প্রত্যেককে 1: বাকি 63yᵢ = xᵢ − 1 ≥ 04y₁+y₂+y₃+y₄ = 65৬ তারা + ৩ দেয়াল = ৯ ঘর6C(9, 3) = 84

একটি কৌতূহল খেয়াল করুন: ৪ ফ্লেভার থেকে ৬ প্যাকেটের ঝুড়িও 84টি। কাকতালীয় নয়! নিম্নসীমা সরানোর পর জেলার প্রশ্নটি হুবহু y₁ + y₂ + y₃ + y₄ = 6, যা ঝুড়ির প্রশ্নের একই সমীকরণ। দুটি আলাদা গল্প একই গাণিতিক বস্তুতে মিলে গেলে গোনার কাজ অর্ধেক হয়ে যায়।

অসমতা: “বড়জোর r”

ধরুন বাজারঘরের একজন রাইডার দিনে তিনটি এলাকায় বড়জোর ৫টি ডেলিভারি দিতে পারেন: x₁ + x₂ + x₃ ≤ 5, xᵢ ≥ 0. প্রতিটি সম্ভাব্য যোগফল 0, 1, …, 5 আলাদা করে গুনে যোগ করা যায়, কিন্তু একটি ছোট কৌশল আরও সুন্দর। একটি নতুন চলক x₄ = 5 − (x₁ + x₂ + x₃) যোগ করুন, যাকে বলে slack variable (“কতটা ক্ষমতা খালি রইল”)। অসমতাটি তখন সমীকরণ x₁ + x₂ + x₃ + x₄ = 5, সব xᵢ ≥ 0, আর এই রূপান্তরও একটি bijection. উত্তর C(5 + 4 − 1, 3) = C(8, 3) = 56. সাধারণভাবে x₁ + … + x_n ≤ r-এর অঋণাত্মক সমাধান C(r + n, n)টি।

এবার সব দাবি brute force-এ মেলানো যাক। নিচের ব্লকের count ফাংশন প্রতিটি চলকের সম্ভাব্য সব মান নিয়ে সব তালিকা পরীক্ষা করে (গুণের নিয়মে কতগুলো, তা শেষ লাইনগুলোয় দেখবেন), আর সূত্রের সঙ্গে তুলনা করে। §৪-এর ঊর্ধ্বসীমার দুটি দাবিও এখানে আগাম পরীক্ষিত।

from itertools import product
from math import comb

def count(n, r, lo=None, hi=None):
    """brute force: tuples (x1..xn) with lo_i <= x_i <= hi_i and sum r"""
    lo = lo or [0] * n
    hi = hi or [r] * n
    ranges = [range(a, b + 1) for a, b in zip(lo, hi)]
    return sum(1 for x in product(*ranges) if sum(x) == r)

print("x1+x2+x3 = 5, all >= 0   :", count(3, 5),
      " formula", comb(5 + 3 - 1, 3 - 1))
print("10 packets, 4 districts>=1:", count(4, 10, lo=[1] * 4),
      " formula", comb(10 - 1, 4 - 1))
print("6 packets, 4 flavours     :", count(4, 6),
      " formula", comb(6 + 4 - 1, 6))
print("x1+x2+x3 <= 5 (slack x4)  :", sum(count(3, r) for r in range(6)),
      " formula", comb(5 + 3, 3))
print("x1+x2+x3 = 7, x1 <= 3     :", count(3, 7, hi=[3, 7, 7]),
      " formula", comb(9, 2) - comb(5, 2))
print("x1+x2+x3 = 10, all <= 4   :", count(3, 10, hi=[4] * 3),
      " formula", comb(12, 2) - 3 * comb(7, 2) + 3 * comb(2, 2))

# where brute force stops: tuples examined vs the answer
for n, r in [(4, 10), (6, 20), (8, 30)]:
    print(f"n={n}, r={r}: brute force checks {(r + 1) ** n:,} tuples,"
          f" answer {comb(n + r - 1, r):,}")

x1+x2+x3 = 5, all >= 0   : 21  formula 21
10 packets, 4 districts>=1: 84  formula 84
6 packets, 4 flavours     : 84  formula 84
x1+x2+x3 <= 5 (slack x4)  : 56  formula 56
x1+x2+x3 = 7, x1 <= 3     : 26  formula 26
x1+x2+x3 = 10, all <= 4   : 6  formula 6
n=4, r=10: brute force checks 14,641 tuples, answer 286
n=6, r=20: brute force checks 85,766,121 tuples, answer 53,130
n=8, r=30: brute force checks 852,891,037,441 tuples, answer 10,295,472

৪ · ঊর্ধ্বসীমা — খারাপগুলো বাদ দেওয়ার হিসাব

নিম্নসীমা সহজে সরে যায়, কিন্তু ঊর্ধ্বসীমা (xᵢ ≤ uᵢ) প্রতিস্থাপনে সরে না। ধরুন গুদামে আদা চা আছে মাত্র ৩ প্যাকেট, আর একজন ক্রেতা তিন ফ্লেভার মিলিয়ে ৭ প্যাকেট নেবেন: x₁ + x₂ + x₃ = 7, 0 ≤ x₁ ≤ 3. কৌশল: পর্ব ৩১-এর complement বা বিয়োগের নিয়ম। আগে শর্ত ছাড়া সব গুনুন, তারপর “খারাপ” সমাধান, অর্থাৎ x₁ ≥ 4, বাদ দিন।

1. শর্ত ছাড়া: C(7 + 2, 2) = C(9, 2) = 36.
2. খারাপ (x₁ ≥ 4): y₁ = x₁ − 4 বসালে y₁ + x₂ + x₃ = 3, তাই C(5, 2) = 10. খারাপ সমাধানের নিম্নসীমা আছে, আর নিম্নসীমা আমরা জানি সরাতে।
3. ভালো = 36 − 10 = 26 (Python-এর পঞ্চম লাইন)।

একাধিক ঊর্ধ্বসীমা থাকলে সাবধান হতে হয়। x₁ + x₂ + x₃ = 10, প্রতিটি xᵢ ≤ 4 প্রশ্নে খারাপ সমাধান মানে কোনো একটি xᵢ ≥ 5. ধরুন Aᵢ = “xᵢ ≥ 5” এমন সমাধানের সেট।

1. শর্ত ছাড়া: C(12, 2) = 66. প্রতিটি |Aᵢ|: xᵢ থেকে 5 সরালে যোগফল 5, তাই C(7, 2) = 21; তিনটি মিলে 63.
2. কিন্তু 66 − 63 = 3 ভুল উত্তর, কারণ যে সমাধানে দুটি চলকই ≥ 5, যেমন (5, 5, 0), তা A₁ আর A₂ দুই সেটেই আছে আর দুবার বাদ পড়েছে। |Aᵢ ∩ Aⱼ|: দুটি থেকে 5 করে সরালে যোগফল 0, তাই C(2, 2) = 1টি; তিনটি জোড়ায় 3, যা ফেরত যোগ করতে হবে।
3. তিনটিই ≥ 5 হলে যোগফল অন্তত 15 > 10, তাই A₁ ∩ A₂ ∩ A₃ ফাঁকা।
4. উত্তর 66 − 63 + 3 − 0 = 6. তালিকা দিয়ে মেলানো যায়: (4, 4, 2) আর (4, 3, 3)-এর প্রতিটির ৩টি করে বিন্যাস, মোট 6 ✓.

এই “যোগ, বিয়োগ, আবার যোগ” হলো inclusion–exclusion-এর নীতি। দুই সেটের রূপ |A ∪ B| = |A| + |B| − |A ∩ B| আপনি পর্ব ১৫-এ দেখেছেন; যেকোনো সংখ্যক সেটের পূর্ণ রূপ আর তার প্রমাণ আসবে পর্ব ৪৯ “Inclusion–exclusion আর derangement”-এ। আপাতত সূত্রের ধাঁচটি মনে রাখুন: x₁ + … + x_n = r, সব xᵢ ≤ u হলে উত্তর ∑_{j ≥ 0} (−1)^j C(n, j) C(r − j(u + 1) + n − 1, n − 1), যেখানে r − j(u + 1) ঋণাত্মক হলে সেই পদ বাদ। যাচাই: ৪ ফ্লেভার থেকে ৬ প্যাকেট, প্রতি ফ্লেভারে বড়জোর ২টি হলে C(9, 3) − 4 · C(6, 3) + 6 · C(3, 3) = 84 − 80 + 6 = 10, আর scratch-এ brute force-ও 10 দিয়েছে।

৫ · Multiset সারিতে সাজানো — একই জিনিসের permutation

এ পর্যন্ত আমরা ক্রমহীন বাছাই গুনেছি। এবার উল্টো প্রশ্ন: জিনিসগুলো ঠিক করা, কিন্তু ক্রম গুরুত্বপূর্ণ, আর কিছু জিনিস হুবহু একই রকম। বাজারঘরের দোকানের একটি তাকে পাশাপাশি ৯টি পণ্য সাজাতে হবে: ২টি একই রকম চায়ের প্যাকেট (T), ৩টি একই রকম সাবান (S), ৪টি একই রকম বিস্কুটের প্যাকেট (B). তাকের চেহারা কতভাবে আলাদা হতে পারে? দুটি চায়ের প্যাকেট অদলবদল করলে তাক দেখতে একই থাকে, তাই 9! = 362880 অনেক বেশি গোনে।

পর্ব ৩৩-এ পুনরাবৃত্ত অক্ষরসহ শব্দ সাজানোর উদাহরণ দেখেছেন। এখানে তার সাধারণ উপপাদ্য আর দুটি প্রমাণ। ধরুন n-টি জিনিস m ধরনের, i-তম ধরনের kᵢ-টি একই রকম, k₁ + … + k_m = n. এমন সংগ্রহের একটি সারিকে বলে multiset-এর permutation.

প্রমাণ ১ (ভাগের নিয়ম):

1. সাময়িকভাবে একই রকম জিনিসগুলোর গায়ে লেবেল লাগান (T₁, T₂, S₁, …), যাতে n-টিই আলাদা হয়। তখন সারি n!টি। — permutation, পর্ব ৩৩
2. লেবেলসহ একটি সারি থেকে লেবেল মুছলে লেবেলহীন একটি সারি পাওয়া যায়। লেবেলহীন একটি নির্দিষ্ট সারি থেকে লেবেলসহ সারি বানাতে i-তম ধরনের kᵢ-টি জায়গায় তার লেবেলগুলো যেকোনো ক্রমে বসানো যায়: kᵢ! উপায়, আর সব ধরন মিলিয়ে গুণের নিয়মে k₁!⋯k_m! উপায়। — গুণের নিয়ম
3. অর্থাৎ “লেবেল মোছা” ফাংশনটি প্রতিটি লেবেলহীন সারির ওপর ঠিক k₁!⋯k_m!টি সারিকে পাঠায়। প্রতিটি ছবির ঠিক একই সংখ্যক পূর্বরূপ আছে বলে ভাগ বৈধ: লেবেলহীন সারি = n!/(k₁!⋯k_m!). ∎ — ভাগের নিয়ম, পর্ব ৩১

প্রমাণ ২ (জায়গা বাছাই): n-টি জায়গার কোন k₁টিতে প্রথম ধরন বসবে, তা C(n, k₁) উপায়ে; বাকি n − k₁টি জায়গা থেকে দ্বিতীয় ধরনের জন্য C(n − k₁, k₂) উপায়ে; এভাবে চলতে থাকে। গুণের নিয়মে মোট C(n, k₁) · C(n − k₁, k₂) ⋯ C(k_m, k_m). প্রতিটি C-কে factorial-এ লিখলে পরপর হর-লব কেটে যায় (telescoping), আর থাকে n!/(k₁!⋯k_m!). ∎

প্রমাণ ১-এর ধাপ ৩ খুব গুরুত্বপূর্ণ, কারণ এখানেই §১-এর 4⁶/6! ভুলের উত্তর লুকিয়ে আছে। ভাগের নিয়ম খাটে কেবল তখন, যখন প্রতিটি “ফলাফল” ঠিক একই সংখ্যকবার গোনা হয়েছে। তাকের প্রশ্নে তা সত্য, কারণ প্রতিটি লেবেলহীন সারির ঠিক 2! · 3! · 4! = 288টি লেবেলসহ রূপ। ঝুড়ির প্রশ্নে তা মিথ্যা: “৬টিই আদা” ঝুড়িটি ক্রমসহ তালিকায় মাত্র একবার আসে, কিন্তু “আদা, এলাচ, লেবু, মসলা, আদা, এলাচ”-এর মতো ঝুড়ি আসে 6!/(2!2!) = 180 বার। নিচের stepper তাকের হিসাব ধাপে ধাপে দেখায়।

1সব আলাদা ধরলে: 9! = 3628802÷ 2! (দুটি চা)3÷ 3! (তিনটি সাবান)4÷ 4! (চারটি বিস্কুট)5C(9,2)·C(7,3)·C(4,4)

একটি বাংলা নামের উদাহরণ: “BAZARGHAR” (বাজারঘর-এর ইংরেজি বানান) শব্দের ৯টি অক্ষরে A আছে ৩টি, R ২টি, আর B, Z, G, H একটি করে। তাই আলাদা বিন্যাস 9!/(3! · 2!) = 30240. যেসব ধরনের kᵢ = 1, তাদের 1! = 1 দিয়ে ভাগে কিছু বদলায় না।

৬ · Multinomial coefficient আর multinomial theorem

উপপাদ্য ৫.১ থেকেই এর তিনটি সমতুল্য অর্থ আসে: (ক) k₁টি প্রথম ধরন, k₂টি দ্বিতীয় ধরন ইত্যাদির সারি; (খ) n-টি আলাদা জিনিসকে লেবেল দেওয়া m-টি দলে ভাগ, যাতে i-তম দলে ঠিক kᵢ-টি থাকে (যেমন ৯ জন রাইডারকে ঢাকা, চট্টগ্রাম, খুলনা দলে 2, 3, 4 জন করে পাঠানো: 1260 উপায়); (গ) অক্ষর বসানো শব্দ। (খ) আর (ক) একই, কারণ রাইডারদের নির্দিষ্ট ক্রমে দাঁড় করালে প্রত্যেকের গায়ে তাঁর দলের নাম একটি “অক্ষর”.

প্রমাণ:

1. (x₁ + … + x_m)ⁿ হলো n-টি একই বন্ধনীর গুণফল। বন্টন নিয়মে (distributive law) পুরো গুণ খুললে প্রতিটি পদ আসে প্রতিটি বন্ধনী থেকে একটি করে চলক বেছে গুণ করে; বাছাইগুলোকে দৈর্ঘ্য n-এর একটি শব্দ হিসেবে লেখা যায়, যার অক্ষর x₁, …, x_m. তাই খোলা রূপে ঠিক mⁿটি পদ। — বন্টন নিয়ম, গুণের নিয়ম
2. একটি শব্দের গুণফল x₁^k₁⋯x_m^kₘ হয় ঠিক তখন, যখন শব্দে x₁ আছে k₁ বার, …, x_m আছে k_m বার, কারণ চলকগুলো বিনিময়যোগ্য। — গুণের বিনিময় ধর্ম
3. এমন শব্দের সংখ্যা উপপাদ্য ৫.১ অনুযায়ী n!/(k₁!⋯k_m!). তাই একই পদগুলো একত্র করলে x₁^k₁⋯x_m^kₘ-এর সহগ C(n; k₁, …, k_m). ∎ — উপপাদ্য ৫.১

এই প্রমাণ থেকে তিনটি বিনামূল্যের ফল আসে। প্রথমত, সব x_i = 1 বসালে ∑ C(n; k₁, …, k_m) = mⁿ: দৈর্ঘ্য n-এর সব শব্দ, অক্ষরের গণনা অনুযায়ী দলে ভাগ করা। দ্বিতীয়ত, আলাদা আলাদা পদ (monomial) কয়টি? প্রতিটি পদ একটি তালিকা (k₁, …, k_m), যোগফল n, তাই stars and bars অনুযায়ী C(n + m − 1, m − 1)টি। এখানে এই পর্বের দুই অংশ একসঙ্গে মিলল। তৃতীয়ত, m = 2 হলে এটিই পর্ব ৩৪ “Binomial coefficient, Pascal-এর ত্রিভুজ আর combinatorial identity”-এর binomial theorem. যেমন (x + y + z)⁶-এ x²y³z-এর সহগ 6!/(2! 3! 1!) = 60, আর মোট পদ C(8, 2) = 28. নিচের ব্লক এসব দাবি সরাসরি গুণ খুলে মেলায়।

from itertools import product, permutations
from collections import Counter
from math import factorial, prod

def multinomial(*ks):            # (k1+...+km)! / (k1! ... km!)
    return factorial(sum(ks)) // prod(factorial(k) for k in ks)

# 1) shelf: 2 tea (T), 3 soap (S), 4 biscuit (B)
shelf = "TTSSSBBBB"
orders = set(permutations(shelf))          # 9! = 362880 orders, many equal
print("distinct shelf orders:", len(orders), " formula:", multinomial(2, 3, 4))

# 2) expand (x+y+z)^4 by brute force: one letter from each bracket
terms = Counter("".join(sorted(w)) for w in product("xyz", repeat=4))
ok = all(c == multinomial(m.count("x"), m.count("y"), m.count("z"))
         for m, c in terms.items())
print("(x+y+z)^4:", len(terms), "monomials, all match multinomial:", ok)
print("coefficient of x^2*y*z:", terms["xxyz"],
      " sum of coefficients:", sum(terms.values()), "= 3^4")

# 3) (x+y+z)^6: coefficient of x^2 y^3 z
c6 = Counter("".join(sorted(w)) for w in product("xyz", repeat=6))
print("x^2*y^3*z in (x+y+z)^6:", c6["xxyyyz"], " formula:", multinomial(2, 3, 1))
print("monomials in (x+y+z)^6:", len(c6), " = C(8, 2)")

distinct shelf orders: 1260  formula: 1260
(x+y+z)^4: 15 monomials, all match multinomial: True
coefficient of x^2*y*z: 12  sum of coefficients: 81 = 3^4
x^2*y^3*z in (x+y+z)^6: 60  formula: 60
monomials in (x+y+z)^6: 28  = C(8, 2)

৭ · বল আর বাক্স — বণ্টনের বারো পথ

এই মডিউলের প্রায় সব গণনাকে একটি ভাষায় লেখা যায়: n-টি বল k-টি বাক্সে রাখার উপায় কয়টি? তিনটি প্রশ্নের উত্তর আগে ঠিক করতে হয়। বলগুলো কি আলাদা (রাইডারের নাম, পার্সেল নম্বর), না একই রকম (উপহারের প্যাকেট, টাকা)? বাক্সগুলো কি আলাদা (জেলা, ফ্লেভার), না একই রকম (নামহীন একই মাপের ব্যাগ, শুধু দলে ভাগ)? আর শর্ত কী: যেকোনোভাবে, প্রতি বাক্সে বড়জোর একটি (injection), নাকি প্রতি বাক্সে অন্তত একটি (surjection)? ২ × ২ × ৩ = ১২টি সম্ভাবনা, যার নাম twelvefold way. আলাদা বল আর আলাদা বাক্সের ক্ষেত্রে বণ্টন আসলে একটি ফাংশন f: বল → বাক্স; বাকি ক্ষেত্রগুলো সেই ফাংশনের কিছু তথ্য “ভুলে যাওয়া”.

গাঢ় করা তিনটি ঘর এই পর্বের। মাঝের ঘরটি C(k, n) কেন? একই রকম বল, প্রতি বাক্সে বড়জোর একটি: বণ্টন ঠিক হয় শুধু কোন n-টি বাক্সে বল পড়ল তা দিয়ে, অর্থাৎ k-টি বাক্স থেকে n-টির একটি সাধারণ বাছাই। প্রথম সারির surjection-এর সংখ্যা inclusion–exclusion দিয়ে বের হয় (পর্ব ৪৯), আর সেখানে আসে S(n, k), যাকে বলে দ্বিতীয় ধরনের Stirling সংখ্যা: n-টি আলাদা জিনিসকে k-টি নামহীন, অশূন্য দলে ভাগ করার উপায়। নিচের দুই সারির জন্য S(n, k) আর পূর্ণসংখ্যার partition, যার কোনো সহজ closed form নেই; এরা পর্ব ৫০ “বিশেষ সংখ্যা — Catalan, Stirling আর partition”-এর বিষয়। এখানে আমরা শুধু ছোট উদাহরণে সব ১২টি ঘর brute force-এ গুনে দেখব।

from itertools import product
from math import comb

n, k = 4, 3                                  # 4 balls, 3 boxes
maps = list(product(range(k), repeat=n))     # ball i goes to box f[i]

def sizes(f):                                # balls in box 0, 1, 2
    return tuple(f.count(b) for b in range(k))

def grouping(f):                             # which balls share a box
    blocks = {frozenset(i for i in range(n) if f[i] == b) for b in range(k)}
    return frozenset(blocks - {frozenset()})

def row(name, objects, size_list):
    total = len(objects)
    at_most_1 = sum(1 for o in objects if max(size_list(o)) <= 1)
    at_least_1 = sum(1 for o in objects if min(size_list(o)) >= 1)
    print(f"{name:<22}{total:>5}{at_most_1:>6}{at_least_1:>6}")

print(f"{'balls / boxes':<22}{'any':>5}{'<=1':>6}{'>=1':>6}")
row("distinct / distinct", maps, sizes)
row("identical / distinct", {sizes(f) for f in maps}, lambda s: s)
row("distinct / identical", {grouping(f) for f in maps},
    lambda g: [len(b) for b in g] + [0] * (k - len(g)))
row("identical / identical", {tuple(sorted(sizes(f))) for f in maps},
    lambda s: s)
print("formulas: k^n =", k ** n, " C(n+k-1, n) =", comb(n + k - 1, n),
      " C(n-1, k-1) =", comb(n - 1, k - 1))

balls / boxes           any   <=1   >=1
distinct / distinct      81     0    36
identical / distinct     15     0     3
distinct / identical     14     0     6
identical / identical     4     0     1
formulas: k^n = 81  C(n+k-1, n) = 15  C(n-1, k-1) = 3

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

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

অঙ্ক ১: একটি ক্রিকেট ইনিংসে ১০টি উইকেট

ধরে নিন উইকেট পড়ার ধরন শুধু পাঁচটি: bowled, caught, lbw, run out, stumped (বাস্তবে আরও বিরল কিছু ধরন আছে, এখানে বাদ)। একটি ইনিংসে ১০টি উইকেট পড়লে “কোন ধরনে কয়টি” এর কয়টি আলাদা সারসংক্ষেপ সম্ভব?

1. কোন উইকেট আগে পড়ল তা সারসংক্ষেপে নেই, আর একই ধরন বারবার আসতে পারে: ৫ ধরন থেকে পুনরাবৃত্তিসহ ১০টির বাছাই।
2. n = 5, r = 10: C(10 + 5 − 1, 10) = C(14, 4) = 14 · 13 · 12 · 11 / 24 = 1001.

অঙ্ক ২: 0 থেকে 9999-এর মধ্যে অঙ্কের যোগফল 10 এমন সংখ্যা কয়টি?

1. প্রতিটি সংখ্যাকে চার অঙ্কে লিখুন (যেমন 0046): d₁ + d₂ + d₃ + d₄ = 10, প্রতিটি 0 ≤ dᵢ ≤ 9. শর্ত ছাড়া C(13, 3) = 286.
2. খারাপ: কোনো dᵢ ≥ 10. তখন বাকি তিনটির যোগফল 0, অর্থাৎ সংখ্যাটি দাঁড়ায় একটি অঙ্কে 10 আর বাকি তিনটিতে 0: প্রতিটি i-এর জন্য ঠিক ১টি, মোট ৪টি। দুটি অঙ্ক একসঙ্গে ≥ 10 অসম্ভব।
3. উত্তর 286 − 4 = 282. (যোগফল 9 হলে কোনো অঙ্ক 9-এর বেশি হতেই পারে না, তাই সরাসরি C(12, 3) = 220.)

অঙ্ক ৩: (a + b + c + d)⁸-এ a²b³c³-এর সহগ, আর মোট পদের সংখ্যা

1. d-এর ঘাত 0, আর 2 + 3 + 3 + 0 = 8 ✓. সহগ 8!/(2! 3! 3! 0!) = 40320/72 = 560.
2. মোট পদ: চারটি অঋণাত্মক ঘাতের যোগফল 8, তাই C(8 + 3, 3) = C(11, 3) = 165.

প্রমাণের ভুল ধরুন: “ক্রম বাদ দিতে r! দিয়ে ভাগ”

একজন লিখলেন: “দাবি: n ধরন থেকে পুনরাবৃত্তিসহ r-টির ক্রমহীন বাছাই n^r/r!টি। প্রমাণ: ক্রমসহ বাছাই গুণের নিয়মে n^rটি। প্রতিটি ক্রমহীন বাছাইয়ের r-টি জিনিস r! ভাবে সাজানো যায়, তাই প্রতিটি ক্রমহীন বাছাই r! বার গোনা হয়েছে। ভাগের নিয়মে উত্তর n^r/r!. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: “r! ভাবে সাজানো যায়” বাক্যটি শুধু তখন সত্য, যখন r-টি জিনিস সব আলাদা। পুনরাবৃত্তি থাকলে একই রকম জিনিস অদলবদল করলে নতুন ক্রম আসে না: {আদা, আদা, লেবু}-এর ক্রম মাত্র 3!/2! = 3টি, 6টি নয়, আর {আদা, আদা, আদা}-এর মাত্র 1টি। ভাগের নিয়মের শর্ত, “প্রতিটি ফলাফল ঠিক একই সংখ্যকবার গোনা”, এখানে ভাঙে। Counterexample: n = 3, r = 2-এ সূত্রটি 9/2 = 4.5 দেয়, যা পূর্ণসংখ্যাই নয়, অথচ আসল উত্তর 6. ঠিক পথ হলো stars and bars-এর bijection, যেখানে কোনো ভাগই লাগে না। এই একই ভুল বাস্তবে ঘটে যখন কেউ “ক্রম বাদ দিতে sort করে unique রাখি, তারপর গুনি” কোডের বদলে মাথায় ভাগ করে নেন।

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

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

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

• বস্তু আলাদা না একই রকম, ক্রম আছে কি না, আর পুনরাবৃত্তি চলে কি না, তিনটিই নিজে ঠিক করেছি
• সূত্রে দেয়াল বা চলকের সংখ্যা (n − 1, r − 1) ছোট উদাহরণ এঁকে মিলিয়েছি
• প্রতিটি নিম্নসীমা আর ঊর্ধ্বসীমা হিসাবে এসেছে; একাধিক ঊর্ধ্বসীমায় জোড়ার পদ ফেরত যোগ হয়েছে
• কোনো ভাগ থাকলে দেখেছি প্রতিটি ফল সমান সংখ্যকবার গোনা হয়েছে
• ছোট সংখ্যায় Python-এ brute force চালিয়ে উত্তর মিলেছে, আর অন্তত একটি এলোমেলো উদাহরণেও
• উদ্ধৃত ইতিহাস, সাল বা বইয়ের নাম বিশ্বস্ত উৎসে মিলিয়েছি

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