Combinatorics Equation I am studying for a test on combinatorics and I recently came across this equation I had lost in my notes.

I do not really have a clue as to why this equation holds or its higher-level meaning. If anyone can offer some explanation as to why this equation is true for any positive integer k and non-negative integer n it would be greatly appreciated. It would even better if someone could give any insights on how I can prove this to be true so that it will be more mathematically intuitive.
 A: I think this is best shown with a simple example. The equation is rather scary in full generality, even though the concept it describes is simple.
Let's start with the simplest example: $(x+y)^2$. We can multiply this out to see
$$(x+y)^2 = x^2 + 2xy + y^2.$$
If I prime you by saying "pascal's triangle", you might notice that the coefficients of this expression $(1 \quad 2 \quad 1)$ form a row of pascal's triangle. Let's try the next one:
$$(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$$
The coefficients of this $(1 \quad 3 \quad 3 \quad 1)$ are also a row of pascal's triangle. You may or may not be aware of this (shocking!) connection, but in general
$$(x+y)^n = \text{something } x^n + \text{something } x^{n-1}y + \ldots + \text{something } xy^{n-1} + \text{something } y^n$$
It turns out that these "somethings" will always be the $n$th row of pascal's triangle!

Let's take a moment to think about that. This is one of the places where mathematics exists to let us be lazy! If you wanted to expand out $(x+y)^{100}$, you would spend all day doing it if you wanted to distribute everything out. Moreover you would almost certainly make a mistake somewhere along the way. But this gives us a quick trick™️ for computing these easily! Simply find the $100$th row of pascal's triangle (which is easy, if tedious, to do) and we're done.
Of course, this still sounds tedious... Is there a way for us to be lazier?
Always!

The next step comes from combinatorics, which is why you're being taught this. Let's think about what the coefficients really mean in these expressions. Why do we have $1 \quad 3 \quad 3 \quad 1$ showing up here?
Well, let's do some distribution and see what happens:
$$(x+y)^2 = xx + \color{green}{xy + yx} + yy$$
$$(x+y)^3 = xxx + \color{blue}{xyy + yxy + yyx} + \color{red}{xxy + xyx + yxx} + yyy$$
Notice what's happening! When we do the distribution, we get every possible choice of $x$s and $y$s. Then, since $xy = yx$, we can reorder them so that they all look like $x^iy^{n-i}$. So our coefficient on $x^i y^{n-i}$ is exactly the number of ways to have $i$ xs and $n-i$ ys in a term!
But we know what that coefficient is! We want to count the number of ways to have $i$ xs and $n-i$ ys in a string of length $n$. This is what binomial coefficients are made for!
$$\text{The coefficient of } x^iy^{n-i} \text{ is } \frac{n!}{i!(n-i)!}$$
We write this as $\binom{n}{i}$, but this is kind of a special case. When we only have $x$ and $y$, things are easy. If we know where the xs go, we have no choice where to put the ys! More generaly we could write this as $\binom{n}{i, n-i}$ to indicate we're choosing $i$ xs and $n-i$ ys.

Ok, last step! What are these multinomial coefficients floating around? Well, they exist to solve this same problem for more variables!
Say you want to calculate $(x+y+z)^{10}$, but you're too lazy to expand it out. Keeping in mind what we've done so far, you might come up with a clever strategy:
You notice the terms of $(x+y+z)^{10}$ are going to be all of the strings of $10$ xs, ys, and zs. Then the coefficient of $x^i y^j z^{10 - i - j}$ is going to be exactly the number of ways you can choose that string.
Again, we know the answer to this problem! How many ways are there to split $10$ things into $3$ groups of size $i$ $j$ and $10-i-j$? There's exactly
$$\binom{10}{i, j, 10-i-j} = \frac{10!}{i! j! (10 - i - j)!}$$
many ways to do this. So that is the coefficient!

More generally, if you want the coefficient of $x^iy^jz^kw^l$ in $(x+y+z+w)^n$, you know what to do! It's $\binom{n}{i,j,k,l}$. Of course, we should have $i+j+k+l = n$, since each term will have $n$ letters in total.
And now, finally, we find ourselves with the formula you started with.
What is $(x_1 + x_2 + \ldots + x_k)^n$?
Well, the coefficient of $x_1^{i_1}x_2^{i_2}\ldots x_k^{i_k}$ is exactly $\binom{n}{i_1, i_2, \ldots, i_k}$. So if we want to express this as a sum, we see:
$$(x_1 + x_2 + \ldots + x_k)^n = \sum \binom{n}{i_1, i_2, \ldots, i_k} x_1^{i_1} x_2^{i_2} \ldots x_k^{i_k}$$
here the constraint on the sum is, again, that $i_1 + i_2 + \ldots + i_k = n$. Because there must still be $n$ letters in any given term.
But people don't like writing $x_1 \ldots x_n$, so we write it using $\prod$ instead. This gives us exactly the formula that you were initially asking about:
$$(x_1 + x_2 + \ldots x_k)^n = \sum_{i_1 + \ldots + i_k = n} \binom{n}{i_1, i_2, \ldots i_k} \prod x_j^{i_j}$$

As some quick exercises to see that you understand:

*

*What is the coefficient of $x^3 y^2 z^4$ in $(x+y+z)^9$?

*Can you expand out in full the polynomial $(w+x+y+z)^3$ without foiling?


I hope this helps ^_^
