# Counting monomials and the Catalan numbers

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$$?

• 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... Apr 22 at 21:07
• Edited. Thank you. Apr 22 at 22:07
• I checked findstat for the distribution of coefficients, to no avail :-( Apr 23 at 9:18

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.
• @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. Apr 25 at 12:30