Binomial coefficient

The binomial coefficient is a part of combinatorics. The binomial coefficient represent the number of possible choices of k elements out of n elements. The binomial coefficient is written as ${\tbinom {n}{k}}$.

Definition

${n \choose k}={\frac {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}{1\cdot 2\cdot 3\cdots k}}={\frac {n!}{k!\cdot (n-k)!}}\quad \mathrm {for} \ n\geq k\geq 0$

Example

${8 \choose 3}={\frac {8\cdot 7\cdot 6}{1\cdot 2\cdot 3}}=56$

Formulas involving binomial coefficients

${n \choose k}={n \choose n-k}$

${n \choose n}={n \choose 0}=1\quad \mathrm {for} \ n\geq 0$

${n \choose 1}=n\quad \mathrm {for} \ n\geq 1$

${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$

${n \choose k}=0\quad \mathrm {if} \ k>n\ \mathrm {or} \ k\ <0$

Examples

$k>n\ \mathrm {:} \ {n \choose k}={\frac {n\cdot n-1\cdot n-2\cdots n-n\cdots n-k+1}{1\cdot 2\cdot 3\cdots k}}$ = ${n \choose k}={\frac {0}{1\cdot 2\cdot 3\cdots k}}=0$

$k\ <0\ \mathrm {:} \ {n \choose n-k}={n \choose k}$

$n-k>n\Rightarrow {n \choose n-k}=0$

Usage

The binomial coefficient can be used to describe the mathematics of lottery games. For example the German Lotto has a system, where you can choose 6 numbers from the numbers 1 to 49. The binomial coefficient ${\tbinom {49}{6}}$ is 13,983,816, so the probability to choose the correct six numbers is ${\frac {1}{13,983,816}}={\frac {1}{49 \choose 6}}$.

Binomial coefficients and prime numbers

If p is a prime number then p divides ${\tbinom {p}{k}}$ for every $1<k<p\$. The converse is also true.