Elementary combinatorics: Factorial and binomial coefficient
Factorial
Just as you shorten \(\blue{\overbrace{\color{black}{a \times a \times \cdots \times a}}^{n\mathrm{\;times}}}\) to \(a^n\), you also have a short notation for \(n\cdot (n-1)\cdots 3\cdot 2\cdot 1\), which is \(n!\). We pronounce this as ``\(n\) factorial''.
The factorial of a natural number \(n\) is defined as follows: \[\begin{cases} n! =n\cdot (n-1)\cdots 3\cdot 2\cdot 1 & \text{for } n\in\mathbb{N}\backslash\{0\}\\ 0!=1&\end{cases}\]
We can also define the factorial via an improper integral in the form of the gamma function: \[\Gamma(x)=\int_{0}^{\infty} t^{x-1}e^{-t}\,\dd t\] For natural numbers \(n\) then holds: \[n!=\Gamma(n+1)\] But because the gamma function exists for all numbers except negative integers, you can extend the factorial to more than only the natural numbers. For example: \[\begin{aligned} (-\tfrac{1}{2})! &= \Gamma(\tfrac{1}{2})\\[0.25cm] &= \int_{0}^{\infty} t^{-\frac{1}{2}}e^{-t}\,\dd t\\[0.25cm] &=2\cdot \int_{0}^{\infty} e^{-u^2}\,\dd u & \blue{\text{substitution }u=t^{\frac{1}{2}}\text{ and } \dd u=t^{-\frac{1}{2}}\,\dd t}\\[0.25cm] &= 2\cdot \frac{\sqrt{\pi}}{2} & \blue{\text{standard integraa}}\\[0.25cm] &= \sqrt{\pi}\end{aligned}\] The graph of the factorial function looks as follows:
Application 1 The number of ways in which \(n\) different objects can be arranged is equal to \(n!\).
In other words, the number of permutations of \(n\) things (i.e. the number of arrangements of \(n\) things) is equal to \(n!\).
Application 2 The number of permutations of \(n\) things of which \(m\) are the same and the remainder is different is equal to \(\dfrac{n!}{m!}\).
Properties For all \(m,n\in\mathbb{N}\) with \(m<n\) the following rules apply: \[\begin{aligned} n!&=n\cdot (n-1)!\\[0.25cm] \frac{n!}{m!} &= (m+1)\cdot (m+2)\cdots (n-1)\cdot n\end{aligned}\]
