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*](https://www.sciencedirect.com/science/article/pii/0097316585900895?ref=cra_js_challenge&fr=RR-1) 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$.



Counting monomials and $q$-Catalan polynomials
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.


