সমাধান — Chapter 0.2: Combinatorics & Counting¶
অধ্যায়
part-0-foundations/00-02-combinatorics-counting.md-এর §৭ অনুশীলনীর পূর্ণ সমাধান।
৭.১ Conceptual¶
Q1 (★) — পূর্ণ খাবার বাছাই¶
তিনটি ধাপ — স্যুপ এবং মূল পদ এবং মিষ্টি — পরপর, এবং প্রতিটি ধাপের option আগের পছন্দের ওপর নির্ভর করে না। তাই multiplication principle:
মোট ৭২ রকম খাবার সম্ভব। যোগ নয় গুণ — কারণ আমরা একটা পদ "অথবা" আরেকটা বাছছি না, বরং প্রতিটি শ্রেণি থেকে একটা করে নিয়ে একসাথে একটা পূর্ণ খাবার গড়ছি।
Q2 (★) — Permutation না Combination¶
(ক) সভাপতি ও সম্পাদক বাছা — permutation। "X সভাপতি, Y সম্পাদক" আর "Y সভাপতি, X সম্পাদক" — দুটো ভিন্ন ফলাফল; অর্থাৎ ক্রম গুরুত্বপূর্ণ (দুটো পদ আলাদা ভূমিকা)। সংখ্যা \(P(30,2)=30\times29=870\)।
(খ) \(5\) জনের picnic দল — combination। দলে কে আগে কে পরে বাছা হলো তার কোনো মানে নেই; "{A,B,C,D,E}" দলটা একই দল যেভাবেই লিখি। ক্রম গোনা হয় না। সংখ্যা \(\binom{30}{5}=142506\)।
মূল পার্থক্য: ফলাফলের পরিচয়ে ক্রম ঢুকলে permutation, না ঢুকলে combination।
Q3 (★★) — কেন \(\binom{n}{0}=1\) ও \(0!=1\)¶
\(\binom{n}{0}=1\): \(n\)টি জিনিস থেকে \(0\)টি বাছার অর্থ "কিছুই না বাছা"। সেটা করার উপায় ঠিক একটাই — খালি দল (\(\varnothing\), empty set)। তাই \(\binom{n}{0}=1\)। একইভাবে \(\binom{n}{n}=1\): সব \(n\)টি একসাথে নেওয়ার উপায়ও একটাই।
\(0!=1\) কনভেনশনের সঙ্গতি: সূত্র \(\binom{n}{k}=\frac{n!}{k!(n-k)!}\) যেন \(k=0\) ও \(k=n\)-এও \(1\) দেয়, তা নিশ্চিত করতে \(0!=1\) লাগে: $$ \binom{n}{0}=\frac{n!}{0!\,n!}=\frac{1}{0!}, \qquad \binom{n}{n}=\frac{n!}{n!\,0!}=\frac{1}{0!}. $$ গণনা-যুক্তি বলে এই দুই মান \(1\); সূত্রও \(1\) দেবে কেবল যদি \(0!=1\)। তাই \(0!=1\) নিছক খেয়ালখুশি নয় — এটি সমস্ত সূত্রকে সুসংগত রাখে (এছাড়া "\(0\)টি জিনিস সাজানোর উপায় = ১টি, অর্থাৎ কিছুই-না-করা" — এই স্বজ্ঞাও একই কথা বলে)।
৭.২ Computational¶
Q4 (★) — মৌলিক গণনা¶
- (ক) \(7! = 7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1 = 5040\)।
- (খ) \(P(6,2) = \dfrac{6!}{4!} = 6\times5 = 30\)।
- (গ) \(\binom{8}{3} = \dfrac{8\cdot7\cdot6}{3\cdot2\cdot1} = \dfrac{336}{6} = 56\)।
- (ঘ) \(\binom{8}{5} = \dfrac{8!}{5!\,3!} = 56\)।
(গ) ও (ঘ) সমান — কারণ \(\binom{8}{5}=\binom{8}{8-5}=\binom{8}{3}\), symmetry (§৪.১)। স্বজ্ঞা: \(8\) থেকে \(5\)টি নেওয়া = \(8\) থেকে \(3\)টি ফেলে দেওয়া — একই সিদ্ধান্ত।
Q5 (★★) — লটারি¶
(ক) \(1\)–\(49\) থেকে \(6\)টি ভিন্ন সংখ্যা, ক্রম গোনা হয় না → combination: $$ \binom{49}{6} = \frac{49!}{6!\,43!} = 13{,}983{,}816 \;\approx\; 1.4\times10^7. $$
(খ) ঠিক একটা জেতা টিকিট, মোট \(\binom{49}{6}\)টি সমসম্ভাব্য টিকিট → classical probability: $$ P(\text{jackpot}) = \frac{1}{13{,}983{,}816} \approx 7.15\times10^{-8} $$ অর্থাৎ প্রায় \(1.4\) কোটিতে \(1\) — প্রায় অসম্ভব।
Q6 (★★) — "BANANA"-র সাজানো¶
অক্ষর-গণনা: B\(\times1\), A\(\times3\), N\(\times2\) (মোট \(6\))। multinomial: $$ \frac{6!}{1!\,3!\,2!} = \frac{720}{1\cdot6\cdot2} = \frac{720}{12} = 60. $$ ৬০ রকম। (\(6!\) হতো সব অক্ষর ভিন্ন হলে; কিন্তু \(3\)টি A নিজেদের মধ্যে বদলালে নতুন শব্দ হয় না → \(3!\) দিয়ে ভাগ, একইভাবে \(2\)টি N → \(2!\)।)
৭.৩ Proof-based¶
Q7 (★★) — প্রমাণ: \(k\binom{n}{k} = n\binom{n-1}{k-1}\)¶
গণনা-যুক্তি (double counting): \(n\) জন থেকে একটা \(k\)-সদস্যের কমিটি বেছে তার ভেতর \(1\) জনকে সভাপতি (chair) করার উপায়-সংখ্যা দুইভাবে গোনো।
বাঁ দিক: আগে \(k\) জনের কমিটি বাছো (\(\binom{n}{k}\) উপায়), তারপর সেই \(k\) জন থেকে সভাপতি বাছো (\(k\) উপায়)। মোট \(k\binom{n}{k}\)।
ডান দিক: আগে \(n\) জন থেকে সভাপতি বাছো (\(n\) উপায়), তারপর বাকি \(n-1\) জন থেকে কমিটির বাকি \(k-1\) জন বাছো (\(\binom{n-1}{k-1}\) উপায়)। মোট \(n\binom{n-1}{k-1}\)।
একই বস্তু (কমিটি-সহ-সভাপতি) দুইভাবে গোনা হয়েছে, তাই দুই সংখ্যা সমান: $$ k\binom{n}{k} = n\binom{n-1}{k-1}. \qquad\blacksquare $$
যাচাই (\(n=5,k=2\)): বাঁ \(=2\cdot10=20\), ডান \(=5\cdot\binom{4}{1}=5\cdot4=20\) ✓ (বীজগণিতেও দেখা যায়: \(k\cdot\frac{n!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}=n\cdot\frac{(n-1)!}{(k-1)!(n-k)!}=n\binom{n-1}{k-1}\)।)
Q8 (★★★) — প্রমাণ: \(\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0\) (যখন \(n\ge1\))¶
binomial theorem \((x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k\)-এ \(x=1,\;y=-1\) বসাই: $$ (1+(-1))^n = \sum_{k=0}^{n}\binom{n}{k}\,1^{\,n-k}\,(-1)^k = \sum_{k=0}^{n}(-1)^k\binom{n}{k}. $$ বাঁ দিক \(=0^n=0\) (যেহেতু \(n\ge1\))। তাই $$ \sum_{k=0}^{n}(-1)^k\binom{n}{k}=0. \qquad\blacksquare $$
গণনা-অর্থ: যোগফলকে দুই ভাগে ভাঙলে — even \(k\)-গুলো ধনাত্মক, odd \(k\)-গুলো ঋণাত্মক — সমীকরণ বলে $$ \sum_{k \text{ even}}\binom{n}{k} = \sum_{k \text{ odd}}\binom{n}{k}. $$ অর্থাৎ \(n\)টি জিনিসের জোড়-আকারের (even-size) subset-সংখ্যা = বিজোড়-আকারের (odd-size) subset-সংখ্যা। যেহেতু মোট subset \(2^n\), প্রতিটি ভাগ \(2^{n-1}\)। যাচাই (\(n=2\)): even-size \(\{\varnothing,\{a,b\}\}=2\), odd-size \(\{\{a\},\{b\}\}=2\) ✓
৭.৪ Coding¶
Q9 (★★) — multinomial¶
from math import factorial
def multinomial(n, ks):
"""n! / (k1! k2! ... kr!) ; ks-এর যোগফল n হতে হবে।"""
assert sum(ks) == n, "ks-এর যোগফল n-এর সমান হতে হবে"
denom = 1
for k in ks:
denom *= factorial(k)
return factorial(n) // denom
# MISSISSIPPI : M=1, I=4, S=4, P=2 (মোট 11)
print(multinomial(11, [1, 4, 4, 2])) # 34650
আউটপুট:
§৩.৩-এর হাতে-গণনার সাথে মিলছে — ৩৪৬৫০।
Q10 (★★★) — Stars and bars যাচাই¶
from itertools import product
from math import comb
# x1 + x2 + x3 = 7, প্রতিটি xi >= 0 পূর্ণসংখ্যা
solutions = [t for t in product(range(8), repeat=3) if sum(t) == 7]
brute = len(solutions)
formula = comb(7 + 3 - 1, 3 - 1) # C(9, 2)
print("brute-force গণনা :", brute) # 36
print("stars-and-bars :", formula) # 36
assert brute == formula
print("✓ দুই পদ্ধতি একমত")
আউটপুট:
product(range(8), repeat=3) সব \((x_1,x_2,x_3)\) (\(0\)–\(7\)) ঘোরায়, যোগফল \(7\) হওয়াগুলো গোনা হয় — মোট \(36\), যা ঠিক \(\binom{9}{2}=\frac{9\cdot8}{2}=36\) (§২.৭)।