For natural numbers $k\leq n$, the binomial coefficient $\binom{n}{k} = \#\binom{[n]}{k}$ is the number of $k$-element subsets of $[n]$. Equivalently, it is the number of function $f:[n]\to [1,2]$ such that $\# f^{-1}(1)=k$ (and hence $\# f^{-1}(2)=n-k$): there is a bijection between such functions and $\binom{[n]}{k}$ where the function $f:[n]\to [1,2]$ corresponds to the subset $f^{-1}(1)\subseteq [n]$. More generally, for natural numbers $n, k_{1},k_{2},\dots, k_{r}$, with $k_{1}+k_{2} +\dots+k_{r}=n$, we consider the number of functions $f:[n]\to \{ 1,2,\dots,r \}$ ($r$-colourings of $n$ beads) such that $\# f^{-1}(1)=k_{1}$, $\# f^{-1}(2)=k_{2}$, and so on. First we choose $f^{-1}(1)$: there are $\binom{n}{k_{1}}$ possibilities. Then we choose $f^{-1}(2)$: there are $\binom{n-k_{1}}{k_{2}}$ possibilities. Continuing like this, we find that there are $\begin{equation}{n \choose k_{1},k_{2},\dots,k_{r}}:= \frac{n!}{k_{1}!\cdot\left(n-k_1\right)!} \frac{\left(n-k_1\right)!}{k_{2}!\cdot\left(n-k_1-k_2\right)!} \cdots \frac{\left(n-k_1-\cdots-k_{r-1}\right)!}{k_{r}!\cdot\left(n-k_1-\cdots-k_r\right)!}=\frac{n!}{k_{1}!\cdots k_{r}!} \end{equation}$such functions which is known as a multinomial coefficient for the statement below. > [!NOTE] Theorem (Multinomial Theorem) > For natural numbers $n$, $(a_{1}+a_{2}+\dots a_{r})^n = \sum_{\substack{k_{1}+k_{2}+\dots+k_{r}=n\\ k_{i}\geq 0 }} {n \choose k_{1},k_{2},\dots,k_{r}} a_{1}^{k_{1}}a_{2}^{k_{2}}\cdots a_{r}^{k_{r}}$where ${n \choose k_{1},k_{2},\dots,k_{r}}= \frac{n!}{k_{1}!k_{2}!\dots k_{r}!}$ is known as a multinomial coefficient. ###### Proof A function $f:[n]\to [r]$ corresponds uniquely to the term in the expansion of the RHS where $f$ corresponds to the term $a_{f(1)}a_{f(2)}\cdots a_{f(n)}$. So the coefficient of $a_{1}^{k_{1}}a_{2}^{k_{2}}\cdots a_{r}^{k_{r}}$ is the number of functions $f:[n]\to [k]$ such that $k_{i}$ elements maps to $i$ (that is, $\# f^{-1}(i)=k_{i}$). As shown already, this indeed the multinomial coefficient as defined above. $\blacksquare$