Permutations and Combinations: Binomial Theorem

$(a+b)^2$ এর সূত্র আমরা পিচ্চিকাল থেকেই আউরিয়ে আসছি। এরপর আমরা আবার $(a+b)^3$ এর সূত্রও শিখেছি - তার পর $(a+b)^4$ এর সূত্র আমাদের হয়তো মুখস্ত করা হয় নি। একবারও ভেবে দেখেছ কি, সহজ কোনো উপায় ব্যাবহার করে $(a+b)^n$ এর বিস্তার করা যায় কি না ? আচ্ছা, $(a+b)^4$ , $(a+b)^5$ ইত্যাদি বিস্তার করে দেখা যাক আমরা কিছু পাই কি না।

$$\begin{align} (x+y)^1 &= x+y \\ (x+y)^2 &= x^2 + 2xy + y^2 \\ (x+y)^3 &= x^3 + 3x^2y+3xy^2+y^3 \\ (x+y)^4 &= x^4 + 4x^3y + 6x^2y^2+4xy^3+y^4 \\ &\vdots \\ \end{align}$$

উপরের সহগ গুলোর দিকে একবার তাকাও। কিছু বুঝতে পারছ কি? এখানে যেই প্যাটার্ন বিদ্যমান, সেটা কিন্তু আমাদের চিরপরিচিত একটি প্যাটার্ন। আচ্ছা, তোমার বোঝার সুবিধার জন্য আমি একটা টেবিল তইরি করি।

$$\begin{array}{ |c|c|c|c|c|c|c|} \hline 1 &&&&&& \\ \hline 1 & 1 &&&&&\\ \hline 1 & 2 & 1 &&&&\\ \hline 1 & 3 & 3 & 1 &&&\\ \hline 1 & 4 & 6 & 4 & 1 &&\\ \hline 1 & 5 & 10 & 10 & 5 & 1 &\\ \hline 1 & 6 & 15 & 20 & 15 & 6 & 1 \\ \hline \end{array}$$

এবার বুঝতে পারছ ? না পারলে একটা হিন্ট দেই। তুমি টেবিলটিকে একটি ত্রিভুজ আকারে কল্পনা কর। তোমার মাথা একটু হেলিয়ে দেখার চেষ্টা কর টেবিলটিকে। পরিচিত লাগছে কি ?

$$\newcommand\cn[3]{\llap{#1}#2\rlap{#3}} \begin{array}{c} &&&&&&\cn{}{1}{}\\ &&&&&\cn{}{1}{}&&\cn{}{1}{}\\ &&&&\cn{}{1}{}&&\cn{}{2}{}&&\cn{}{1}{}\\ &&&\cn{}{1}{}&&\cn{}{3}{}&&\cn{}{3}{}&&\cn{}{1}{}\\ &&\cn{}{1}{}&&\cn{}{4}{}&&\cn{}{6}{}&&\cn{}{4}{}&&\cn{}{1}{}\\ &\cn{}{1}{}&&\cn{}{5}{}&&\cn{1}{}{0}&&\cn{1}{}{0}&&\cn{}{5}{}&&\cn{}{1}{}\\ \cn{}{1}{}&&\cn{}{6}{}&&\cn{1}{}{5}&&\cn{2}{}{0}&&\cn{1}{}{5}&&\cn{}{6}{}&&\cn{}{1}{} \end{array}$$

হ্যাঁ, আমাদের দ্বিপদী বিস্তারের সহগ গুলো আসলে প্যাস্কেলের ত্রিভুজের এন্ট্রিগুলোর মত !! প্যাস্কেলের ত্রিভুজ নিয়ে মনে আছে কি ? ত্রিভুজ টির প্রথম রোয়ে আছে $1$, দ্বিতীয় রোয়ে $1$ , $1$ । এরপর থেকে প্রত্যেকটি রোয়ের প্রথম ও শেষ এন্ট্রি $1$, কিন্তু মাঝখানের এন্ট্রি গুলো হলো এর আগের রোয়ের ঠিক উপরেরে দুটো এন্ট্রির যোগফল।

আমরা $(a+b)^7$ এর টার্মগুলো আগে বের করার চেষ্টা করি। $a$ এর পাওয়ার গুলোকে $1$ করে কমাতে থাকি আর অন্যদিকে $b$ এর পাওয়ার বাড়াতে থাকি। তাহলে আমরা পাই $a^7,a^6b^1, a^5b^2,$ $a^4b^3, a^3b^4, a^2b^5,a^1b^6 ,b^7$। খেয়াল কর যে $a$ এবং $b$ এর ঘাতের যোগফল সবসময় $7$ হয়। যাই হোক, এটা নিয়ে পরে বিস্তারিত আলোচনা করা যাবে, এখন আমরা $a^3b^4$ এর সহগ নির্ধারণের চেষ্টা করি। প্যাস্কেলের ত্রিভুজটি ব্যবহার করে আমরা সহগ গুলো বের করি।

$$\newcommand\cn[3]{\llap{#1}#2\rlap{#3}} \begin{array}{c} &&&&&&\cn{}{1}{}\\ &&&&&\cn{}{1}{}&&\cn{}{1}{}\\ &&&&\cn{}{1}{}&&\cn{}{2}{}&&\cn{}{1}{}\\ &&&\cn{}{1}{}&&\cn{}{3}{}&&\cn{}{3}{}&&\cn{}{1}{}\\ &&\cn{}{1}{}&&\cn{}{4}{}&&\cn{}{6}{}&&\cn{}{4}{}&&\cn{}{1}{}\\ &\cn{}{1}{}&&\cn{}{5}{}&&\cn{1}{}{0}&&\cn{1}{}{0}&&\cn{}{5}{}&&\cn{}{1}{}\\ \cn{}{1}{}&&\cn{}{6}{}&&\cn{1}{}{5}&&\cn{2}{}{0}&&\cn{1}{}{5}&&\cn{}{6}{}&&\cn{}{1}{} \end{array}$$

এর পরের লাইনটি তাহলে হবে $1,7,21,35,35,21,7,1$ । সুতরাং

$(a+b)^7 = a^7+7a^6b^1+21 a^5b^2 + 35a^4b^3+35a^3b^4+21 a^2b^5+7a^1b^6 +b^7$

অর্থাৎ $a^3b^4$ এর সহগ $35$।

আমরা উপরের বিস্তারটি থেকে পাই যে $a^4b^3$ এর সহগও $35$ হবে। এর বিশেষ কোনো কারণ আছে কি? তুমি পুরো ত্রিভুজটির দিকেই তাকিয়ে দেখ - প্রত্যেকটি লাইন মাঝ বরাবর সিমেট্রিক । তাই $a^ib^{n-i}$ এবং $a^{n-i}b^i$ এর সহগ সমান।

আমরা যদি প্যাস্কেলের ত্রিভুজ তৈরি করে সহগ নির্ধারণের কাজটি করতে চাই, তাহলে খুব বেশি দূরের কাজ করতে পারব না। তাছাড়া আমরা চেয়েছিলাম সহগ গুলোর একটি বীজগাণিতিক রূপ বের করতে, যেটা আমরা এখনও পাই নি। সুতরাং সেটার চেষ্টাই করে যাই।

প্রথমে আমরা একটা নতুন নোটেশনের পরিচয় দেই। $(a+b)^n$ এ $a^{n-i}b^{i}$ এর সহগকে আমরা সুবিধার জন্য $C(n,i)$ বা $\dbinom{n}{i}$ হিসেবে লিখব। আমরা একটু নিচেই দেখতে পাব যে এই নোটেশনটি স্ট্যান্ডার্ড।

$$(a+b)^n = \dbinom{n}{0}a^nb^0 + \dbinom{n}{1}a^{n-1}b^1+\cdots +\dbinom{n}{n}a^0b^n$$

উপরের আলোচনা থেকে আমরা এটা প্রমাণ না করতে পারলেও অনুমান করতে পারি। $\dbinom{n}{i}=\dbinom{n}{n-i}$ কেননা $a^ib^{n-i}$ ও $a^{n-i}b^i$ এর সহগ একই।

প্যাস্কেলের ত্রিভুজে ফিরে যাই আবার আমরা। এখানে যেকোনো এন্ট্রি উপরের দুটো এন্ট্রির যোগফলের সমান। তুমি একটু খেয়াল করলেই দেখতে পাবে যে $\dbinom{n+1}{k+1}$ এর উপরের দুট এন্ট্রি হল $\dbinom{n}{k}$ ও $\dbinom{n}{k+1}$ । তাই $$\dbinom{n}{k}+\dbinom{n}{k+1}=\dbinom{n+1}{k+1}$$

এবার $n$-ফ্যাক্টরিয়ালের ($n!$) সংজ্ঞাটা দেওয়া যাক।

$$n! = 1\cdot 2 \cdot 3 \cdots (n-1)\cdot n$$

তাহলে $\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}$

আমরা এটার প্রমাণ দেওয়ার চেষ্টা করব।

প্রমাণটি করা হবে গাণিতিক আরোহ (ম্যাথমেটিকাল ইনডাকশন) পদ্ধতির দ্বারা। প্রথমে খেয়াল কর যে $(a+b)^0 =1,(a+b)^1=\dbinom{1}{0}a+\dbinom{1}{1}b$ এর জন্য উপরের মানটি আসলেই ঠিক আছে।

এবার ধরে নাও যে $n$ এর জন্য $\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}$। আমরা প্রমাণ করব যে $n+1$ এর জন্যও তা সত্য।

খেয়াল কর যে $(a+b)^{n+1} = (a+b)^n\cdot (a+b)$। আমরা এখান থেকে $\dbinom{n+1}{k}$ এর মান বের করার চেষ্টা করব। $\dbinom{n+1}{k}$ আসলে কী? সংজ্ঞা অনুযায়ী $a^kb^{n+1-k}$ এর সহগ। $(a+b)^n*(a+b)$ এ $a^kb^{n+1-k}$ এর সহগের মান কত? চিন্তা করে দেখ, $a^kb^{n+1-k}$ পাওয়ার জন্য তোমার $(a+b)^n$ এর থেকে $a^kb^{n-k}$ এবং $(a+b)$ এর থেকে $b$ গুণ করা লাগবে। একই ভাবে $a^{k-1}b^{n+1-k}$ ও $a$ এর গুণফলেও $a^kb^{n+1-k}$ পাওয়া সম্ভব। এই দুটি ছাড়া আর কেন সম্ভব না তা বুঝতে পারছ কি? ভেবে দেখ, $(a+b)$ থেকে কিন্তু একঘাতি মান ছাড়া আর কিছু পাওয়া সম্ভব না।

তো আমরা বলতে পারি যে $a^kb^{n+1-k}$ এর সহগ হল $a^kb^{n-k}$ ও $a^{k-1}b^{n+1-k}$ এর সহগের যোগফল। অর্থাৎ $$\dbinom{n}{k-1}+\dbinom{n}{k}=\dbinom{n+1}{k}$$ যেটা আমরা আগেই দেখে এসেছি কিন্তু প্রমাণ দেই নি।

শুরুতেই আমরা ধরে এসেছি যে $\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}$ এবং $\dbinom{n}{k-1} = \dfrac{n!}{(k-1)!(n-k+1)!}$। উপরে সেটি বসালে কি $\dfrac{(n+1)!}{k!(n+1-k)!}$ আসে কি না তা নিজেই যাচাই করে দেখ।