A binomial coefficient counts the k-element combinations that can be selected from n items, written n C k and pronounced “n choose k.” It counts selections rather than arrangements, so order does not matter. section 6.3.2
Useful identities expose both boundary cases and an efficient computation:
- n C k = 0 when k > n, while n C 0 = 1. section 6.3.2
- n C k = n C (n − k), because choosing the selected items corresponds to choosing the unselected items. section 6.3.2
- n C k = (n − 1) C (k − 1) + (n − 1) C k, dividing combinations according to whether they contain the final item. section 6.3.2
- The direct product formula divides by k! to remove the ordering counted while selecting items sequentially. section 6.3.2
Computing and using a coefficient
A C# implementation uses BigInteger, replaces k with n − k when that is smaller, and multiplies and divides incrementally. Thus 20.Choose(10) evaluates the number of ten-element selections from twenty items.
