Binomial coefficient

From Citizendium, the Citizens' Compendium

Jump to: navigation, search

Main Article

Talk

Related Articles ^[?]

Bibliography ^[?]

External Links ^[?]

This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

[edit intro]

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 $\tbinom{n}{k}$ ; they are named for their role in the expansion of the binomial expression (x+y)ⁿ.

1 Definition
- 1.1 Example
2 Formulae involving binomial coefficients
- 2.1 Examples
3 Usage
4 Binomial coefficients and prime numbers

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 \ge k \ge 0$

Example

${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

${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").

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

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

${n \choose 1} = n\quad\mathrm{for}\ n \ge 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.

${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.

${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}}$ .