Binomial Coefficient · aiwiki.page

A binomial coefficient, written $\binom{n}{k}$ and read “ $n$ choose $k$ ,” counts the ways to select $k$ distinct objects from $n$ distinct objects without regard to order. Equivalently, it counts the $k$ -element subsets of an $n$ -element set. These numbers connect combinatorics with algebra: they are also the coefficients in the expansion described by the binomial theorem. (discrete.openmathbooks.org)

Definition and counting interpretation

For nonnegative integers $n$ and $k$ , with $0\leq k\leq n$ ,

\binom{n}{k}=\frac{n!}{k!(n-k)!},

where $n!$ denotes the factorial and $0!=1$ . The boundary values are

\binom{n}{0}=\binom{n}{n}=1.

For fixed nonnegative $n$ , the conventional extension is $\binom{n}{k}=0$ when $k<0$ or $k>n$ . This makes many identities valid without separate boundary cases. (dlmf.nist.gov)

The factorial formula follows by first counting ordered selections:

n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.

Each unordered selection appears $k!$ times, once for each ordering, so division by $k!$ removes the duplication. For example,

\binom{5}{2}=\frac{5\cdot4}{2\cdot1}=10.

Thus five people can form ten different two-person committees. The counting interpretation requires distinct objects, no repetition, and no significance attached to selection order. (discrete.openmathbooks.org)

Binomial expansion

For a nonnegative integer $n$ ,

(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k.

To obtain $a^{n-k}b^k$ , one chooses $b$ from exactly $k$ of the $n$ factors and $a$ from the others. There are $\binom{n}{k}$ such choices. For example,

(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4.

The formula holds for commuting quantities; it does not generally hold in this form for noncommuting matrices or operators. (dlmf.nist.gov)

Setting $a=1$ gives the generating function

\sum_{k=0}^{n}\binom{n}{k}x^k=(1+x)^n,

a polynomial whose coefficients record the numbers of subsets of each size. (dlmf.nist.gov)

Pascal’s triangle and recurrence

Arranging the coefficients by their upper index produces Pascal’s triangle, with rows numbered from zero:

\begin{array}{c|rrrrrr} n=0&1\\ n=1&1&1\\ n=2&1&2&1\\ n=3&1&3&3&1\\ n=4&1&4&6&4&1\\ n=5&1&5&10&10&5&1 \end{array}

Its interior entries satisfy Pascal’s recurrence relation:

\binom{n}{k} = \binom{n-1}{k-1}+\binom{n-1}{k}.

To prove this, distinguish one object. A $k$ -element selection either contains it, leaving $k-1$ objects to choose from the remaining $n-1$ , or excludes it, leaving $k$ objects to choose. These cases are disjoint and exhaustive. (discrete.openmathbooks.org)

The triangle predates Pascal’s work: earlier forms occurred in Indian, Chinese, and Islamic mathematical traditions. Pascal’s seventeenth-century treatment developed its properties and applications rather than introducing the underlying array for the first time. (opentext.uleth.ca)

Fundamental identities

Symmetry follows by pairing each selection with its complement:

\binom{n}{k}=\binom{n}{n-k}.

The row sum

\sum_{k=0}^{n}\binom{n}{k}=2^n

counts all subsets, or equivalently all elements of the power set. The alternating row sum is

\sum_{k=0}^{n}(-1)^k\binom{n}{k}=0 \qquad(n\geq1).

Both sums also follow by evaluating $(1+x)^n$ at $x=1$ and $x=-1$ . (dlmf.nist.gov)

Vandermonde’s identity states that

\sum_{j=0}^{r}\binom{m}{j}\binom{n}{r-j} =\binom{m+n}{r}.

It counts an $r$ -element selection from two disjoint sets by separating cases according to how many selected elements come from the first set. (dlmf.nist.gov)

Applications in probability and path counting

In probability, the binomial distribution describes the number $X$ of successes in $n$ independent trials with the same success probability $p$ . Its probability mass function is

\Pr(X=k)=\binom{n}{k}p^k(1-p)^{n-k}, \qquad 0\leq k\leq n.

The coefficient counts which $k$ trial positions contain successes; the remaining factors give the probability of each such outcome pattern. (statslab.cam.ac.uk)

Binomial coefficients also count lattice paths. A path from $(0,0)$ to $(a,b)$ , using only unit steps right and up, has $a+b$ steps. Choosing the positions of its $b$ upward steps gives

\binom{a+b}{b}

possible paths. Restrictions such as forbidden points or boundaries require additional counting arguments. (dlmf.nist.gov)

Computation and numerical limitations

For one coefficient, a multiplicative calculation avoids constructing three factorials. Put $r=\min(k,n-k)$ ; then

\binom{n}{k} =\prod_{i=1}^{r}\frac{n-r+i}{i}.

Starting with $c=1$ , the update

c\leftarrow\frac{c(n-r+i)}{i}

produces an integer at each stage when performed exactly. However, the intermediate multiplication can overflow a fixed-width integer even when the final coefficient fits. Cancelling common factors before multiplication reduces that risk. (commons.apache.org)

For many nearby coefficients, Pascal’s recurrence supports dynamic programming using addition. Direct factorial evaluation is mathematically correct but can create unnecessarily large intermediate values; exact integer calculation and approximate numerical calculation are therefore distinct computational tasks. (discrete.openmathbooks.org)

Generalized coefficients

For a complex number $\alpha$ and a nonnegative integer $k$ , the generalized definition is

\binom{\alpha}{k} = \frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}, \qquad \binom{\alpha}{0}=1.

For fixed $k$ , this is a polynomial in $\alpha$ . It agrees with ordinary binomial coefficients when $\alpha$ is a nonnegative integer, but otherwise need not represent a count. (dlmf.nist.gov)

These coefficients occur in the generalized binomial power series:

(1+x)^\alpha =\sum_{k=0}^{\infty}\binom{\alpha}{k}x^k, \qquad |x|<1,

using the branch analytic near $x=0$ . When $\alpha$ is a nonnegative integer, the series terminates and becomes the ordinary finite expansion. (dlmf.nist.gov)

A different extension is the multinomial coefficient:

\binom{n}{k_1,\ldots,k_s} =\frac{n!}{k_1!\cdots k_s!}, \qquad k_1+\cdots+k_s=n.

It counts assignments of $n$ distinct objects to labeled groups of prescribed sizes. The binomial coefficient is its two-group case. (dlmf.nist.gov)

References

Binomial Coefficientsdiscrete.openmathbooks.org
DLMF: §1.2 Elementary Algebradlmf.nist.gov
DLMF: §26.3 Lattice Paths: Binomial Coefficientsdlmf.nist.gov
The Arithmetic Triangle (Pascal's Triangle)opentext.uleth.ca
BinomialCoefficient.javacommons.apache.org
DLMF: §4.6 Power Seriesdlmf.nist.gov
DLMF: §26.4 Lattice Paths: Multinomial Coefficients and Set Partitionsdlmf.nist.gov