Binomial coefficient

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written ${\displaystyle {\tbinom {n}{k}}.}$ It is the coefficient of the x^k term in the polynomial expansion of the binomial power (1 + x)ⁿ; this coefficient can be computed by the multiplicative formula

$${\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\times \cdots \times 1}},}$$

which using factorial notation can be compactly expressed as

$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$$

For example, the fourth power of 1 + x is $${\displaystyle {\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}}$$ and the binomial coefficient ${\displaystyle {\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6}$ is the coefficient of the x² term.

Arranging the numbers ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}}$ in successive rows for n = 0, 1, 2, ... gives a triangular array called Pascal's triangle, satisfying the recurrence relation $${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}.}$$

The binomial coefficients occur in many areas of mathematics, and especially in combinatorics. In combinatorics the symbol ${\displaystyle {\tbinom {n}{k}}}$ is usually read as "n choose k" because there are ${\displaystyle {\tbinom {n}{k}}}$ ways to choose an (unordered) subset of k elements from a fixed set of n elements. For example, there are ${\displaystyle {\tbinom {4}{2}}=6}$ ways to choose 2 elements from {1, 2, 3, 4}, namely {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and {3, 4}.

The binomial coefficients can be extended to accept more general families of inputs. When n is a nonnegative integer and k is an integer such that k < 0 or k > n, it is common to define ${\displaystyle {\tbinom {n}{k}}=0}$. If k is a nonnegative integer and z is any complex number, the first multiplicative formula above can be used to define ${\displaystyle {\tbinom {z}{k}}}$. Many of the properties of binomial coefficients continue to hold in these more general contexts.