Multinomial Theorem

Prerequisite

Knowledge of Factorial

Where magic happens

We start off by asking the question: how many ways are there to arrange 4 0's and 3 1's in a row. For example, 0001110 or 0000111. 

If we treat all the 1's and 0's as distinct, perhaps by coloring like this: 0,0,0,0,1,1,1, we have $(4+3)!$ ways to arrange them. Fixing any possible configuration, for example 0000111, we see that we have $4!$ to permute the 1's, like 0000,111,0000111 ect... And similarly, $3!$ ways to permute the 0's in one configuration. So we count $4!3!$ times each time when we should have counted only once. Therefore, to correct the over-counting, the answer is $\displaystyle \frac{7!}{4!3!}$.

Quiz : How many ways are there to arrange 5 A's and 6 B's to form a weird string of characters?

It's easy to generalize the above result further. Suppose we have $n_1$ objects $x_1$, $n_2$ objects $x_2$,..., $n_k$ objects $x_k$. The number of distinct ways to arrange them in a row is $\displaystyle \frac{(n_1+n_2+...+n_k)!}{n_1!n_2!...n_k!}$

If you want to be cool, write it as $\displaystyle \binom{n_1+n_2+...+n_k}{n_1,n_2,...,n_k}$. This is the Multinomial Coefficient (Wiki).

Note that $\binom{n}{n,n-k}$ is often written as $\binom{n}{k}$ or $\binom{n}{n-k}$. This is called the binomial coefficient. It counts how many ways to choose $k$ places from $n$ places to put the 1's in. And of course, all the $n-k$ places left will go to 0's. $(*)$

Q&A

A natural question to ask is: what can I do with this new mathematical theorem? The natural answer is to do more math! So here is more math.

Binomial Theorem
Do you know that $(x+y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 +y^5$?
Wow how do I know that?

The trick is to look at $(x+y)^5$ in this form: $(x+y)(x+y)(x+y)(x+y)(x+y)$. First, notice that if you multiply everything out, at the first bracket you have two choices. You can start with either $x$ or $y$. You also have two choices to choose from in the second parenthesis, once you have chosen your first variable from the first.

The degrees of $x$ and $y$ must add up to $5$ since there are $5$ parentheses. Now, take a look at $x^4y$. The coefficient of $x^4y$ tells you the number of ways to can choose $4$ places/parentheses to take the $x's$ and in one parenthesis you will take $y$. Referring to $(*)$, you have $\binom{5}{4} = \binom{5}{1}=5$. The same principle applies to other terms, so $10 = \binom{5}{3}$.

Also, note that because at every parenthesis, you have $2$ choices, in total you will have $2.2.2.2.2=2^5$ possible ways. If you are not sure, what I'm talking about, please check out Multiplication Principle (James Tanton, youtube).
So $\binom{5}{0} + \binom{5}{1}+ \binom{5}{2}+ \binom{5}{3}+ \binom{5}{4}+ \binom{5}{5}=2^5$.

To sum this all up,
$(x+y)^n = \displaystyle \sum_{i=0}^{n}\binom{n}{i}x^iy^{n-i}$ and $\displaystyle \sum_{i=0}{n}\binom{n}{i}=2^n$
In general, $\displaystyle(x_1+x_2+...+x_k)^n = \sum_{i_1+i_2+...+i_k=n}\binom{n}{i_1,i_2,...,i_k}x_1^{i_1}x_2^{i_2}...x_k^{i_k}$

Relating Binomial and Multinomial 

We readily have the identity:
$\displaystyle \binom{n}{i_1,i_2,...,i_k}=\binom{n}{i_1}\binom{n-i_1}{i_2}\binom{n-i_1-i_2}{i_3}...\binom{n-i_1-i_2-...-i_{k-1}}{i_k}$

Example : $\displaystyle \binom{7}{2,2,3}=\binom{7}{2}\binom{5}{2}\binom{3}{3}$ (**)

Note that the two sides of (**) are just two ways of counting the same thing. Think of it as the way of counting the number of ways to arrange 2 A's, 2 B's and 3 C's. The right hand side counts it directly, while the left hand side takes a step-by-step approach, choosing the places for A's first, then B's and then C's.