Binomial coefficient

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]

This editable Main Article is under development and subject to a disclaimer.

The binomial coefficient is a part of combinatorics. The binomial coefficient represent the number of possible choices of k elements out of n labelled elements (with the order of the k elements being irrelevant): that is, the number of subsets of size k in a set of size n. The binomial coefficients are written as ${\displaystyle {\tbinom {n}{k}}}$; they are named for their role in the expansion of the binomial expression (x+y)n.

Definition

${\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\geq k\geq 0}$

Example

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

Formulae involving binomial coefficients

Specifying a subset of size k is equivalent to specifying its complement, a subset of size n-k and vice versa. Hence

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

There is just one way to choose n elements out of n ("all of them") and correspondingly just one way to choose zero element ("none of them").

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

The number of singletons (single-element sets) is n.

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

The subset of size k out of n things may be split into those which do not contain the element n, which correspond to subset of n-1 of size k, and those which do contain the element n. The latter are uniquely specified by the remaining k-1 element which are drawn from the other n-1.

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

There are no subsets of negative size or of size greater than n.

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

Examples

${\displaystyle 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}}}$ = ${\displaystyle {n \choose k}={\frac {0}{1\cdot 2\cdot 3\cdots k}}=0}$
${\displaystyle k\ <0\ \mathrm {:} \ {n \choose n-k}={n \choose k}}$
${\displaystyle 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 ${\displaystyle {\tbinom {49}{6}}}$ is 13,983,816, so the probability to choose the correct six numbers is ${\displaystyle {\frac {1}{13,983,816}}={\frac {1}{49 \choose 6}}}$.

Binomial coefficients and prime numbers

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