3.7 Factorial and binomial coefficient

1 Introduction 2 Mathematics is not only about computing 3 Basic concepts 3.1 Note on mathematical notation 3.2 Sets and set operations 3.3 Number sets 3.4 Significant subsets of real numbers 3.5 Propositions and logical connectives 3.6 Abbreviated writing of sums and products 3.7 Factorial and binomial coefficient 3.8 Important constants 4 Elementary functions 5 Analytical geometry 6 Warning 7 List of the used symbols Index Bibliography

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}

Indeed,

\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.

section

Chapter