Binomial coefficient
For , the binomial coefficient counts the subsets of size of an -element set: .
Given , and , we can write for the number of subsets of an -element set that are of size .
is called a binomial coefficient.
Basic values and total count
By definition, , , and for . Grouping subsets by their size counts every subset of an -element set exactly once:
Symmetry
forall and . Specifying which elements to pick is equivalent to specifying which elements to leave out.
Pascal's rule
Moreover,
Committee counting explains the rule. To form a committee from a group of people, either you are in the committee — in which case the remaining members come from the other people — or you are not, in which case all members come from the other . For instance, .
Iterating the rule builds Pascal’s triangle, where each row starts and ends with a , and the remaining entries are the sum of the terms immediately above.
Related
Stated in
- Definition 3.10 (Binomial Coefficient)§3.3.1 Binomial Coefficients