higher college level combinatorics

Question

Show the following equality: $$\sum_{n_1,\ldots,n_k\geq 0} \min(n_1,\ldots,n_k)x_1^{n_1} \cdots x_k^{n_k}=\frac{x_1\cdots x_k}{(1-x_1)\dots(1-x_k)(1-x_1x_2\cdots x_k)}.$$

This is a problem from Stanley's Enumerative Combinatorics, and I am trying to prove the equality. I tried to plug in some some numbers and this equality stays true, so I guess induction would work~ but I would also like to some other ways of showing this equality.

Answer 1

Looking at the RHS, you should know that $\frac{1}{(1-x_i)} = (1+x_i+x_i^2+x_i^3+\dots)$

Let us simplify notation a little by letting $x_1x_2x_3\dots x_k=X$

and since the RHS is a product of such terms you have:

$=X(1+x_1+x_1^2+x_1^3+\dots)(1+x_2+x_2^2+x_2^3+\dots)\dots(1+x_k+x_k^2+x_k^3+\dots)(1+X+X^2+X^3+\dots)$

Distributing the $x_1x_2\dots x_k=X$ into its respective parenthesis, this is then

$=(x_1+x_1^2+x_1^3+\dots)(x_2+x_2^2+x_2^3+\dots)\dots(x_k+x_k^2+x_k^3+\dots)(1+X+X^2+X^3+\dots)$

Can you figure out how many ways there are by looking at the RHS to get a specific outcome such as $x_1^3x_2^2x_3^4\dots x_k^4$?

---

Looking at a smaller example, let $k=3$ and we ask what the coefficient is for $x_1^4x_2^3x_3^5$

$(x_1+x_1^2+x_1^3+x_1^4+\dots)(x_2+x_2^2+x_2^3+x_2^4+\dots)(x_3+x_3^2+x_3^3+x_3^4+\dots)(1+X+X^2+X^3+\dots)$

We try to pick a term from each parenthesis and count how many ways we could have made such a selection. We could have for example taken:

$(x_1+x_1^2+x_1^3+\color{red}{x_1^4}+\dots)(x_2+x_2^2+\color{red}{x_2^3}+x_2^4+\dots)(x_3+x_3^2+x_3^3+x_3^4+\color{red}{x_3^5}+\dots)(\color{red}{1}+X+X^2+X^3+\dots)$

Or we could have taken $(x_1+x_1^2+\color{red}{x_1^3}+x_1^4+\dots)(x_2+\color{red}{x_2^2}+x_2^3+x_2^4+\dots)(x_3+x_3^2+x_3^3+\color{red}{x_3^4}+\dots)(1+\color{red}{X}+X^2+X^3+\dots)$

In general, if we first pick from $(1+X+X^2+X^3+\dots)$, given our specific choice there will be exactly one choice (or zero choices) from each of the other parenthesis to reach the target product. The question now is how many different choices from $(1+X+X^2+\dots)$ are legal and would allow us to reach our desired product. There are in fact $\min(n_1,n_2,\dots,n_k)$ many such choices, which yields the identity asked.

Explicitly, the choices being $1,X,\dots,X^{m-1}$ where $m=\min(n_1,\dots,n_k)$. If you had chosen a higher power of $X$ than that, then the resulting product would have too large of a power on one of the terms. Having picked your power of $X$, then you are forced to pick $x_i^{n_i-m+1}$ as the choice from the parenthesis $(x_i+x_i^2+x_i^3+\dots)$

Answer 2

If you look at each part as a set, then all the terms are just gonna be the product of each one element from each set! If you pick in his example, $x_2^2$ can either be $x_2^2$ from the second set or $x_2$ times this big $X$! Does it make any sense to you? Can you see that you cannot have more than 2 possibilities in this example? Because from the last set you can't go over the power of 2.