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 theoremapplied 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 coefficientsappear.

•
$n\\choose r$ constitute the coefficients when expanding thebinomial $(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 numberof strings consisting of ones and zeros with $r$ ones and $n-r$ zeros.This equivalency comes from the fact thatif $S$ be a finite set with $n$ elements, ${n\\choose r}$ is the number of distinctsubsets 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 functionfor $T$ ). For each $T\\in\\mathcal{P}(S)$ , $X_{T}$ can be used to produce a unique bitstring of length $n$ with exactly $r$ ones.

Notes

The ${n\\choose r}$ notation was first introduced byvon Ettinghausen [1] in 1826, altoughthese numbers have been used long before that. Seethis page (http://planetmath.org/PascalsTriangle) for some notes on their history.Although the standard mathematical notation for the binomial coefficients is $n\\choose r$ , thereare 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.