Skip to main content
1 of 4
Will Sawin
  • 148.5k
  • 9
  • 324
  • 563

The generating function is $$ \sum_{s_1,s_2, s_3} {s_1 + s_2-1 \choose s_2} {s_2+ s_3-1 \choose s_3} x^{s_1+s_2+s_3}.$$

Examining just the sum over the $s_3$ variable, we get $1/(1-x)^{s_2}.$ then the sum over just the $s_2$ variable is $1/(1-x/(1-x))^{s_1}=((1-x)/(1-2x))^{s_1}$ and so the whole generating function is $(1-2x)/(1-3x+ x^2)$. Thus explains two of the eugenvalues Carlo found. The remaining one comes from the fact that for this to work we need ${-1 \choose 0}=1$. We have to subtract off the terms where $s_1,s_2,$ or $s_3$ is zero. If any is zero then all later ones are zero so these are all contained I $s_3=0$ which gives $(1-x)/(1-2x)$. Subtracting this off we should get the right formula.

Will Sawin
  • 148.5k
  • 9
  • 324
  • 563