binomial coefficient

For integers $n\geq r\geq 0$ we define

{n\choose r}=\frac{n!}{(n-r)!r!}

and call such numbers binomial coefficients.

Properties.

1.

$n\choose r$ is an integer (proof. (http://planetmath.org/NchooseRIsAnInteger)).
2.

${n\choose r}={n\choose n-r}$ .
3.

${n\choose r-1}+{n\choose r}={n+1\choose r}$ (Pascal’s rule).
4.

${n\choose 0}=1={n\choose n}$ for all $n$ .
5.

${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots+{n\choose n}=2^{n}$ .
6.

${n\choose 0}-{n\choose 1}+{n\choose 2}-\cdots+(-1)^{n}{n\choose n}=0$ for $n>0$ .
7.

$\sum_{t=k}^{n}{t\choose k}={n+1\choose k+1}$ .

Properties 5 and 6 are the binomial theorem applied to $(1+1)^{n}$ and $(1-1)^{n}$ , respectively, although they also have purely combinatorial meaning.

Motivation

Suppose $n\geq r$ are integers. The below list shows some examples where the binomial coefficients appear.

•

$n\choose r$ constitute the coefficients when expanding the binomial $(x+y)^{n}$ – hence the name binomial coefficients. See Binomial Theorem.
•

$n\choose r$ is the number of ways to choose $r$ objects from a set with $n$ elements.
•

On the context of computer science, it also helps to see ${n\choose r}$ as the number of strings consisting of ones and zeros with $r$ ones and $n-r$ zeros. This equivalency comes from the fact that if $S$ be a finite set with $n$ elements, ${n\choose r}$ is the number of distinct subsets of $S$ with $r$ elements. For each subset $T$ of $S$ , consider the function

$X_{T}\colon S\rightarrow\{0,1\}$

where $X_{T}(x)=1$ whenever $x\in T$ and $0$ otherwise (so $X_{T}$ is the characteristic function for $T$ ). For each $T\in\mathcal{P}(S)$ , $X_{T}$ can be used to produce a unique bit string of length $n$ with exactly $r$ ones.

Notes

The ${n\choose r}$ notation was first introduced by von Ettinghausen [1] in 1826, altough these numbers have been used long before that. See this page (http://planetmath.org/PascalsTriangle) for some notes on their history. Although the standard mathematical notation for the binomial coefficients is $n\choose r$ , there are also several variants. Especially in high school environments one encounters also ${C}(n,r)$ or ${C}^{n}_{r}$ for ${n\choose r}$ .

Remark. It is sometimes convenient to set ${n\choose r}:=0$ when $r>n$ . For example, property 7 above can be restated: $\sum_{t=1}^{n}{t\choose k}={n+1\choose k+1}$ . It can be shown that ${n\choose r}$ is elementary recursive.

References

1 N. Higham, Handbook of writing for the mathematical sciences, Society for Industrial and Applied Mathematics, 1998.

Title	binomial coefficient
Canonical name	BinomialCoefficient
Date of creation	2013-03-22 11:47:25
Last modified on	2013-03-22 11:47:25
Owner	matte (1858)
Last modified by	matte (1858)
Numerical id	32
Author	matte (1858)
Entry type	Definition
Classification	msc 11B65
Classification	msc 05A10
Classification	msc 19D55
Classification	msc 19K33
Classification	msc 19D10
Synonym	combinations
Synonym	choose
Related topic	PascalsRule
Related topic	BinomialTheorem
Related topic	BernoulliDistribution2
Related topic	MultinomialTheorem
Related topic	ProofOfLucassTheorem2
Related topic	Factorial
Related topic	CentralBinomialCoefficient
Related topic	PascalsTriangle
Related topic	TaylorSeriesViaDivision
Related topic	CombinationsWithRepeatedElements
Related topic	NonIsomorphicGroupsOfGivenOrder
Related topic	AppellSeque