Elementary combinatorics: Factorial and binomial coefficient
Properties of binomial coefficients
The following properties follow from the definition of the binomial coefficient \(\binom{n}{k}\).
Properties For natural numbers \(n\), \(k\) with \(k\le n\) we have: \[\begin{aligned}\binom{n}{k} &= \binom{n}{n-k}\\[0.25cm] \binom{n}{k} &= \frac{n}{k}\binom{n-1}{k-1}\quad\text{for }k\ge 1 \\[0.25cm] \binom{n}{0}&=\binom{n}{n}=1\\[0.25cm] \binom{n}{1}&=n\quad\text{for }n\ge 1\\[0.25cm] \binom{n}{2}&=\tfrac{1}{2}n(n-1)\quad\text{for }n\ge 2\\[0.25cm] \binom{n+1}{k}&= \binom{n}{k-1}+\binom{n}{k}\quad\text{for }k\ge 1 \end{aligned}\]
The last equality \[\binom{n+1}{k}= \binom{n}{k-1}+\binom{n}{k}\quad\text{for }k\ge 1\] can be interpreted as a recursive formula for calculating binomial coefficients. This leads to Pascal's triangle.
Pascal's triangle Pascal's triangle contains numbers arranged in a pyramid shape: \[\blue{\begin{array}{lccccccccccccc}
n=0\rightarrow\phantom{abc} &&&&&&&1&&&&&&\\[0.2cm]
n=1\rightarrow\phantom{abc} &&&&&&1&&1&&&&&\\[0.2cm]
n=2\rightarrow\phantom{abc} &&&&&1&&2&&1&&&&\\[0.2cm]
n=3\rightarrow\phantom{abc} &&&&1&&3&&3&&1&&&\\[0.2cm]
n=4\rightarrow\phantom{abc} &&&1&&4&&6&&4&&1&&\\[0.2cm]
n=5\rightarrow\phantom{abc} &&1&&5&&10&&10&&5&&1&\\[0.2cm]
n=6\rightarrow\phantom{abc} &1&&6&&15&&20&&15&&6&&1\\[0.2cm]
\ldots &&&&&&&\ldots&&&&&&&
\end{array}}\] There are ones along the left- and right-hand sides, and each number is the sum of its upper left and upper right neighbours.
This means that the binomial coefficient \(\binom{n}{k}\) is in the \(n\)-th row at position \(k=0,\ldots, n\).
For example, \(\binom{6}{0}=\binom{6}{6}=1\), \(\binom{6}{2}=15\) and \(\binom{6}{3}=20\).
