Factorial formula for binomial coefficients
The binomial coefficient is a ratio of factorials: for .
Proposition 3.12
Counting proof
Given a set of size , there are ways to pick elements, in order, one by one. But each subset of size is picked in ways by this method. Hence the number of subsets of size in is
Growth for large n
The formula tells us, for example, that
so grows like and grows like for large .
Related
Stated in
- Proposition 3.12§3.3.1 Binomial Coefficients