Algebra: Binomial Coefficient
Binomial coefficients and factorials
We look at Pascal's triangle in its original schematic form: \[ \begin{array}{rrrrrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7& 8 & 9 & 10 & \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & & \\ 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 & & & \\ 1 & 5 & 15 & 35 & 70 & 126 & 210 & & & & \\ 1 & 6 & 21 & 56 & 126 & 252 & & & & & \\ 1 & 7 & 28 & 84 & 210 & & & & & & \\ 1 & 8 & 36 & 120 & & & & & & & \\ 1 & 9 & 45 & & & & & & & & \\ 1 & 10 & & & & & & & & & \\ 1 & & & & & & & & & & \end {array}\]
Beside rows and columns, we will also look at anti-diagonals; these are the rows of numbers that you find on a line from northeast to southwest. The first anti-diagonal is #1#. The second is #1,2,1#, and the sixth #1,6,15,20,15,6,1#.
binomial coefficient
Let #n# and #k# be non-negative integers with #k\le n#. The #(k+1)# number on the #(n+1)# anti-diagonal can be written as \(\binom{n}{k}\).
This is called the binomial coefficient of #n# and #k#, or simply ''\(n\) choose \(k\)'.'
In terms of Pascal's triangle the binomial coefficient \(\binom{n}{k}\) is the #(k+1)# th number on the #(n+1)# th row.
The first number on the top left is the first (and only) number from the first anti-diagonal. It is equal to #1# , so \(\binom{0}{0}=1\).
The way this number is created, is determined by the following formula.
Characterizing properties for binomial coefficients For all non-negative integers #n# and #k# with #k\le n# we have:
\[\binom{n}{k}= \begin{cases}\displaystyle\binom{n-1}{k-1}+\binom{n-1}{k}&\text{ if } n\gt0 \text{ and } k\gt 0\\ \phantom{\displaystyle\binom{n}{k-1}}\ 1&\text{ otherwise}\end {cases}\]
The second part of the formula implies that \(\binom{n}{0}=\!\binom{n}{n}=1\) for all \(n\). With this formula one can calculate every binomial coefficient in a finite number of steps.
\[\begin{array}{rcl}\binom{4}{2} &=& \binom{3}{1} + \binom{3}{2} \\ \\ &=& \binom{2}{0} + \binom{2}{1} + \binom{2}{1} + \binom{2}{2} \\ \\&=& 1 + 2\cdot \binom{2}{1} + 1 \\ \\ &=& 1+2\cdot\left(\binom{1}{0}+\binom{1}{1}\right)+1\\ \\ &=& 1+2\cdot\left(1+1\right)+1\\ \\ &=& 6\end{array}\]
It is inconvenient to calculate in this way. It can be done in a simpler way. But for this we first need to discuss \(n!\) (pronounced as ''\(n\) - factorial'').
factorial
\[ \begin{array}{rcl} 0! &=& 0 \\ n! &= &1\times\cdots\times n\qquad\text{for every positive number }n\end {array}\]
Examples \[ \begin{array}{rcl} 1! &=&1\\ 2! &=& 1\times 2 = 2\\ 3! &=& 1\times 2\times 3 = 6\\ 4! &=& 1\times 2\times 3\times 4 = 24\end {array}\]
With this notation we have:
\[\binom{n}{k}=\frac{n!}{k!(n-k)!}\]
Now the earlier calculation would be: \[\binom{4}{2} =\frac{4!}{2!\,2!} = \frac{24}{2\times 2}=6\] Practically you never have to calculate the three factorials separately. Just use the definition of \(n!\) which in this case leads to \[\binom{4}{2} =\frac{4!}{2!\,2!}=\frac{1\times 2\times 3\times 4}{(1 \times 2)\times(1\times 2)}=\frac{3\times 4}{1\times 2} = \frac{12}{2}=6\] In general we have:
\[\binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{(n-k+1)\times\cdots\times (n-1)\times n}{1\times 2\times\cdots\times k}\]
Explanation: \(\binom{5}{3}=\frac{5!}{3!(5-3)!}=\frac{5!}{3!\,2!}=\frac{3\cdot 4\cdot 5}{1\cdot 2\cdot 3}=10\).
Or visit omptest.org if jou are taking an OMPT exam.
