Given a multi-variable polynomial $F$, denote the number of monomials by $N(F)$. Take for instance, \begin{align*}N(x(x+y)+(x+y)^2-(x-y)^2)=N(x^2+5xy)&=2 \qquad \text{and} \\ N((x+z)(x+y)^2)=N(x^3 + 2x^2y + x^2z + xy^2 + 2xyz + y^2z)&=6.\end{align*} Denote the symmetric group on $n$ letters $\{1,2,\dots,n\}$ by $\mathfrak{S}_n$. Define the action of $\mathfrak{S}_n$ on a function $F(x_1,\dots,x_n)$ in a natural way: given $w\in\mathfrak{S}_n$, then $w\cdot F(x_1,\dots,x_n)=F(x_{w(1)},\dots,x_{w(n)})$. Introduce the (multi-variable) rational functions $$G(\mathbf{x},\mathbf{z})=\prod_{k=1}^n\frac{x_1z_1+x_2z_2+\cdots+x_kz_k}{x_k-x_{k+1}}.$$

Assuming that the symmetric groups act only on the $x$-variables, let's compute the polynomial $$G_{\mathfrak{S}_{n+1}}=\sum_{w\in\frak{S}_{n+1}}w\cdot G.$$ I would like to ask:

QUESTION. Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Is there a combinatorial proof that $N(G_{\mathfrak{S}_{n+1}})=C_n$?

  • $\begingroup$ Are you sure the $G(\mathbf{x},\mathbf{z})$ are polynomials (as opposed to rational functionals)? I guess the point is that after symmetrization the $G_{\mathfrak{S}_{n+1}}$ become polynomials... $\endgroup$ Apr 22 at 21:07
  • $\begingroup$ Edited. Thank you. $\endgroup$ Apr 22 at 22:07
  • 1
    $\begingroup$ I checked findstat for the distribution of coefficients, to no avail :-( $\endgroup$ Apr 23 at 9:18

1 Answer 1


Any monomial $P:=\prod x_i^{c_i}$ of degree $\sum c_i=n$ maps to a non-zero constant after symmetrization $$ P\to \Phi(P):=G_{\mathfrak{S}_{n+1}}\frac{P}{(x_1-x_2)(x_2-x_3)\ldots (x_n-x_{n+1})}. $$ Indeed, $\Phi(P)$ is a constant by a degree consideration, to prove that this constant is non-zero you may use, for example, Theorem 2 here.

Thus any monomial $\prod (x_iz_i)^{c_i}$ maps to a non-zero constant times $\prod z_i^{c_i}$.

Thus, you simply count the number of monomials which may arise, when you multiply the linear forms $\prod_{k=1}^n(x_1z_1+x_2z_2+\cdots+x_kz_k)$. The only condition is that $c_1+\ldots+c_i\geqslant i$ for all $i$. Such sequences are indeed enumerated by Catalan numbers, a bijection with lattice paths below diagonal is straightforward.

  • $\begingroup$ This is now findstat.org/StatisticsDatabase/St001786 $\endgroup$ Apr 25 at 8:04
  • 1
    $\begingroup$ Does your Theorem yield a direct interpretation of the coefficients? Is it true that the coefficient equals 1 if and only if the path is a bounce path? $\endgroup$ Apr 25 at 10:36
  • $\begingroup$ @MartinRubey the coefficient equals (upto sign) to the number of enumerations of $n+1$ vertices of the path which satisfy $n$ inequalities which in turn correspond to the $n$ edges. The inequality $\pi(x)<\pi(y)$ for an edge $xy$ corresponds to our monomial $C$ being $y$-biased in the following sense: remove the edge $xy$, let $k$ denote the number of vertices in the piece containing $y$; then the total degree of $C$ in these $k$ variables is at least $k$. So, the number of monomials with coefficient $\pm 1$ (happens when all inequalities have the same direction) is twice Catalan number. $\endgroup$ Apr 25 at 12:30
  • $\begingroup$ That's strange, possibly I have a bug in my code, but my coefficients are all positive. $\endgroup$ Apr 25 at 14:33
  • $\begingroup$ @MartinRubey this is quite possible, I simply did not care about the sign writing my comment $\endgroup$ Apr 25 at 15:48

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.