Combination
সমাবেশ
`n` টা থেকে `k` টা বাছা যেখানে **ক্রম গুরুত্বপূর্ণ নয়** — `C(n,k) = n!/(k!(n−k)!)`। Permutation-কে `k!` দিয়ে ভাগ করা।
also: binomial coefficient, n choose k
C(n,k) = P(n,k) / k! = n! / (k!(n−k)!)k! দিয়ে ভাগ, কারণ একই k টা জিনিসকে k! ভাবে সাজানো যায় —
কিন্তু combination হিসেবে সেগুলো একই।
হিসাব করার সঠিক উপায় — factorial ব্যবহার করবেন না:
def bad(n, k): return factorial(n)//(factorial(k)*factorial(n-k))C(100,50) ≈ 10²⁹ কিন্তু 100! ≈ 10¹⁵⁸ — মধ্যবর্তী মান
উত্তরের 10¹²⁹ গুণ বড়। C/Java-তে সরাসরি overflow।
def good(n, k):
k = min(k, n - k)
r = 1
for i in range(k): r = r * (n - i) // (i + 1)
return rপ্রতি ধাপে ভাগ — সবসময় নিঃশেষে বিভাজ্য, আর মধ্যবর্তী মান
কখনো উত্তরের চেয়ে বড় হয় না। Python 3.8+ -এ math.comb।
দুইটা দরকারি ধর্ম:
C(n,k) = C(n, n−k) symmetry
C(n,k) = C(n−1,k−1) + C(n−1,k) Pascal's identity
Σ C(n,k) = 2ⁿ সব subsetPascal’s identity-ই DP-র সরলতম উদাহরণ।