Binomial Coefficient
দ্বিপদী সহগ
`C(n,k)` বা `ⁿCₖ` — `(x+y)ⁿ` -এর বিস্তারে `xᵏ` -এর সহগ, আর একই সাথে `n` থেকে `k` বাছার সংখ্যা।
(x+y)ⁿ = Σₖ C(n,k) xᵏ yⁿ⁻ᵏx = y = 1 বসালে Σ C(n,k) = 2ⁿ — সব subset-এর সংখ্যা।
দুইটা সম্পূর্ণ ভিন্ন পথে (বীজগণিত আর গোনা) একই উত্তর।
Pascal’s triangle হলো Pascal’s identity-র দৃশ্যরূপ:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1প্রতিটা সংখ্যা উপরের দুইটার যোগফল — C(n,k) = C(n−1,k−1) + C(n−1,k)।
CS-এ কোথায়:
- Binomial distribution —
nটা স্বাধীন trial-এkটা সফল হওয়ার সম্ভাবনা C(2n,n)= দুইটা thread-এরnoperation-এর interleaving সংখ্যা (n=10→ ১,৮৪,৭৫৬ — এজন্যই race condition ধরা কঠিন)- Catalan সংখ্যা
C(2n,n)/(n+1)— balanced bracket, binary tree, stack permutation-এর সংখ্যা - Load balancing আর hash table বিশ্লেষণে