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 ${n \choose k}$

Definition

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {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 \ge k \ge 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 coeffizient is used in the Lottery. For example the german Lotto have a System, where you can choose 6 numbers from the numbers 1 to 49. The binomial coeffizient ${49 \choose 6}$ is 13.983.816, so the probability to choose the correct six numbers is 1 to 13.983.816 ${49 \choose 6}=13.983.816$

binomial coefficients and prime numbers

Iff p is a prime number than p divides ${p \choose k}$ for every $1<k<p\$. The converse is true.