# Binomial coefficients/Introduction/Section

## Definition

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

${\displaystyle {}{\binom {n}{k}}:={\frac {n!}{k!(n-k)!}}\,}$
is called the binomial coefficient ${\displaystyle {}n}$ choose ${\displaystyle {}k}$

One can write this fraction also as

${\displaystyle {\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 ${\displaystyle {}(n-k)!}$ are also in ${\displaystyle {}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 ${\displaystyle {}k}$ or ${\displaystyle {}k>n}$ and define in these cases the binomial coefficients to be ${\displaystyle {}0}$.

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

## Lemma

The binomial coefficients fulfill the recursive relationship

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

### Proof

${\displaystyle \Box }$