Binomial coefficients/Introduction/Section

Definition

Let ${}k$ and ${}n$ denote natural numbers with ${}k\leq n$. Then

${}{\binom {n}{k}}:={\frac {n!}{k!(n-k)!}}\,$

is called the binomial coefficient ${}n$ choose ${}k$

One can write this fraction also as

${\frac {n(n-1)(n-2)\cdots (n-k+2)(n-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}},$

because th factors from ${}(n-k)!$ are also in ${}n!$. In this representation, we have the same number of factors in the numerator and in the denominator. Sometimes it is useful to allow also negative ${}k$ or ${}k>n$ and define in these cases the binomial coefficients to be ${}0$.

From the very definition, it is not immediately clear that the binomial coefficients are natural numbers. This follows from the following relationship.

The triangle of the binomial coefficients was known in India and Persia around 1000,

in China it is called triangle of Yanghui (after Yang Hui (about 1238-1298)),

in Europe it is called the triangle of Pascal (after Blaise Pascal (1623-1662)).

Lemma

The binomial coefficients fulfill the recursive relationship

${}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,.$

Proof

See exercise.

$\Box$