Definition
Binomial Coefficient
Let be a finite set with , and let . The binomial coefficient , read “ choose ”, is the number of -element subsets of :
It therefore counts combinations without repetition: selections in which order does not matter and no element is selected twice.
For integer outside , the usual convention is .
Why the Factorials Appear
Begin with the factorial , which counts the orderings of all elements. For any fixed selection of elements, permuting the selected elements in ways and the unselected elements in ways does not change the selection. Hence
which gives the factorial formula after division by .
Identities
Boundedness
Definition
Link to originalBoundedness of Binomial Coefficients
For and , the binomial coefficients satisfy
The lower bound is attained at and , while the largest coefficients occur in the middle of the row.
In particular, the two boundary coefficients are
There is exactly one way to choose no elements—the empty set—and exactly one way to choose all elements—the entire set.
Symmetry
Definition
Link to originalSymmetry of Binomial Coefficients
For , the binomial coefficients satisfy the symmetry identity
Thus choosing elements from an -element set gives the same number of choices as choosing the elements to leave out.
Pascal’s Identity
Definition
Link to originalPascal's Identity
For , adjacent binomial coefficients satisfy
Coefficients outside are interpreted as zero. The identity expresses each coefficient as the sum of the two coefficients immediately above it.
Asymptotic Growth
For fixed ,
Across all , the largest coefficient occurs in the middle:
Examples
Choosing two elements
From , the two-element subsets are
Thus