You are here
Homebinomial coefficient
Primary tabs
binomial coefficient
For integers $n\geq r\geq 0$ we define
${n\choose r}=\frac{n!}{(nr)!r!}$ 
and call such numbers binomial coefficients.
Properties.
1. $n\choose r$ is an integer (proof.).
2. ${n\choose r}={n\choose nr}$.
3. ${n\choose r1}+{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 $(11)^{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.

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 $nr$ 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 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.
Mathematics Subject Classification
11B65 no label found05A10 no label found19D55 no label found19K33 no label found19D10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Attached Articles
upper and lower bounds to binomial coefficient by rspuzio
sum of powers of binomial coefficients by Andrea Ambrosio
an algebraic identity leading to Wilson's theorem by GeraW
generalized binomial coefficients by pahio
${n\choose r}$ is an integer by matte
divisibility of primepower binomial coefficients by rm50