কম্বিনেটরিক্স এর হ য ব র ল

1.     nCk = nCn-k

2.    nCk = n-1Ck + n-1Ck-1

nCk এর ভ্যালু বের করা যায় প্যাসকেলের ত্রিভুজ থেকে যা আমরা অনেকেই জানি। প্যাসকেলের ত্রিভুজ দেখতে অনেকটা এরকমঃ 

                                                                1

                                                             1    1

                                                          1    2    1

                                                        1    3    3    1

                                                     1    4    6    4    1

                                               1    5    10    10    5    1

                                            1    6    15    20    15    6    1

এখন প্যাসকেলের ত্রিভুজকে যদি আমরা একটি দ্বিমাত্রিক অ্যারের মধ্যে স্টোর করি তাহলে জিনিসটা কেমন হবে? 

1        0        0        0        0        0        0        0

1        1        0        0        0        0        0        0

1        2        1        0        0        0        0        0

1        3        3        1        0        0        0        0

1        4        6        4        1        0        0        0

1        5        10      10      5        1        0        0

1        6        15      20      15      6        1        0

এই দ্বিমাত্রিক অ্যারের সারি এবং কলামগুলোর ইনডেক্সিং হবে ০ বেজড। যেমনঃ 5C2 = 10 (৫ নাম্বার সারির ২ নাম্বার কলাম এর ভ্যালু ১০) 

3. Row sum of pascal's triangle:

nC0 + nC1 + nC2 + nC3 + --- + nCn = 2^n

অর্থাৎ, প্যাসকেলের ত্রিভুজের ৫ তম সারির সংখ্যাগুলোর যোগফল = ২ ^ ৫।

4. Hockey Stick Identity:

২ নাম্বার কলামের শুরু থেকে ৫ নাম্বার সারি পর্যন্ত সংখ্যাগুলোর যোগফল = ২০ (যা ৩নাম্বার কলাম এর ৬ নাম্বার রো এর ঘরের ভ্যালুর সমান!) 

৩ নাম্বার কলামের শুরু থেকে ৪ নাম্বার সারি পর্যন্ত সংখ্যাগুলোর যোগফল = ৫ (যা ৪নাম্বার কলাম এর ৫ নাম্বার রো এর ঘরের ভ্যালুর সমান!) 

এখন, যোগফল এবং কলামের ভ্যালুগুলো লাল কালার করার পর দেখো তারা সুন্দর একটি হকি স্টিক এর আকার ধারণ করেছে 😉

এখন, Hockey Stick Identity থেকে যা দাঁড়ালো,

kCk + (k+1)Ck + ---- + nCk = (n+1)C(k+1)

5.  0*nC0 + 1*nC1 + 2*nC2 +----+ n*nCn = n * 2^(n-1)

এখানে, 

2*nC2 মানে ২ সাইজের সকল সম্ভাব্য সাবসেটের সাইজের যোগফল। 

3*nC3 মানে ৩ সাইজের সকল সম্ভাব্য সাবসেটের সাইজের যোগফল। 

তার মানে, 0*nC0 + 1*nC1 + 2*nC2 +----+ n*nCn দ্বারা বুঝায় সম্ভাব্য সকল সাইজের সাবসেটের জন্য তাদের সাইজের যোগফল। 

এখন, ৩টি ক্যারেক্টার নিয়ে গঠিত একটি সেট {A , B , C} এর জন্য চিন্তা করি। সাবসেটগুলো কি কি হবে?

{{A} , {B} , {C} , {A,B} , {B,C} , {A,C} , {A,B,C}}

A আছে কয়টি সাবসেটে? ৪ টি

B আছে কয়টি সাবসেটে? ৪ টি

C আছে কয়টি সাবসেটে? ৪ টি

অর্থাৎ, মূল সেটের সাইজ যদি n হয় তবে প্রতিটি ক্যারেক্টার 2 ^ (n-1) সংখ্যক সাবসেটে থাকবে। 

অর্থাৎ, সম্ভাব্য সকল সাবসেটের জন্য তাদের সাইজের যোগফলে প্রতিটি ক্যারেক্টার এর জন্য কন্ট্রিবিউশন হচ্ছে 2^(n-1) ।

n সংখ্যক ক্যারেক্টারের সর্বমোট কন্ট্রিবিউশন = n * 2^(n-1) 

6.    (nC0)^2 + (nC1)^2 +----+ (nCn)^2 = 2nCn

মূলত, 2n টা জিনিস থেকে n টা জিনিস বাছাই করা যায় কত উপায়ে সেটাই দেখানো হয়েছে এই সমীকরণে। 

আমার কাছে থাকা 2n টা জিনিস কে ২ভাগে ২টি বক্সে রাখি। ১ম n সংখ্যক ১ম বক্সে। পরের n সংখ্যক ২য় বক্সে রাখলাম। 

1 , 2 , ... , n    |     n+1 , n+2 , .... , 2n

এখন, ১ম বক্স থেকে ০ টা নিলে ২য় বক্স থেকে n টা জিনিস নিতে হবে। নেয়া যায়ঃ nC0 * nCn উপায়ে

১ম বক্স থেকে ১টা নিলে ২য় বক্স থেকে n-1 টা জিনিস নিতে হবে। নেয়া যায়ঃ nC1 * nCn-1 উপায়ে 

১ম বক্স থেকে ২টা নিলে ২য় বক্স থেকে n-2 টা জিনিস নিতে হবে। নেয়া যায়ঃ nC2 * nCn-2 উপায়ে 

............................................................................................................................................................

১ম বক্স থেকে n টা নিলে ২য় বক্স থেকে 0 টা জিনিস নিতে হবে। নেয়া যায়ঃ nCn * nC0 উপায়ে 

এখন, এই সবগুলো উপায় কে যোগ করলে মোট উপায় পাওয়া যাবে। আবার আমরা জানি,

nCk = nCn-k

তার মানে nC0 = nCn , nC1 = nCn-1 , nC2 = nCn-2

তাহলে এখন আমরা লিখতেই পারি,

2nCn = (nC0)^2 + (nC1)^2 +----+ (nCn)^2

7. nC0 + (n+1)C1 + (n+2)C2 + --- + (n+k)Ck = (n+k+1)Ck

প্যাসকেল এর ত্রিভুজের দেখলে যা অনেকটা এরকম হবেঃ 

তার মানে প্যাসকেলের ত্রিভুজের ১ম কলাম এর যেকোন সারি থেকে কর্ণ বরাবর এলিমেন্টগুলোর যোগফল শেষ এলিমেন্ট এর ঠিক নিচের সারিতে একই কলাম বরাবর থাকে। 

8. Lucas Theorem:

nCr%p = ? where p is a prime number.

লুকাস থিওরি অনুযায়ী nCr%p বের করার পদ্ধতি হলোঃ

প্রথমেই, n এবং r উভয় সংখ্যাকে p-base সংখ্যা তে রূপান্তর করতে হবে। এরপর, p-base সংখ্যাদ্বয়ের প্রতি পজিশনে যে সংখ্যাদ্বয় থাকবে তাদের xCy এর গুণফলই হবে এন্সার যেখানে x হচ্ছে n কে p-base এ রূপান্তর করলে ঐ পজিশনে যে সংখ্যা থাকে এবং y হচ্ছে r কে p-base এ রূপান্তর করলে ঐ পজিশনে যে সংখ্যা থাকে। 

যেমন, 15C5 % 5 = 3003 % 5 = 3

15 কে p=5 base সংখ্যাতে রূপান্তরিত করলে হয় = 3 0

5 কে p=5 base সংখ্যাতে রূপান্তরিত করলে হয়   = 1 0

তাহলে এন্সার = 3C1 * 0C0 = 3 * 1 = 3

বলে রাখা ভালো, এই পদ্ধতিতে হিসেবের সময় xCy = 0 হবে যদি x<y হয়। 

আজ এ পর্যন্তই। Happy Coding 😊