Knowlpedia

Definition

Binomial coefficient

The number of k-element subsets of an n-element set and its factorial formula.

For integers 0≤k≤n0\le k\le n, the binomial coefficient is

(nk)=n!k!(n−k)!.\binom nk=\frac{n!}{k!(n-k)!}.

It counts the kk-element of an nn-element set. We set (nk)=0\binom nk=0 when k<0k<0 or k>nk>n, and (n0)=(nn)=1\binom n0=\binom nn=1.

Counting argument

There are n(n−1)⋯(n−k+1)n(n-1)\cdots(n-k+1) ordered selections of kk distinct elements. Each subset is represented by exactly k!k! orders, giving the factorial formula. Splitting subsets according to whether they contain one distinguished element gives Pascal's identity

(n+1k)=(nk−1)+(nk).\binom{n+1}{k}=\binom n{k-1}+\binom nk.
A product bound

For 0≤k≤a0\le k\le a and 0≤l≤b0\le l\le b, choosing kk elements from a first block and ll from a second gives only some of the (k+l)(k+l)-element subsets of the union. Consequently

(ak)(bl)≤(a+bk+l).\binom ak\binom bl\le\binom{a+b}{k+l}.

This bound often controls coefficients in repeated product differentiation.

References