3.7 Factorial and binomial coefficient

The factorial of a positive natural number $n$ is defined as

\begin{equation*} n! := \prod_{k=1}^n k. \end{equation*}

The factorial of zero is defined separately, $0! := 1$. The factorial of negative integers is not defined.

The factorial can be extended to all real numbers with the exception of negative integers. This extention is represented by a special function $\Gamma$, which has the property that $\Gamma(n+1) = n!$ for $n\in\N_0$ and, moreover, $\Gamma(x+1) = x\Gamma(x)$ for $x\in\mathbb{R}\smallsetminus\{\ldots,-2,-1,0\}$. The reader will certainly meet the $\Gamma$ function in the Probability and Statistics course (BIE-PST).

The binomial coefficient is often used in practical calculations. For a natural $n$ and integer $k$ such that $0 \leq k \leq n$ we define

\begin{equation*} \binom{n}{k} := \frac{n!}{(n-k)!k!}. \end{equation*}

Although this definition looks confusing, the actual meaning of a binomial coefficient $\binom{n}{k}$ is simple. This number represents the number of possible selections of $k$ items out of $n$ objects where the order of selection does not matter and where we do not allow repeted selection of an item.

Often it is useful to know all binomial coefficients for a given $n$. Here, the Pascal's triangle will come in handy. First we will observe the equality

\begin{equation}\label{eq-komb}\tag{3.20} \binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}. \end{equation}


\begin{equation*} \begin{aligned} \binom{n}{k-1} + \binom{n}{k} &= \frac{n!}{(n-k+1)!(k-1)!} + \frac{n!}{(n-k)!k!} = \\ &= \frac{n!}{(n-k)!(k-1)!} \Bigg( \underbrace{\frac{1}{n-k+1} + \frac{1}{k}}_{\frac{n+1}{(n-k+1)k}} \Bigg) = \\ &= \frac{(n+1)!}{(n-k+1)!k!} = \binom{n+1}{k}. \end{aligned} \end{equation*}

Now imagine all binomial coefficients organised as a Pascal's triangle. The formula (3.20) then says that the sum of neighbouring binomial coefficients will be located one row below. See Figure 3.8.

The rows of a Pascal's triangle are enumerated starting from zero, i.e. the 0th row contains only $1$, the first row reads $1,1$, the second row reads $1,2,1$, etc. This method of enumeration is chosen so that $\binom{n}{k}$ lie in row $n$. It also makes it easer to remember the binomial theorem (see equation 2.1), the coefficients for $(a+b)^n$ are placed in row $n$.

Figure 3.8: Pascal's triangle.