# ¶ Binomial Coefficients

The numbers $\left(\genfrac{}{}{0px}{}{n}{k}\right)\binom\left\{n\right\}\left\{k\right\}$ (read as $nn$ choose $kk$) are known as the binomial coefficients.

## ¶ The Binomial Theorem

$\left(a+b{\right)}^{n}=\left(\genfrac{}{}{0px}{}{n}{0}\right){a}^{n}{b}^{0}+\left(\genfrac{}{}{0px}{}{n}{1}\right){a}^{n-1}{b}^{1}+\left(\genfrac{}{}{0px}{}{n}{2}\right){a}^{n-2}{b}^{2}+\dots \left(\genfrac{}{}{0px}{}{n}{n-1}\right){a}^{1}{b}^{n-1}+\left(\genfrac{}{}{0px}{}{n}{n}\right){a}^{0}{b}^{n}=\sum _{k=0}^{n}\left(\genfrac{}{}{0px}{}{n}{k}\right){a}^{n-k}{b}^{k}\left(a+b\right)^n=\binom\left\{n\right\}\left\{0\right\}a^nb^0+\binom\left\{n\right\}\left\{1\right\}a^\left\{n-1\right\}b^1+\binom\left\{n\right\}\left\{2\right\}a^\left\{n-2\right\}b^2+\dots\binom\left\{n\right\}\left\{n-1\right\}a^\left\{1\right\}b^\left\{n-1\right\}+\binom\left\{n\right\}\left\{n\right\}a^0b^n=\sum^\left\{n\right\}_\left\{k=0\right\} \binom\left\{n\right\}\left\{k\right\}a^\left\{n-k\right\}b^\left\{k\right\}$

This is why $\left(\genfrac{}{}{0px}{}{n}{k}\right)\displaystyle\binom\left\{n\right\}\left\{k\right\}$ is called the binomial coefficient.

## ¶ Pascal's Triangle

Source: Figure 1.20, Bertsekas and Tsitsiklis (2008).

From the figure above, we can derive the following property of the binomial coefficient:

$\left(\genfrac{}{}{0px}{}{n}{k}\right)=\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0px}{}{n-1}{k}\right)\binom\left\{n\right\}\left\{k\right\}=\binom\left\{n-1\right\}\left\{k-1\right\}+\binom\left\{n-1\right\}\left\{k\right\}$

# ¶ Multinomial Coefficients

A combination is a choice of $kk$ elements out of an $nn$-element set without regard to order.

A combination can be viewed as a partition of the set in two: one part contains $kk$ element and the other part contains the remaining $n-kn-k$. We generalize by considering partitions into $rr$ subsets, ${n}_{1},{n}_{2},\dots ,{n}_{r}n_1,n_2,\dots,n_r$, whose sum is equal to $nn$.

The multinomial coefficient is:

$\left(\genfrac{}{}{0px}{}{n}{{n}_{1}}\right)\left(\genfrac{}{}{0px}{}{n-{n}_{1}}{{n}_{2}}\right)\left(\genfrac{}{}{0px}{}{n-{n}_{1}-{n}_{2}}{n3}\right)\cdots \left(\genfrac{}{}{0px}{}{n-{n}_{1}-\cdots -{n}_{r-1}}{{n}_{r}}\right)\binom\left\{n\right\}\left\{n_1\right\}\binom\left\{n-n_1\right\}\left\{n_2\right\}\binom\left\{n-n_1-n_2\right\}\left\{n3\right\}\cdots\binom\left\{n-n_1-\cdots-n_\left\{r-1\right\}\right\}\left\{n_r\right\}$

which is equal to

$\frac{n!}{{n}_{1}!\left(n-{n}_{1}\right)!}\frac{\left(n-{n}_{1}\right)!}{{n}_{2}!\left(n-{n}_{1}-{n}_{2}\right)!}\frac{\left(n-{n}_{1}-{n}_{2}\right)!}{{n}_{3}!\left(n-{n}_{1}-{n}_{2}-{n}_{3}\right)!}\cdots \frac{\left(n-{n}_{1}-\cdots -{n}_{r-1}\right)!}{{n}_{r}!\left(n-{n}_{1}-\cdots -{n}_{r-1}-{n}_{r}\right)!}\frac\left\{n!\right\}\left\{n_1!\left(n-n_1\right)!\right\}\frac\left\{\left(n-n_1\right)!\right\}\left\{n_2!\left(n-n_1-n_2\right)!\right\}\frac\left\{\left(n-n_1-n_2\right)!\right\}\left\{n_3!\left(n-n_1-n_2-n_3\right)!\right\}\cdots \frac\left\{\left(n-n_1-\cdots -n_\left\{r-1\right\}\right)!\right\}\left\{n_r!\left(n-n_1-\cdots -n_\left\{r-1\right\}-n_r\right)!\right\}$

collect terms, we get:

$\frac{n!}{{n}_{1}!{n}_{2}!\cdots {n}_{r}!}=\left(\genfrac{}{}{0px}{}{n}{{n}_{1},{n}_{2},\cdots \text{\hspace{0.17em}},{n}_{r}}\right)\frac\left\{n!\right\}\left\{n_1!n_2!\cdots n_r!\right\}=\binom\left\{n\right\}\left\{n_1,n_2,\cdots,n_r\right\}$