Counting monomials and $q$-Catalan polynomials

Question

Define $N(F)$ to be the number of monomials of a multi-variable polynomial $F$. For example $N(x^2y+3xy-y^5)=3$.

If $\mathbf{x}=(x_1,\dots,x_n)$ and $F_n(\mathbf{x})=\prod_{k=1}^n(x_1+\cdots+x_k)$ then it's easy to verify that $N(F_n)=C_n$ where $C_n=\frac1{n+1}\binom{2n}n$ are the Catalan numbers.

Consider now the polynomial $$G_n(\mathbf{x};q)=\prod_{k=1}^n(x_1+x_2q+x_3q^2+\cdots+x_kq^{k-1}).$$ Note. $G_n(\mathbf{x};1)=F_n(\mathbf{x})$.

On the other hand, among the many variants of the $q$-Catalan polynomials there is one called the Carlitz's $q$-Catalan numbers which can be presented by the recurrence $C_0(q):=1$ and $$C_{n+1}(q)=\sum_{k=0}^nC_k(q)C_{n-k}(q)\,q^{(k+1)(n-k)}.$$

I would like to ask:

QUESTION. If $g_{n,j}(\mathbf{x})$ denotes the coefficient of $q^j$ in $G_n(\mathbf{x};q)$ (after expansion), then $N(g_{n,j}(\mathbf{x}))$ equals the coefficient of $q^j$ in $C_n(q)$. Is this true?

Example. Take $n=3$. Then, $G_3(\mathbf{x};q)=x_1^3 + 2x_1^2x_2q + (x_1^2x_3+x_1x_2^2)q^2+x_1x_2x_3q^3$ and $C_3(q)=1+q+2q^2+q^3$. Therefore, $N(x_1^3)=1, N(2x_1^2x_2)=1, N(x_1^2x_3+x_1x_2^2)=2$ and $N(x_1x_2x_3)=1$.

Answer 1

Yes, bijectively.

Associate to a monomial $\prod_{i=1}^n x_i^{e_i}$ with $\sum_{i=1}^n e_i =n$ the path where we walk one step to the right, then up $e_n$ steps, then one step to the right, then up $e_{n-1}$ steps, then $\dots$, and finally walk up $e_1$ steps.

It's easy to see that this gives a bijection between monomials and paths with all steps up and right, and the path stays below the diagonal (a Dyck path) if and only if the monomial appears in $\prod_{k=1}^n (x_1 + \dots + x_k)$.

Furthermore since each of our $e_k$ steps up has $k-1$ squares to the right of it the number of squares below-right of our path is $\sum_{k=1}^n e_k (k-1)$, which is the power of $q$ next to which this monomial appears in $G_n ( \mathbf x; q)$.

So $g_{n,j}(\mathbf x)$ is a (weighted) sum of all the monomials corresponding to Dyck paths with $j$ squares below-right, and so the number of monomials appearing in $g_{n,j}(\mathbf x)$ is the number of Dyck paths with $j$ squares below-right.

Since the generating function of this count of Dyck paths is the $n$th Carlitz $q$-Catalan number (if I understand correctly, this is one of the combinatorial descriptions in the paper you link), this proves your claim.