0.2 · Combinatorics Counting
১ · ভূমিকা ও insight (অন্তর্দৃষ্টি)¶
ধরো একটা ন্যায্য (fair) মুদ্রা ৩ বার ছুড়লে। প্রশ্ন: ঠিক ২ বার head পড়ার probability (সম্ভাবনা) কত? এই প্রশ্নের উত্তর দিতে গিয়ে তোমাকে আসলে দুটো জিনিস গুনতে হবে — মোট কতগুলো সম্ভাব্য ফলাফল আছে, আর তার মধ্যে কতগুলো আমাদের পছন্দের (favorable)। উত্তরটা হবে এই দুই সংখ্যার ভাগফল। এটাই classical probability (সম্ভাবনার ধ্রুপদী সংজ্ঞা)-র মূল কথা:
লক্ষ করো, এখানে probability-র সব কাজটাই আসলে counting (গণনা)। আর সঠিকভাবে, দ্রুত, ভুল না করে গোনার বিজ্ঞানের নাম combinatorics (গণনাবিদ্যা)। এই অধ্যায়ে আমরা সেই গোনার যন্ত্রপাতিগুলো তৈরি করব।
Statistics-এ এর ভূমিকা কোথায়? তিন জায়গায় সরাসরি:
- Classical probability: যেকোনো "সমসম্ভাব্য (equally likely) outcome" সমস্যা — পাশা, তাস, লটারি, sampling — মানেই গণনা।
- Binomial distribution: পরে Part II-তে আমরা দেখব \(n\) বার চেষ্টায় ঠিক \(k\) বার সফলতার সম্ভাবনা \(\binom{n}{k}p^k(1-p)^{n-k}\)। এই \(\binom{n}{k}\) অংশটাই combinatorics থেকে আসে — এটা ছাড়া binomial distribution লেখাই যায় না।
- Sampling theory: একটা population থেকে \(n\)টি নমুনা (sample) কত ভাবে বাছা যায় — এটা ঠিক combination-এর প্রশ্ন।
Hook — একটা ছোট ধাঁধা। তোমার কাছে \(52\)টা তাস। random-ভাবে \(5\)টা তাস তুললে। সম্ভাব্য কতগুলো ভিন্ন হাত (hand) হতে পারে? উত্তরটা \(2{,}598{,}960\) — প্রায় ছাব্বিশ লাখ! একটা royal flush পাওয়ার সম্ভাবনা তাই \(4/2598960 \approx 0.0000015\)। এই বিশাল সংখ্যাটা আমরা একটাও তাস না সাজিয়ে, শুধু একটা সূত্র দিয়ে বের করব — সেটাই combinatorics-এর শক্তি।
২ · মূল ধারণা ও সংজ্ঞা¶
সব counting-এর ভিত্তি মাত্র দুটো নীতি। প্রথমে সেগুলো, তারপর তার ওপর সব কিছু গড়ে উঠবে।
২.১ Multiplication principle (গুণনের নীতি)¶
যদি একটা কাজ পর পর কয়েকটা ধাপে করা যায়, এবং প্রথম ধাপ \(n_1\) ভাবে, দ্বিতীয় ধাপ \(n_2\) ভাবে, …, \(r\)-তম ধাপ \(n_r\) ভাবে করা যায় (প্রতিটি ধাপের option-সংখ্যা আগের ধাপের পছন্দের ওপর নির্ভর করে না), তবে পুরো কাজটা মোট $$ n_1 \times n_2 \times \cdots \times n_r $$ ভাবে করা যায়।
স্বজ্ঞা (intuition): ৩টা শার্ট ও ২টা প্যান্ট থাকলে পোশাকের সংখ্যা \(3 \times 2 = 6\)। প্রতিটি শার্টের সাথে ২ ভাবে প্যান্ট মেলানো যায়, শার্ট ৩টা — তাই \(3+3=6\), অর্থাৎ \(3 \times 2\)। মূল শব্দ "এবং" (and): এক ধাপ এবং পরের ধাপ → গুণ।
২.২ Addition principle (যোগের নীতি)¶
যদি একটা কাজ পরস্পর-বিচ্ছিন্ন (mutually exclusive — একসাথে দুটো হতে পারে না) কয়েকটা উপায়ের মধ্যে যেকোনো একটিতে করা যায়, এবং উপায়গুলো যথাক্রমে \(n_1, n_2, \dots, n_r\) ভাবে করা যায়, তবে কাজটা মোট $$ n_1 + n_2 + \cdots + n_r $$ ভাবে করা যায়।
স্বজ্ঞা: তাকে \(5\)টা গল্পের বই অথবা \(8\)টা প্রবন্ধের বই আছে; একটা বই বাছার উপায় \(5+8=13\)। মূল শব্দ "অথবা" (or, বিচ্ছিন্ন ক্ষেত্রে): এই ধাপ অথবা ওই ধাপ → যোগ।
💡 মনে রাখার কৌশল: "and" দেখলে গুণ, বিচ্ছিন্ন "or" দেখলে যোগ। প্রায় সব counting সমস্যা এই দুটো নীতির সাজানো প্রয়োগ মাত্র।
২.৩ Factorial (গৌণিক) — \(n!\)¶
\(n\) একটা অঋণাত্মক পূর্ণসংখ্যা (non-negative integer) হলে, factorial হলো \(1\) থেকে \(n\) পর্যন্ত সব পূর্ণসংখ্যার গুণফল: $$ n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1. $$ সংজ্ঞা অনুসারে \(0! = 1\) (এটা একটা সুবিধাজনক কনভেনশন (convention), পরে কেন তা পরিষ্কার হবে)।
উদাহরণ: \(5! = 5\cdot4\cdot3\cdot2\cdot1 = 120\)। factorial খুব দ্রুত বাড়ে: \(10! = 3{,}628{,}800\), \(13! \approx 6.2 \times 10^9\)।
Notation খোলা: \(n!\) পড়ো "n factorial"; এটা \(n\)টি ভিন্ন জিনিসকে একটা সারিতে সাজানোর মোট উপায়ের সংখ্যা। কেন? প্রথম জায়গায় \(n\)টি option, দ্বিতীয় জায়গায় বাকি \(n-1\), … শেষ জায়গায় \(1\) — multiplication principle দিয়ে \(n\times(n-1)\times\cdots\times1 = n!\)।
২.৪ Permutation (বিন্যাস)¶
Permutation মানে ক্রম গুরুত্বপূর্ণ (order matters) এমন বাছাই/সাজানো। দুই ধরন:
(ক) Without repetition (পুনরাবৃত্তি ছাড়া) — \(n\)টি ভিন্ন জিনিস থেকে \(k\)টি বেছে সাজানোর উপায়:
এটাকে \(\,^{n}P_k\) বা \(P^n_k\)ও লেখা হয়। স্বজ্ঞা: প্রথম জায়গায় \(n\) option, পরের জায়গায় \(n-1\), … \(k\)-তম জায়গায় \(n-k+1\) option (multiplication principle)।
(খ) With repetition (পুনরাবৃত্তি সহ) — প্রতি জায়গায় আবার সব \(n\)টি জিনিস ব্যবহার করা গেলে (যেমন digit), \(k\)টি জায়গার জন্য:
উদাহরণ: \(0\)–\(9\) এই \(10\)টি digit থেকে \(4\)-অঙ্কের PIN বানানো (অঙ্ক বারবার আসতে পারে) \(\Rightarrow 10^4 = 10{,}000\)।
২.৫ Combination (সংযোজন) ও binomial coefficient \(\binom{n}{k}\)¶
Combination মানে ক্রম গুরুত্বপূর্ণ নয় (order does not matter) এমন বাছাই — শুধু "কোন কোনগুলো নিলাম" সেটাই গোনা হয়, কোন ক্রমে নিলাম তা নয়।
\(n\)টি ভিন্ন জিনিস থেকে \(k\)টি বাছার উপায়-সংখ্যাকে binomial coefficient বলে এবং \(\binom{n}{k}\) ("n choose k") লেখা হয়: $$ \binom{n}{k} = \frac{n!}{k!\,(n-k)!}, \qquad 0 \le k \le n. $$
কেন এই সূত্র? \(k\)টি জিনিস বেছে সাজানোর উপায় \(P(n,k) = n!/(n-k)!\)। কিন্তু combination-এ ক্রম গোনা হয় না, আর একই \(k\)টি জিনিসকে \(k!\) ভিন্ন ক্রমে সাজানো যায়। তাই permutation-সংখ্যাকে \(k!\) দিয়ে ভাগ করলেই combination পাওয়া যায়:
এই একটাই সম্পর্ক — permutation \(=\) combination \(\times\, k!\) — পুরো combinatorics-এর হৃদয়। "Binomial coefficient" নামটা কেন, তা §৪-এ binomial theorem দেখলে পরিষ্কার হবে।
২.৬ Multinomial coefficient (বহুপদ সহগ) — হালকা পরিচয়¶
ধরো \(n\)টি জিনিসকে \(r\)টি দলে ভাগ করতে হবে, দলগুলোর আকার যথাক্রমে \(k_1, k_2, \dots, k_r\) (\(k_1+\cdots+k_r = n\))। উপায়-সংখ্যা:
এটা \(\binom{n}{k}\)-এর সাধারণীকরণ (\(r=2\) হলে \(\binom{n}{k,\,n-k}=\binom{n}{k}\))। ব্যবহার: একটা শব্দে একই অক্ষর বারবার থাকলে তার ভিন্ন সাজানো গোনা (যেমন MISSISSIPPI — §৩.৩)।
২.৭ Stars and bars (তারা ও দণ্ড) — ঐচ্ছিক ধারণা¶
প্রশ্ন: \(x_1 + x_2 + \cdots + x_r = n\) সমীকরণের কতগুলো অঋণাত্মক পূর্ণসংখ্যা সমাধান আছে? কল্পনা করো \(n\)টি একরকম তারা \(\star\) একটা সারিতে, আর \(r-1\)টি দণ্ড \(\mid\) দিয়ে তাদের \(r\) ভাগে ভাগ করছ। প্রতিটি ভাগের তারা-সংখ্যাই এক একটা \(x_i\)। মোট \(n + (r-1)\)টি প্রতীকের মধ্যে \(r-1\)টি দণ্ডের জায়গা বাছার উপায়:
statistics-এ এটা লাগে যখন "\(n\)টি একরকম নমুনাকে \(r\)টি শ্রেণিতে কত ভাবে ফেলা যায়" — যেমন occupancy / allocation সমস্যায়।
৩ · পূর্ণাঙ্গ উদাহরণ¶
উদাহরণ ৩.১ — Permutation: দৌড়ের পদক¶
\(8\) জন প্রতিযোগী দৌড়াচ্ছে। স্বর্ণ, রৌপ্য, ব্রোঞ্জ — এই \(3\)টি পদক কত ভাবে বিতরণ হতে পারে? এখানে ক্রম গুরুত্বপূর্ণ (কে প্রথম, কে দ্বিতীয় — আলাদা ফলাফল), তাই permutation:
ধাপে ধাপে: স্বর্ণ পেতে পারে \(8\) জনের যেকোনো একজন; স্বর্ণ ঠিক হয়ে গেলে রৌপ্য বাকি \(7\) জনের একজন; তারপর ব্রোঞ্জ বাকি \(6\) জনের একজন। multiplication principle: \(8\times7\times6 = 336\)।
উদাহরণ ৩.২ — Combination: কমিটি বাছাই ও তাসের হাত¶
(ক) \(5\) জন থেকে \(2\) জনের একটা কমিটি কত ভাবে বাছা যায়? কমিটিতে কে আগে কে পরে — তার কোনো মানে নেই, তাই combination:
যাচাই (ছোট বলে হাতে লেখা যায়): \(\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}\) — ঠিক \(10\)টি।
(খ) §১-এর তাসের ধাঁধা: \(52\) থেকে \(5\) তাস, ক্রম গোনা হয় না →
উদাহরণ ৩.৩ — Multinomial: MISSISSIPPI শব্দের সাজানো¶
"MISSISSIPPI" শব্দে \(11\)টি অক্ষর: M\(\times1\), I\(\times4\), S\(\times4\), P\(\times2\)। সব অক্ষর ভিন্ন হলে \(11!\) সাজানো হতো; কিন্তু একই অক্ষর নিজেদের মধ্যে স্থান বদলালে নতুন শব্দ হয় না — তাই প্রতিটি পুনরাবৃত্ত অক্ষরের factorial দিয়ে ভাগ:
উদাহরণ ৩.৪ — Classical probability: ৩ মুদ্রায় ঠিক ২ head¶
§১-এর hook-এর উত্তর। \(3\) বার মুদ্রা ছুড়লে মোট outcome \(2^3 = 8\) (প্রতিবার H/T, multiplication principle)। ঠিক \(2\)টি head পেতে হলে \(3\)টি অবস্থান থেকে \(2\)টি বাছতে হবে head-এর জন্য — combination \(\binom{3}{2} = 3\)। তাই
গণনা করে যাচাই: favorable outcome \(\{HHT, HTH, THH\}\) — ঠিক \(3\)টি, মোট \(8\)টির মধ্যে। এটাই হবে binomial distribution-এর প্রথম ঝলক (§৮ ও Part II)।
৪ · প্রমাণ ও derivation (উৎপাদন)¶
এই Part 0, তাই সব প্রমাণ elementary (প্রাথমিক) — শুধু দুই গণনা-নীতি ও বীজগণিত লাগবে।
৪.১ Symmetry: \(\binom{n}{k} = \binom{n}{n-k}\) ★¶
দাবি: \(n\) থেকে \(k\)টি বাছা আর \(n\) থেকে \(n-k\)টি বাছা — উপায়-সংখ্যা সমান।
বীজগাণিতিক প্রমাণ: সূত্রে বসিয়ে, $$ \binom{n}{n-k} = \frac{n!}{(n-k)!\,\big(n-(n-k)\big)!} = \frac{n!}{(n-k)!\,k!} = \binom{n}{k}. \qquad\blacksquare $$
গণনা-যুক্তি (combinatorial proof) — আরও সুন্দর: \(n\)টি জিনিস থেকে কোন \(k\)টি নেব তা ঠিক করা, আর কোন \(n-k\)টি ফেলে দেব তা ঠিক করা — একই সিদ্ধান্ত! যতগুলো ভাবে নেওয়ার দল বানানো যায়, ঠিক ততগুলো ভাবে ফেলে-দেওয়ার দল বানানো যায়। তাই দুই সংখ্যা সমান। (উদাহরণ: \(\binom{10}{3}=\binom{10}{7}=120\)।)
৪.২ Pascal's rule: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) ★★¶
এই একটা সূত্রই Pascal's triangle-এর গোটা গঠন।
গণনা-যুক্তি (সবচেয়ে স্বচ্ছ): \(n\)টি জিনিসের মধ্যে একটা বিশেষ জিনিসকে আলাদা করো — ধরো "\(\star\)"। \(n\) থেকে \(k\)টি বাছার প্রতিটি দলকে ঠিক দুই শ্রেণিতে ফেলা যায়, এবং কোনো দল দুই শ্রেণিতে একসাথে পড়ে না (mutually exclusive — addition principle খাটে):
- যেসব দলে \(\star\) আছে: তাহলে বাকি \(k-1\)টি জিনিস বাছতে হবে অবশিষ্ট \(n-1\)টি থেকে — উপায় \(\binom{n-1}{k-1}\)।
- যেসব দলে \(\star\) নেই: তাহলে পুরো \(k\)টিই বাছতে হবে অবশিষ্ট \(n-1\)টি থেকে — উপায় \(\binom{n-1}{k}\)।
প্রতিটি দল ঠিক একটি শ্রেণিতে পড়ে, তাই মোট \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)। \(\;\blacksquare\)
যাচাই: \(\binom{5}{2} = \binom{4}{1} + \binom{4}{2} = 4 + 6 = 10\) ✓
৪.৩ Binomial theorem (দ্বিপদী উপপাদ্য) ★★¶
দাবি: যেকোনো অঋণাত্মক পূর্ণসংখ্যা \(n\)-এর জন্য, $$ (x+y)^n = \sum_{k=0}^{n} \binom{n}{k}\, x^{\,n-k}\, y^{\,k}. $$
গণনা-ভিত্তিক প্রমাণ: \((x+y)^n\) মানে \(n\)টি একই উৎপাদক \((x+y)\)-কে গুণ করা: $$ (x+y)^n = \underbrace{(x+y)(x+y)\cdots(x+y)}_{n \text{ টি}}. $$ গুণফল বিস্তার করলে প্রতিটি পদ তৈরি হয় প্রতিটি বন্ধনী থেকে \(x\) অথবা \(y\) — যেকোনো একটা — বেছে নিয়ে। একটা পদ \(x^{\,n-k}y^{\,k}\) হবে ঠিক তখন, যখন \(n\)টি বন্ধনীর মধ্যে \(k\)টি থেকে \(y\) এবং বাকি \(n-k\)টি থেকে \(x\) বাছা হয়। কোন \(k\)টি বন্ধনী থেকে \(y\) নেব — তার উপায় \(\binom{n}{k}\)। তাই \(x^{\,n-k}y^{\,k}\) পদটির coefficient (সহগ) ঠিক \(\binom{n}{k}\)। সব \(k=0,1,\dots,n\) যোগ করলেই theorem (উপপাদ্য)। \(\;\blacksquare\)
এজন্যই \(\binom{n}{k}\)-কে binomial coefficient বলে — এরা \((x+y)^n\) বিস্তারের coefficient। উদাহরণ (\(n=4\)): $$ (x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4, $$ coefficient-গুলো \(1,4,6,4,1\) — ঠিক Pascal-এর \(4\)নং সারি।
৪.৪ Row sum: \(\sum_{k=0}^{n}\binom{n}{k} = 2^n\) ★¶
binomial theorem-এ \(x=y=1\) বসাও: $$ 2^n = (1+1)^n = \sum_{k=0}^{n}\binom{n}{k}\,1^{\,n-k}\,1^{\,k} = \sum_{k=0}^{n}\binom{n}{k}. \qquad\blacksquare $$
অর্থ: \(n\)টি জিনিসের মোট subset-সংখ্যা \(2^n\), আর আকার-\(k\) subset-সংখ্যা \(\binom{n}{k}\); সব আকার যোগ করলে স্বাভাবিকভাবেই \(2^n\) পাওয়া যায়। যাচাই: \(\binom{5}{0}+\cdots+\binom{5}{5} = 1+5+10+10+5+1 = 32 = 2^5\) ✓
৫ · কোড ল্যাব (Python)¶
প্রথমে from-scratch (শুধু Python/NumPy), তারপর library (math, scipy) — দুটোর ফল মিলিয়ে theory যাচাই।
৫.১ From scratch — factorial, permutation, combination¶
import numpy as np
def factorial_scratch(n):
"""n! গুণফল লুপ দিয়ে। 0! = 1 (খালি গুণফল)।"""
result = 1
for i in range(2, n + 1):
result *= i
return result
def nPr_scratch(n, k):
"""P(n, k) = n! / (n-k)! — ক্রম গুরুত্বপূর্ণ।"""
return factorial_scratch(n) // factorial_scratch(n - k)
def nCr_scratch(n, k):
"""C(n, k) — overflow এড়াতে ধাপে ধাপে; symmetry দিয়ে কম গুণ।"""
if k < 0 or k > n:
return 0
k = min(k, n - k) # C(n,k)=C(n,n-k): ছোট k নিলে কম ধাপ
num = 1
for i in range(k):
num = num * (n - i) // (i + 1) # integer division সবসময় exact থাকে
return num
print("factorial_scratch(5) =", factorial_scratch(5)) # 120
print("nPr_scratch(5, 3) =", nPr_scratch(5, 3)) # 60
print("nCr_scratch(52, 5) =", nCr_scratch(52, 5)) # 2598960
print("nCr_scratch(10, 7) =", nCr_scratch(10, 7)) # 120
আউটপুট:
factorial_scratch(5) = 120
nPr_scratch(5, 3) = 60
nCr_scratch(52, 5) = 2598960
nCr_scratch(10, 7) = 120
nCr_scratch-এnum * (n - i) // (i + 1)ক্রমটা ইচ্ছাকৃত: প্রতি ধাপে গুণফল সবসময় পূর্ণসংখ্যা থাকে (পরপর \(i{+}1\)টি সংখ্যার গুণফল সবসময় \((i{+}1)!\) দিয়ে বিভাজ্য), তাই integer division-এ কোনো ভুল হয় না।
৫.২ Library দিয়ে যাচাই — math ও scipy¶
import math
from scipy.special import comb as scomb, perm as sperm
# math module (Python 3.8+): দ্রুত ও exact integer
print("math.factorial(5) =", math.factorial(5)) # 120
print("math.perm(5, 3) =", math.perm(5, 3)) # 60
print("math.comb(52, 5) =", math.comb(52, 5)) # 2598960
# scipy: exact=True দিলে বড় সংখ্যাও নির্ভুল
print("scipy comb(52,5) =", int(scomb(52, 5, exact=True))) # 2598960
print("scipy perm(5,3) =", int(sperm(5, 3, exact=True))) # 60
# from-scratch ও library মিলছে কিনা — assert দিয়ে নিশ্চিত
assert nCr_scratch(52, 5) == math.comb(52, 5)
assert nPr_scratch(5, 3) == math.perm(5, 3)
print("✓ from-scratch ও library একমত")
আউটপুট:
math.factorial(5) = 120
math.perm(5, 3) = 60
math.comb(52, 5) = 2598960
scipy comb(52,5) = 2598960
scipy perm(5,3) = 60
✓ from-scratch ও library একমত
৫.৩ Brute-force গণনা দিয়ে সূত্র যাচাই (itertools)¶
ছোট ক্ষেত্রে সত্যিকারের সব সম্ভাবনা গুনে দেখি সূত্র ঠিক কিনা:
from itertools import permutations, combinations, product
# permutation সূত্র বনাম প্রকৃত গণনা
assert len(list(permutations(range(5), 3))) == math.perm(5, 3) # 60
# combination সূত্র বনাম প্রকৃত গণনা
assert len(list(combinations(range(5), 2))) == math.comb(5, 2) # 10
# classical probability: 3 মুদ্রায় ঠিক 2 head
outcomes = list(product([0, 1], repeat=3)) # 0=T, 1=H ; মোট 2^3=8
favorable = [o for o in outcomes if sum(o) == 2] # ঠিক 2 head
p = len(favorable) / len(outcomes)
print("P(ঠিক 2 head) =", p, " | সূত্র C(3,2)/8 =", math.comb(3, 2) / 8)
আউটপুট:
৫.৪ Pascal's triangle ও row sum¶
def pascal_row(n):
"""n নং সারি Pascal's rule দিয়ে: পরের সহগ = আগেরটা * (n-k+1) / k।"""
row = [1]
for k in range(1, n + 1):
row.append(row[-1] * (n - k + 1) // k)
return row
for n in range(6):
r = pascal_row(n)
print(f"row {n}: {r} (sum = {sum(r)} = 2^{n} = {2**n})")
আউটপুট:
row 0: [1] (sum = 1 = 2^0 = 1)
row 1: [1, 1] (sum = 2 = 2^1 = 2)
row 2: [1, 2, 1] (sum = 4 = 2^2 = 4)
row 3: [1, 3, 3, 1] (sum = 8 = 2^3 = 8)
row 4: [1, 4, 6, 4, 1] (sum = 16 = 2^4 = 16)
row 5: [1, 5, 10, 10, 5, 1] (sum = 32 = 2^5 = 32)
প্রতিটি সারির যোগফল ঠিক \(2^n\) — §৪.৪ প্রমাণ computation দিয়ে যাচাই হলো।
৬ · ভিজ্যুয়ালাইজেশন¶
চিত্র ১ — \(\binom{n}{k}\)-এর symmetry (bar chart)¶
স্থির \(n=10\)-এর জন্য \(\binom{10}{k}\) আঁকলে স্পষ্ট দেখা যায়: মান বাড়ে, মাঝে (\(k=5\)) সর্বোচ্চ হয়, তারপর কমে — এবং \(k=n/2\) অক্ষের সাপেক্ষে পুরোপুরি symmetric (প্রতিসম) (§৪.১)।
import matplotlib
matplotlib.use("Agg")
import numpy as np
import matplotlib.pyplot as plt
from math import comb
n = 10
ks = np.arange(0, n + 1)
vals = np.array([comb(n, k) for k in ks])
fig, ax = plt.subplots(figsize=(8, 4.6))
bars = ax.bar(ks, vals, color="#2c6fbb", edgecolor="black", linewidth=0.7, alpha=0.85)
for k, b in zip(ks, bars):
if k == n // 2:
b.set_color("#e07b39") # মাঝের সর্বোচ্চ bar আলাদা রঙে
ax.axvline(n / 2, color="#c0392b", linestyle="--", linewidth=1.5,
label=f"axis of symmetry k = n/2 = {n/2}")
for k, v in zip(ks, vals):
ax.text(k, v + max(vals) * 0.015, str(v), ha="center", va="bottom", fontsize=8.5)
ax.set_xlabel("k (number chosen)")
ax.set_ylabel(r"$\binom{n}{k}$")
ax.set_title(f"Binomial coefficients C(n, k) for n = {n} (symmetry about k = n/2)")
ax.set_xticks(ks); ax.set_ylim(0, max(vals) * 1.12)
ax.legend(loc="upper right", fontsize=9)
fig.tight_layout()
fig.savefig("../_assets/0-2-binom-bars.png", dpi=150)
চিত্র ২ — Pascal's triangle (heatmap)¶
প্রতিটি ঘর \(\binom{n}{k}\); প্রতিটি ভেতরের সংখ্যা ঠিক তার ওপরের দুই সংখ্যার যোগফল (Pascal's rule, §৪.২)। কিনারা বরাবর সব \(1\) (\(\binom{n}{0}=\binom{n}{n}=1\))। রঙ যত গাঢ় (log scale), মান তত বড় — মাঝখানে কেন্দ্রীভূত।
import matplotlib
matplotlib.use("Agg")
import numpy as np
import matplotlib.pyplot as plt
from math import comb
N = 9
tri = np.full((N, N), np.nan)
for i in range(N):
for j in range(i + 1):
tri[i, j] = comb(i, j)
fig, ax = plt.subplots(figsize=(8, 5.2))
masked = np.ma.masked_invalid(tri)
cmap = plt.cm.YlOrRd.copy(); cmap.set_bad(color="white")
im = ax.imshow(masked, cmap=cmap,
norm=matplotlib.colors.LogNorm(vmin=1, vmax=np.nanmax(tri)))
for i in range(N):
for j in range(i + 1):
ax.text(j, i, str(int(tri[i, j])), ha="center", va="center",
fontsize=9, color="black", fontweight="bold")
ax.set_title("Pascal's Triangle (entry at row n, position k = C(n, k))")
ax.set_xlabel("k"); ax.set_ylabel("n")
ax.set_xticks(range(N)); ax.set_yticks(range(N))
fig.colorbar(im, ax=ax, fraction=0.046, pad=0.04).set_label("value (log scale)")
fig.tight_layout()
fig.savefig("../_assets/0-2-pascal.png", dpi=150)
চিত্র ৩ — Growth: factorial বনাম permutation বনাম combination¶
বাঁ-প্যানেল (log scale): \(n!\) সবচেয়ে দ্রুত বাড়ে, তারপর \(P(n,3)\), সবচেয়ে ধীরে \(\binom{n}{3}\)। ডান-প্যানেল: \(P(n,3)/\binom{n}{3}\) সবসময় ঠিক \(3! = 6\) — §২.৫-এর "permutation \(=\) combination \(\times k!\)" সম্পর্কের ছবি।
import matplotlib
matplotlib.use("Agg")
import numpy as np
import matplotlib.pyplot as plt
from math import comb, factorial
ns = np.arange(0, 11)
fact = np.array([factorial(i) for i in ns], dtype=float)
ns2 = np.arange(3, 14)
perm3 = np.array([factorial(i)//factorial(i-3) for i in ns2], dtype=float)
comb3 = np.array([comb(i, 3) for i in ns2], dtype=float)
fig, axes = plt.subplots(1, 2, figsize=(11, 4.4))
ax = axes[0]
ax.plot(ns, fact, "o-", color="#c0392b", label="n! (factorial)")
ax.plot(ns2, perm3, "s-", color="#2c6fbb", label="P(n, 3) permutations")
ax.plot(ns2, comb3, "^-", color="#3a9d6e", label="C(n, 3) combinations")
ax.set_yscale("log"); ax.set_xlabel("n"); ax.set_ylabel("count (log scale)")
ax.set_title("Growth: factorial vs permutation vs combination"); ax.legend(fontsize=9)
ax = axes[1]
ax.plot(ns2, perm3 / comb3, "d-", color="#7d5ba6")
ax.axhline(factorial(3), color="gray", linestyle="--", label=f"k! = 3! = {factorial(3)}")
ax.set_xlabel("n"); ax.set_ylabel("P(n,3) / C(n,3)")
ax.set_title("Permutations are exactly k! times combinations")
ax.set_ylim(0, 10); ax.legend(fontsize=9)
fig.tight_layout()
fig.savefig("../_assets/0-2-growth.png", dpi=150)
চিত্র ৪ ও ৫ — counting tree ও binomial distribution সংযোগ¶
নিচের counting tree-তে \(\{A,B,C\}\)-এর সব permutation: প্রথম পছন্দ \(3\) ভাবে, দ্বিতীয় \(2\) ভাবে, তৃতীয় \(1\) ভাবে → \(3\times2\times1 = 3! = 6\)টি পাতা (leaf)। এটাই multiplication principle ও factorial-এর চাক্ষুষ রূপ।
পরের চিত্রে Pascal-এর \(10\)নং সারিকে \(2^{10}\) দিয়ে ভাগ করলে যা পাই, সেটাই \(p=0.5\)-এর binomial distribution \(P(X=k)=\binom{10}{k}/2^{10}\) — Part II-এর bridge (সেতু)। সর্বোচ্চ \(k=5\)-এ (\(\approx 0.246\)), আর পুরো bar-এর যোগফল ঠিক \(1\)।
import matplotlib
matplotlib.use("Agg")
import numpy as np
import matplotlib.pyplot as plt
from math import comb
n = 10
ks = np.arange(0, n + 1)
pmf = np.array([comb(n, k) for k in ks], dtype=float) / 2**n # p = 0.5
fig, ax = plt.subplots(figsize=(8, 4.4))
ax.bar(ks, pmf, color="#7d5ba6", edgecolor="black", linewidth=0.7, alpha=0.85)
for k, v in zip(ks, pmf):
ax.text(k, v + 0.003, f"{v:.3f}", ha="center", va="bottom", fontsize=8)
ax.set_xlabel("k (number of successes)"); ax.set_ylabel("P(X = k)")
ax.set_title("Binomial pmf = C(n,k) / 2^n for n=10, p=0.5")
ax.set_xticks(ks); ax.set_ylim(0, max(pmf) * 1.18)
fig.tight_layout()
fig.savefig("../_assets/0-2-binom-dist.png", dpi=150)
print("যোগফল =", pmf.sum()) # 1.0
উপরের counting-tree চিত্রটি একই plotting workflow-এ তৈরি; পূর্ণ tree-আঁকার কোড chapter-এর asset-script-এ আছে এবং একই PNG (
0-2-tree.png) উৎপন্ন করে।
৭ · অনুশীলনী¶
প্রতিটি প্রশ্নে difficulty: ★ সহজ, ★★ মাঝারি, ★★★ কঠিন। পূর্ণ সমাধান আলাদা ফাইলে: _solutions/00-02-combinatorics-counting-solutions.md।
৭.১ Conceptual (ধারণাগত)¶
Q1 (★) এক রেস্তোরাঁয় \(4\) রকম স্যুপ, \(6\) রকম মূল পদ, \(3\) রকম মিষ্টি। প্রতিটি থেকে একটা করে নিয়ে একটা পূর্ণ খাবার (meal) কত ভাবে বাছা যায়? কোন নীতি — যোগ না গুণ — এবং কেন? Hint: তিনটি ধাপ "এবং" দিয়ে যুক্ত।
Q2 (★) নিচের কোনটা permutation, কোনটা combination — ব্যাখ্যা করো: (ক) ক্লাসের \(30\) জন থেকে \(1\) জন সভাপতি, \(1\) জন সম্পাদক বাছা; (খ) \(30\) জন থেকে \(5\) জনের একটা picnic দল বাছা। Hint: ক্রম (order) কি ফলাফল বদলায়?
Q3 (★★) যুক্তি দিয়ে (সূত্রে না বসিয়ে) ব্যাখ্যা করো কেন \(\binom{n}{0} = 1\) এবং কেন \(0! = 1\) কনভেনশনটা \(\binom{n}{0}=\binom{n}{n}=1\)-এর সাথে সঙ্গতিপূর্ণ। Hint: "কিছুই না বাছা"র উপায় কয়টা?
৭.২ Computational (গণনামূলক)¶
Q4 (★) গণনা করো: (ক) \(7!\), (খ) \(P(6,2)\), (গ) \(\binom{8}{3}\), (ঘ) \(\binom{8}{5}\) — এবং (গ),(ঘ) সমান কিনা ব্যাখ্যা করো। Hint: symmetry §৪.১।
Q5 (★★) একটা প্রমাণ লটারিতে \(1\)–\(49\) থেকে \(6\)টি ভিন্ন সংখ্যা বাছা হয় (ক্রম গোনা হয় না)। (ক) মোট কতগুলো টিকিট সম্ভব? (খ) একটা টিকিট কিনে jackpot জেতার probability কত? Hint: \(\binom{49}{6}\); classical probability।
Q6 (★★) "BANANA" শব্দের অক্ষরগুলো কত ভিন্ন ভাবে সাজানো যায়? Hint: multinomial — কোন অক্ষর কতবার আছে গোনো (B,A,N)।
৭.৩ Proof-based (প্রমাণভিত্তিক)¶
Q7 (★★) গণনা-যুক্তি (combinatorial argument) দিয়ে প্রমাণ করো: \(k\binom{n}{k} = n\binom{n-1}{k-1}\). Hint: \(n\) জন থেকে \(k\) জনের একটা কমিটি বেছে তার মধ্যে \(1\) জন সভাপতি বাছা — দুইভাবে গোনো।
Q8 (★★★) binomial theorem ব্যবহার করে প্রমাণ করো: \(\displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0\) (যখন \(n \ge 1\))। এর গণনা-অর্থ কী? Hint: \((x+y)^n\)-এ \(x=1,\,y=-1\) বসাও; even ও odd আকারের subset-সংখ্যা সমান।
৭.৪ Coding (কোডিং)¶
Q9 (★★) এমন একটা ফাংশন multinomial(n, ks) লেখো যা \(\frac{n!}{k_1!\cdots k_r!}\) ফেরত দেয় (ks একটা list, যার যোগফল n)। math.factorial ব্যবহার করো। "MISSISSIPPI"-তে চালিয়ে \(34650\) পাও কিনা দেখো।
Hint: লব \(n!\), হর প্রতিটি \(k_i!\)-এর গুণফল।
Q10 (★★★) itertools দিয়ে brute-force-এ যাচাই করো যে \(x_1+x_2+x_3=7\)-এর অঋণাত্মক পূর্ণসংখ্যা সমাধানের সংখ্যা stars-and-bars সূত্র \(\binom{7+3-1}{3-1}=\binom{9}{2}\)-এর সমান। (সব সমাধান গুনে math.comb(9,2)-এর সাথে মেলাও।)
Hint: product(range(8), repeat=3) থেকে যেগুলোর যোগফল \(7\) সেগুলো গোনো।
৮ · সারসংক্ষেপ ও সংযোগ¶
যা শিখলাম (recap):
| ধারণা | সূত্র | কখন |
|---|---|---|
| Multiplication principle | \(n_1\times n_2\times\cdots\) | ধাপগুলো "and" |
| Addition principle | \(n_1 + n_2 + \cdots\) | বিচ্ছিন্ন "or" |
| Factorial | \(n! = n(n-1)\cdots1,\;\; 0!=1\) | সব সাজানো |
| Permutation (no rep.) | \(P(n,k)=\dfrac{n!}{(n-k)!}\) | ক্রম গোনা, বাছাই |
| Permutation (with rep.) | \(n^k\) | বারবার ব্যবহার |
| Combination | \(\binom{n}{k}=\dfrac{n!}{k!(n-k)!}\) | ক্রম গোনা নয় |
| Multinomial | \(\dfrac{n!}{k_1!\cdots k_r!}\) | দলে ভাগ |
| Stars and bars | \(\binom{n+r-1}{r-1}\) | একরকম জিনিস distribution (বণ্টন) |
মূল সম্পর্কগুলো: permutation \(=\) combination \(\times\, k!\); symmetry \(\binom{n}{k}=\binom{n}{n-k}\); Pascal's rule \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\); binomial theorem \((x+y)^n=\sum_k\binom{n}{k}x^{n-k}y^k\); row sum \(\sum_k\binom{n}{k}=2^n\)।
পূর্ববর্তী সংযোগ (০.১): এখানে \(\binom{n}{k}\) আসলে একটা \(n\)-উপাদানের set-এর আকার-\(k\) subset গোনে; মোট subset \(2^n\) — power set-এর আকার, যা ০.১-এ দেখা। permutation আসলে এক set থেকে আরেক set-এ এক-এক (bijective) function গোনা।
পরবর্তী সংযোগ (০.৩ Calculus I): পরের অধ্যায়ে limit, derivative ও optimization। সেখানে factorial আবার ফিরবে Taylor series-এর হরে (\(\frac{1}{n!}\)), আর binomial coefficient-এর সাধারণীকরণ (generalized binomial) দিয়ে \((1+x)^\alpha\)-এর series লেখা হবে।
Statistics-এ এর গন্তব্য (source pointer): এই অধ্যায় self-contained, কিন্তু সরাসরি Part II — Discrete distributions-কে support করে। সেখানে দেখবে binomial distribution $$ P(X = k) = \binom{n}{k} p^{k} (1-p)^{n-k}, $$ যার \(\binom{n}{k}\) অংশটা ঠিক এখানে শেখা — "\(n\) trial-এর মধ্যে কোন \(k\)টিতে সফলতা" তার গণনা। §৩.৪ ও §৬-এর শেষ চিত্রে (\(p=0.5\)) তার প্রথম রূপ দেখেছ। Classical probability (\(\text{favorable}/\text{total}\))-র এই counting-ভিত্তি Part II-র probability axioms-এর আগে শেষ ধাপ।