One has the nice identities $${xy\choose 1}={x\choose 1}{y\choose 1},$$ $${xy+1\choose 2}={x+1\choose 2}{y+1\choose 2}+{x\choose 2}{y\choose 2}$$ and $${xy+2\choose 3}={x+2\choose 3}{y+2\choose 3}+4{x+1\choose 3}{y+1\choose 3}+{x\choose 3}{y\choose 3}.$$

(The proof is essentially trivial by interpreting ${z\choose k}$ as a polynomial of degree $k$.)

This sequence of identities stops: There seems to be no nice expression of ${xy+k-1\choose k}$ as a linear combination of ${x+k-i\choose k}{y+k-i\choose k},i=1,\ldots,k$ for $k\geq 4$.

Is there a good reason for this breakdown? (Probably a better question is: Is there a reason for these identities to hold for $k=2$ and, especially, for $k=3$?)

  • 1
    $\begingroup$ Is it a coincidence that 1; 1,1; 1,4,1 is the Eulerian numbers sequence? $\endgroup$ Aug 3, 2022 at 14:59
  • 1
    $\begingroup$ No idea if this is coincidental. Coefficients on the right hand side should however add up to $k!$ (by comparing coefficients of $(xy)^k$ on both sides). $\endgroup$ Aug 3, 2022 at 15:30

1 Answer 1


$\def\des{\operatorname{des}}$Let $\des(\pi)$ be the number of descents of the permutation $\pi$. Then for any permutation $\pi$ in $S_k$, we have \begin{equation*}\binom{xy+k-\des(\pi)-1}{k} =\sum_{\sigma\tau=\pi}\binom{x+k-\des(\tau)-1}{k} \binom{y+k-\des(\sigma)-1}{k}.\tag{$*$}\label{star} \end{equation*}

If $\pi$ is the identity then $\des(\pi)=0$, so the left side of \eqref{star} is $\binom{xy+k-1}{k}$ and on the right, $\tau=\sigma^{-1}$. The OP's identities correspond to the fact that if $k\le 3$ then the number of descents of $\pi$ is the same as the number of descents of $\pi^{-1}$, but this is not true for $k>3$. This also explains the occurrence of the Eulerian numbers as coefficients for $k\le3$.

As far as I know, the earliest proof of \eqref{star} is in Bogdan Mielnik and Jerzy Plebański, Combinatorial approach to Baker–Campbell–Hausdorff exponents, Annales de l’I. H. P., section A, tome 12, no 3 (1970), pp. 215–254 (see equation (11.10)); further references can be found in Jason Fulman and T. Kyle Petersen, Card shuffling and P-partitions, arXiv:2004.01659 [math.CO].

  • 2
    $\begingroup$ Very nice explanation! Thanks. $\endgroup$ Aug 3, 2022 at 16:36
  • 2
    $\begingroup$ MathJax notes: as with TeX, you can use \label+\eqref with \tag and get nice hyperlinks to boot. Unlike TeX, MathJax is not aggressive about discarding whitespace, so a preamble line $\def\des{…}$ followed by a newline will force a space in the text. Unfortunately, as ugly as it is in the source, the only way to get rid of the space is to put the closing $ directly next to the first line of the post, with no intervening whitespace. I have edited accordingly. $\endgroup$
    – LSpice
    Aug 3, 2022 at 18:56
  • $\begingroup$ is it implied that $\pi = \tau \sigma$? $\endgroup$ Aug 4, 2022 at 12:03
  • 1
    $\begingroup$ @NooneAtAll If $\sigma\tau$ is the identity then so is $\tau\sigma$ but in general $\tau\sigma\ne\sigma\tau$. $\endgroup$
    – Ira Gessel
    Aug 4, 2022 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.