কম্বিনেশন ও বাইনোমিয়াল কোয়েফিসিয়েন্ট

Combinations & the binomial coefficient

৮ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

কম্বিনেশন (Combination) মানে অ-ক্রমবিন্যাস নির্বাচন — শুধু কোন বস্তুগুলো বাছাই হলো তা গুরুত্বপূর্ণ, ক্রম নয়।
$n$টি থেকে $r$টি বাছাইয়ের সংখ্যা: $C(n,r) = \dfrac{n!}{r!(n-r)!}$, এবং $C(n,r) = P(n,r)/r!$।
বাইনোমিয়াল থিওরেম: $(x+y)^n = \sum_{k=0}^{n} C(n,k)\, x^{n-k} y^k$ — কম্বিনেশনগুলোই এখানে সহগ (coefficient)।
পাস্কালের আইডেন্টিটি: $C(n,k) = C(n-1,k-1) + C(n-1,k)$ — পাস্কালের ত্রিভুজের প্রতিটি সংখ্যা এভাবেই তৈরি হয়।

এই পাঠে যা শিখবেন

কম্বিনেশনের সংজ্ঞা এবং $C(n,r)$ সূত্র পারমুটেশন থেকে কীভাবে আসে
বাইনোমিয়াল থিওরেম ও তার সাথে পাস্কালের ত্রিভুজের সম্পর্ক
পাস্কালের আইডেন্টিটি এবং $C(n,k)=C(n,n-k)$ প্রতিসাম্যতা
Python-এর math.comb দিয়ে পাস্কালের ত্রিভুজ তৈরি ও যাচাই

১ · কম্বিনেশন — ক্রম গুরুত্বপূর্ণ নয়

গত পাঠে (L13) আমরা দেখেছি পারমুটেশনে ক্রম গুরুত্বপূর্ণ। কিন্তু অনেক বাস্তব সমস্যায় শুধু কোন বস্তুগুলো বাছাই হলো তা গুরুত্বপূর্ণ — কীভাবে সাজানো হলো তা নয়। যেমন ৫ জন থেকে একটি ৩ জনের কমিটি বাছাই করা — এখানে কমিটির সদস্য কে, তা গুরুত্বপূর্ণ, কিন্তু "কে প্রথমে বাছাই হয়েছে" তা অপ্রাসঙ্গিক। এই ধরনের অ-ক্রমবিন্যাস নির্বাচনকে বলা হয় CombinationCombination (কম্বিনেশন)একটি সেট থেকে বস্তুর একটি উপসেট বাছাই — যেখানে শুধু কোন বস্তুগুলো বাছাই হলো তা গুরুত্বপূর্ণ, সাজানোর ক্রম নয়।।

পারমুটেশন থেকে কম্বিনেশন

প্রতিটি $r$-সদস্যের কম্বিনেশনকে $r!$ ভিন্নভাবে সাজানো যায় (পারমুটেশন করা যায়)। তাই পারমুটেশনের সংখ্যা কম্বিনেশনের সংখ্যার চেয়ে ঠিক $r!$ গুণ বেশি:

$$C(n,r) = \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}$$

২ · উদাহরণ — $C(5,2)$

৫ জন বন্ধু থেকে ২ জনকে বেছে একসাথে সিনেমা দেখতে পাঠাতে হবে (কোনো পদ নেই, শুধু কারা যাবে তা গুরুত্বপূর্ণ)। মোট উপায়:

সমাধান

$$C(5,2) = \frac{5!}{2!\,3!} = \frac{120}{2 \times 6} = \frac{120}{12} = 10$$

৩ · বাইনোমিয়াল থিওরেম

কম্বিনেশনের সংখ্যা $C(n,k)$-কে বাইনোমিয়াল কোয়েফিসিয়েন্টBinomial Coefficient$(x+y)^n$-এর বিস্তৃতিতে $x^{n-k}y^k$ পদের সহগ, যা $C(n,k)$-এর সমান — তাই "n choose k" প্রতীকটি $\binom{n}{k}$ দিয়েও লেখা হয়।-ও বলা হয়, কারণ এটি $(x+y)^n$-এর বিস্তৃতিতে সহগ হিসেবে সরাসরি আসে —

বাইনোমিয়াল থিওরেম

$$(x+y)^n = \sum_{k=0}^{n} C(n,k)\, x^{n-k} y^k$$

উদাহরণস্বরূপ $n=3$-এর জন্য বিস্তার করলে:

$$(x+y)^3 = C(3,0)x^3 + C(3,1)x^2y + C(3,2)xy^2 + C(3,3)y^3 = x^3+3x^2y+3xy^2+y^3$$

লক্ষ্য করুন সহগগুলো — $1, 3, 3, 1$ — ঠিক পাস্কালের ত্রিভুজের ৩য় সারির (০-ইনডেক্স করে সারি ৩) সংখ্যাগুলোর সাথে মিলে যায়।

৪ · পাস্কালের ত্রিভুজ ও পাস্কালের আইডেন্টিটি

পাস্কালের ত্রিভুজের প্রতিটি সংখ্যা তার ঠিক উপরের সারির দুই পার্শ্ববর্তী সংখ্যার যোগফল। এই নিয়মকে পাস্কালের আইডেন্টিটিPascal's Identity$C(n,k) = C(n-1,k-1) + C(n-1,k)$ — একটি $r$-সদস্যের উপসেটে একটি নির্দিষ্ট বস্তু (a) থাকবে অথবা (b) থাকবে না — এই দুই পরস্পর-বিচ্ছিন্ন কেসের যোগফলই মোট কম্বিনেশন। বলা হয়। এটি প্রমাণ করা যায় যুক্তির মাধ্যমে: $n$টি বস্তু থেকে $k$টি বাছাইয়ের সময় একটি নির্দিষ্ট বস্তু (ধরা যাক $x$) হয় বাছাই হবে, নয়তো হবে না — এই দুই পরস্পর-বিচ্ছিন্ন কেস যোগ করলেই মোট কম্বিনেশন পাওয়া যায়।

প্রতিসাম্যতা
$C(n,k)=C(n,n-k)$ — $k$টি বাছাই করা মানে $n-k$টি বাদ দেওয়া, দুটোই একই সংখ্যক উপায়ে হয়।

পাস্কালের আইডেন্টিটি
$C(n,k) = C(n-1,k-1) + C(n-1,k)$ — ত্রিভুজের প্রতিটি সংখ্যার ভিত্তি।

Python

import math

print("C(5,2) =", math.comb(5, 2))

print("\nপাস্কালের ত্রিভুজ (সারি ০-৫):")
for n in range(6):
    row = [math.comb(n, k) for k in range(n + 1)]
    print(row)

n = 5
symmetric_ok = all(math.comb(n, k) == math.comb(n, n - k) for k in range(n + 1))
print(f"\nC({n},k) == C({n},{n}-k) সব k-তে সত্য:", symmetric_ok)

পাস্কালের ত্রিভুজের সারি ৩ হবে [1, 3, 3, 1] — ঠিক $(x+y)^3$-এর সহগগুলোর সাথে মিলে যায়, যা উপরের বাইনোমিয়াল থিওরেমের বিস্তারকে নিশ্চিত করে।

মূল কথা · Key takeaway

কম্বিনেশন হলো পারমুটেশনকে $r!$ দিয়ে ভাগ করে ক্রম-নিরপেক্ষ করা — একই ধারণার একটি ভিন্ন কোণ থেকে দেখা। পরের পাঠে (L15) আমরা দেখব কীভাবে এই কাউন্টিং নিয়মগুলো একটি সম্পূর্ণ নতুন ধরনের যুক্তি — পিজনহোল প্রিন্সিপল — প্রমাণ করতে সাহায্য করে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ একটি পিৎজা শপে ১০ ধরনের টপিং আছে। আপনি ঠিক ৩টি টপিং বেছে একটি পিৎজা অর্ডার করতে চান (একই টপিং দুইবার নয়, এবং কোন ক্রমে বলছেন তা অপ্রাসঙ্গিক)। মোট কতভাবে অর্ডার করা যায়?

এটি একটি কম্বিনেশন সমস্যা — শুধু কোন ৩টি টপিং বাছাই হলো তা গুরুত্বপূর্ণ, বলার ক্রম নয়। $C(10,3) = \dfrac{10!}{3!\,7!} = \dfrac{10 \times 9 \times 8}{3 \times 2 \times 1} = \dfrac{720}{6} = 120$টি ভিন্ন পিৎজা সম্ভব।

প্র ০২ $C(n,0)$ এবং $C(n,n)$-এর মান সবসময় কত, এবং কেন তা স্বজ্ঞাগতভাবেও সত্য?

দুটোরই মান $1$। $C(n,0)=1$ কারণ "কিছুই বাছাই না করা"র ঠিক একটিমাত্র উপায় আছে — খালি সেট। $C(n,n)=1$ কারণ "সবগুলো বস্তু বাছাই করা"রও ঠিক একটিমাত্র উপায় — পুরো সেটটিই। সূত্র দিয়েও যাচাই: $C(n,0)=\dfrac{n!}{0!\,n!}=\dfrac{n!}{n!}=1$ এবং $C(n,n)=\dfrac{n!}{n!\,0!}=1$ (যেহেতু $0!=1$)।

প্র ০৩ পাস্কালের আইডেন্টিটি $C(n,k)=C(n-1,k-1)+C(n-1,k)$ কীভাবে যুক্তি দিয়ে (কোনো সূত্র না লিখে) প্রমাণ করা যায়?

ধরুন $n$টি বস্তুর মধ্যে একটি নির্দিষ্ট বস্তু $x$ আছে। $n$টি থেকে $k$টি বাছাইয়ের যেকোনো উপায়ে $x$ হয় থাকবে, নয়তো থাকবে না — এই দুটি পরস্পর-বিচ্ছিন্ন (mutually exclusive) কেস।

কেস ১ — $x$ বাছাইয়ে আছে: বাকি $k-1$টি বাকি $n-1$টি বস্তু থেকে বাছাই করতে হবে — $C(n-1,k-1)$ উপায়। কেস ২ — $x$ বাছাইয়ে নেই: সবগুলো $k$টি বাকি $n-1$টি বস্তু থেকে বাছাই করতে হবে — $C(n-1,k)$ উপায়। যোগের নিয়ম (L12) প্রয়োগ করে দুই কেস যোগ করলেই $C(n,k)=C(n-1,k-1)+C(n-1,k)$ পাওয়া যায়।

অনুশীলন

গণনা করুন: একটি ৬ জনের দল থেকে ৪ জনের একটি সাব-কমিটি (কোনো পদ ছাড়া) কতভাবে বাছাই করা যায়? প্রতিসাম্যতার সূত্র ব্যবহার করে হাতে যাচাই করুন।

$C(6,4) = C(6,2)$ (প্রতিসাম্যতা, কারণ ৪ জন বাছাই করা মানে ২ জন বাদ দেওয়া) $= \dfrac{6 \times 5}{2 \times 1} = 15$টি উপায়।
যাচাই করুন: উপরের কোড সেলে n = 5-এর বদলে n = 7 বসিয়ে পাস্কালের ত্রিভুজের সারি ৭ প্রিন্ট করুন, তারপর হাতে-হিসাব করা $(x+y)^7$-এর সহগের সাথে মিলিয়ে দেখুন।

সারি ৭ হওয়া উচিত [1, 7, 21, 35, 35, 21, 7, 1] — লক্ষ্য করুন এটিও প্রতিসম (সামনে থেকে পড়া আর পেছন থেকে পড়া একই), যা $C(n,k)=C(n,n-k)$ নিয়মেরই প্রতিফলন।