Binomial Coefficient

combinatorics

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

Boundedness 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.

Link to original

Symmetry

Definition

Symmetry 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.

Link to original

Pascal’s Identity

Definition

Pascal'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.

Link to original

Asymptotic Growth

For fixed ,

Across all , the largest coefficient occurs in the middle:

Examples

Choosing two elements

From , the two-element subsets are

Thus