Skip to main content
4 of 4
Theproof of $(*)$ is simplified.
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

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.

Ilya Bogdanov
  • 23.7k
  • 54
  • 92