Return to Answer

Let me complete Sam Hopkins' answer.

The expression on the left is $$ \Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right)\\ =\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j(i_j+1)!\\ =(n-1)!\sum_{i_1+\dots+i_{n+1}=n-1}\prod_j (i_j+1) =(n-1)!\sum_{a_1+\dots+a_{n+1}=2n}\prod_j a_j. $$ Now the identity is a partial case of the following: $$ \sum_{a_1+\dots+a_k=\ell}\prod_j a_j={\ell+k-1\choose 2k-1}, \qquad(*) $$ as $$ n!\frac1{2n+1}{3n\choose n}=\frac{(3n)!}{(2n+1)!}=(n-1)!{3n\choose 2n+1}. $$

To prove the general identity $(*)$, denote the left-hand part by $f(k,\ell)$ and notice that $f(1,\ell)=\ell$ and $$ f(k,\ell)=\sum_i if(k-1,\ell-i). $$ Now it suffices to check that the right-hand part satisfies the same conditions, which is easy (the recurrence follows from $(1-x)^{-2k}=(1-x)^{-2}(1-x)^{2-2k}$).

A more direct proof of $(*)$: both parts equal to the number of ways of choosing $2k-1$ elements from the string of $\ell+k-1$ ones, and paint them alternatively in red and blue. The $k-1$ blue elements serve as separators dividing the other $k$ elements into the groups of $a_1,\dots,a_k$ elements.

Let me complete Sam Hopkins' answer.

The expression on the left is $$ \Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right)\\ =\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j(i_j+1)!\\ =(n-1)!\sum_{i_1+\dots+i_{n+1}=n-1}\prod_j (i_j+1) =(n-1)!\sum_{a_1+\dots+a_{n+1}=2n}\prod_j a_j. $$ Now the identity is a partial case of the following: $$ \sum_{a_1+\dots+a_k=\ell}\prod_j a_j={\ell+k-1\choose 2k-1}, \qquad(*) $$ as $$ n!\frac1{2n+1}{3n\choose n}=\frac{(3n)!}{(2n+1)!}=(n-1)!{3n\choose 2n+1}. $$

The general identity $(*)$ follows immediately from the generating functions identity $((1-x)^{-2})^k=(1-x)^{-2k}$.

A more direct proof of $(*)$: both parts equal to the number of ways of choosing $2k-1$ elements from the string of $\ell+k-1$ ones, and paint them alternatively in red and blue. The $k-1$ blue elements serve as separators dividing the other $k$ elements into the groups of $a_1,\dots,a_k$ elements.

Let me complete Sam Hopkins' answer.

The expression on the left is $$ \Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right)\\ =\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j(i_j+1)!\\ =(n-1)!\sum_{i_1+\dots+i_{n+1}=n-1}\prod_j (i_j+1) =(n-1)!\sum_{a_1+\dots+a_{n+1}=2n}\prod_j a_j. $$ Now the identity is a partial case of the following: $$ \sum_{a_1+\dots+a_k=\ell}\prod_j a_j={\ell+k-1\choose 2k-1}, \qquad(*) $$ as $$ n!\frac1{2n+1}{3n\choose n}=\frac{(3n)!}{(2n+1)!}=(n-1)!{3n\choose 2n+1}. $$

To prove the general identity $(*)$, denote the left-hand part by $f(k,\ell)$ and notice that $f(1,\ell)=\ell$ and $$ f(k,\ell)=\sum_i if(k-1,\ell-i). $$ Now it suffices to check that the right-hand part satisfies the same conditions, which is easy (the recurrence follows from $(1-x)^{1-2k}=(1-x)^{-2}(1-x)^{3-2k}$).

A more direct proof of $(*)$: both parts equal to the number of ways of choosing $2k-1$ elements from the string of $\ell+k-1$ ones, and paint them alternatively in red and blue. The $k-1$ blue elements serve as separators dividing the other $k$ elements into the groups of $a_1,\dots,a_k$ elements.

Let me complete Sam Hopkins' answer.

The expression on the left is $$ \Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right)\\ =\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j(i_j+1)!\\ =(n-1)!\sum_{i_1+\dots+i_{n+1}=n-1}\prod_j (i_j+1) =(n-1)!\sum_{a_1+\dots+a_{n+1}=2n}\prod_j a_j. $$ Now the identity is a partial case of the following: $$ \sum_{a_1+\dots+a_k=\ell}\prod_j a_j={\ell+k-1\choose 2k-1}, \qquad(*) $$ as $$ n!\frac1{2n+1}{3n\choose n}=\frac{(3n)!}{(2n+1)!}=(n-1)!{3n\choose 2n+1}. $$

To prove the general identity $(*)$, denote the left-hand part by $f(k,\ell)$ and notice that $f(1,\ell)=\ell$ and $$ f(k,\ell)=\sum_i if(k-1,\ell-i). $$ Now it suffices to check that the right-hand part satisfies the same conditions, which is easy (the recurrence follows from $(1-x)^{-2k}=(1-x)^{-2}(1-x)^{2-2k}$).

A more direct proof of $(*)$: both parts equal to the number of ways of choosing $2k-1$ elements from the string of $\ell+k-1$ ones, and paint them alternatively in red and blue. The $k-1$ blue elements serve as separators dividing the other $k$ elements into the groups of $a_1,\dots,a_k$ elements.

Let me complete Sam Hopkins' answer.

The expression on the left is $$ \Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right) =\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j(i_j+1)! =(n-1)!\sum_{i_1+\dots+i_{n+1}=n-1}\prod_j (i_j+1) =(n-1)!\sum_{a_1+\dots+a_{n+1}=2n}\prod_j a_j. $$ Now the identity is a partial case of the following: $$ \sum_{a_1+\dots+a_k=\ell}\prod_j a_j={\ell+k-1\choose 2k-1}, $$ as $$ n!\frac1{2n+1}{3n\choose n}=\frac{(3n)!}{(2n+1)!}=(n-1)!{3n\choose 2n+1}. $$

To prove the general identity, denote the left-hand part by $f(k,\ell)$ and notice that $f(1,\ell)=\ell$ and $$ f(k,\ell)=\sum_i if(k-1,\ell-i). $$ Now it suffices to check that the right-hand part satisfies the same conditions, which is easy (the recurrence follows from $(1-x)^{1-2k}=(1-x)^{-2}(1-x)^{3-2k}$).

Let me complete Sam Hopkins' answer.

The expression on the left is $$ \Psi\left(\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j x_j^{i_j+1}\right)\\ =\sum_{i_1+\dots+i_{n+1}=n-1}{n-1\choose i_1,\dots,i_{n+1}}\prod_j(i_j+1)!\\ =(n-1)!\sum_{i_1+\dots+i_{n+1}=n-1}\prod_j (i_j+1) =(n-1)!\sum_{a_1+\dots+a_{n+1}=2n}\prod_j a_j. $$ Now the identity is a partial case of the following: $$ \sum_{a_1+\dots+a_k=\ell}\prod_j a_j={\ell+k-1\choose 2k-1}, \qquad(*) $$ as $$ n!\frac1{2n+1}{3n\choose n}=\frac{(3n)!}{(2n+1)!}=(n-1)!{3n\choose 2n+1}. $$

To prove the general identity $(*)$, denote the left-hand part by $f(k,\ell)$ and notice that $f(1,\ell)=\ell$ and $$ f(k,\ell)=\sum_i if(k-1,\ell-i). $$ Now it suffices to check that the right-hand part satisfies the same conditions, which is easy (the recurrence follows from $(1-x)^{1-2k}=(1-x)^{-2}(1-x)^{3-2k}$).

A more direct proof of $(*)$: both parts equal to the number of ways of choosing $2k-1$ elements from the string of $\ell+k-1$ ones, and paint them alternatively in red and blue. The $k-1$ blue elements serve as separators dividing the other $k$ elements into the groups of $a_1,\dots,a_k$ elements.