Binomial coefficient

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly denoted by \(\binom{n}{k}\) or \(C(n,k)\), and read "n choose k", each binomial coefficient counts the number of ways to choose \(k\) elements from a set of \(n\) distinct elements, also called combinations. The study of binomial coefficients is a central topic in combinatorics, number theory, and algebra.

Definition and notation

For nonnegative integers \(n\) and \(k\) with \(0 \le k \le n\), the binomial coefficient \(\binom{n}{k}\) is defined by the expression
\[
\binom{n}{k} = \frac{n!}{k!\,(n-k)!},
\]
where \(n!\) denotes the factorial of \(n\). By convention, \(0! = 1\), so \(\binom{n}{0} = \binom{n}{n} = 1\). The notation \(\binom{n}{k}\) was introduced by Andreas von Ettingshausen in 1826, though the modern usage was popularized by Carl Friedrich Gauss. Alternative notations include \(C(n,k)\), \(C_k^n\), and \({}_nC_k\).

Basic properties

Symmetry

A fundamental symmetry holds:
\[
\binom{n}{k} = \binom{n}{n-k}.
\]
This reflects the fact that choosing \(k\) elements is equivalent to leaving out \(n-k\) elements.

Recurrence relation

The binomial coefficients satisfy Pascal's identity:
\[
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, \qquad 1 \le k \le n-1.
\]
This recurrence provides the basis for constructing Pascal's triangle, where each entry is the sum of the two above it.

Binomial theorem

The binomial theorem states that for any real or complex numbers \(x\) and \(y\),
\[
(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k.
\]
This is the origin of the name "binomial coefficient".

Combinatorial interpretation

The coefficient \(\binom{n}{k}\) equals the number of \(k\)-element subsets (or \(k\)-combinations) of an \(n\)-element set. For example, \(\binom{5}{2}=10\) because there are 10 ways to choose 2 objects from 5. This interpretation is often used in probability and statistics, particularly in the binomial distribution.

Multiplicative formula and factorial formula

The factorial formula given above is computationally inefficient for large \(n\) due to large numbers. A multiplicative form is often more practical:
\[
\binom{n}{k} = \frac{n (n-1) \cdots (n-k+1)}{k (k-1) \cdots 1} = \prod_{i=1}^k \frac{n+1-i}{i}.
\]
This expresses the binomial coefficient as a product of \(k\) fractions.

Generalizations

Negative integer n

The binomial coefficient can be extended to negative integer \(n\) using the definition
\[
\binom{-n}{k} = (-1)^k \binom{n+k-1}{k},
\]
which appears in the expansion of \((1-x)^{-n}\) and in the study of multiset combinations (stars and bars).

Real or complex parameters

For an arbitrary complex number \(\alpha\) and nonnegative integer \(k\), the generalized binomial coefficient is defined by
\[
\binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}.
\]
This leads to the binomial series
\[
(1+z)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k} z^k,
\]
which converges for \(|z|<1\) when \(\alpha\) is not a nonnegative integer.

Computing binomial coefficients

Pascal's triangle

Pascal's triangle arranges \(\binom{n}{k}\) for \(n=0,1,2,\ldots\) in a triangular array. The first few rows are:
\[
\begin{array}{c}
1 \\
1 \quad 1 \\
1 \quad 2 \quad 1 \\
1 \quad 3 \quad 3 \quad 1 \\
1 \quad 4 \quad 6 \quad 4 \quad 1
\end{array}
\]
Each entry is the sum of the two above, making it easy to compute small coefficients manually.

Efficient computation

For large \(n\) and \(k\), direct multiplication using the multiplicative formula with integer arithmetic is efficient, provided the intermediate results do not overflow. When \(k\) is close to \(n/2\), symmetry can be used to reduce the number of multiplications. In programming, iterative multiplication with division at each step minimizes intermediate growth. For moderate values, precomputed factorials and modular inverses are used in modular arithmetic.

Applications

Binomial coefficients appear in numerous areas of mathematics and science:

• In combinatorics, they count combinations, permutations with repetition, and lattice paths.
• In probability, the binomial distribution \(P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}\) models the number of successes in independent trials.
• In number theory, they satisfy congruences such as Lucas's theorem and Kummer's theorem, and are related to prime factorization.
• In algebra, they arise in expansions of powers, sums of powers, and polynomial identities.
• In calculus, they appear in Taylor series expansions for rational functions.

History

The concept of binomial coefficients dates back to ancient India, where it was described by Pingala (c. 300–200 BCE) in relation to poetic meter. Later, the Persian mathematician Al-Karaji (c. 1000 CE) gave a systematic exposition, and Pascal's triangle was known to Chinese mathematicians (Yang Hui, 13th century) and European mathematicians before Pascal. The explicit formula using factorials was published by Isaac Newton in the 17th century, and the modern notation \(\binom{n}{k}\) was introduced in the 19th century. Today, binomial coefficients remain a fundamental tool across mathematics.