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 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 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 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 at 18:56
  • $\begingroup$ is it implied that $\pi = \tau \sigma$? $\endgroup$ Aug 4 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 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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