Combination
A combination counts the ways to choose k elements from n without regard to order, C(n,k)=n!/(k!(n-k)!), i.e., the binomial coefficient.
Purpose
To count unordered selections, a foundation of combinatorics and probability.
Mechanism
C(n,k) = n!/(k!(n-k)!) = C(n,n-k). Recurrence: C(n,k)=C(n-1,k-1)+C(n-1,k) (Pascal's triangle). For large numbers use logarithms or the recurrence to avoid overflow. C(n,0)=1, C(n,n)=1.
Use cases
- Probability computation (binomial distribution)
- Combinatorial enumeration
- Binomial expansion coefficients
- Hypergeometric distribution
Examples
- Input
C(5,2)=5!/(2!3!)=10Output10Choosing 2 of 5, unordered
Common errors
- Computing factorials directly overflows
- Use the recurrence or logarithms
Related terms
Permutation
A permutation counts the ordered ways to choose k elements from n, P(n,k)=n!/(n-k)!; the full permutation count is n!. GLOSSARY
Factorial
The factorial n! = n×(n-1)×...×1 is the basis of permutations and combinations; it grows extremely fast, with 20! already exceeding the 64-bit integer range. GLOSSARY