Cells of fixed height in Catalan words and restricted growth functions (Q6665421)

A word \(w = w_1w_2\ldots w_n\) of length \(n\) over the set of positive integers is called a Catalan word whenever \(w_1 = 1\) and \(1 \leq w_k \leq w_{k-1} + 1\) for \(k = 2, 3,\ldots , n\). A restricted growth function (rgf) is defined as a word \(w = w_1w_2 \ldots w_n\) of length \(n\) over the set of positive integers where \(w_1 = 1\) and for \(k \geq 2\) we have \(1 \leq w_k \leq \max\{w_1, w_2,\ldots, w_{k-1}\} + 1\). In this paper, such words are represented as bargraphs (otherwise known as polyominoes) where the \(i\)th column contains \(w_i\) cells for \(1 \leq i \leq n\) and where all columns have their bottom cell on the \(x\)-axis. In the case of Catalan words, the authors prove a relationship between the number of cells at different heights and the first terms of the expanded polynomial \((1+x)^{2n}\). In the case of restricted growth functions with \(n\) parts the polynomials \(F_n(x)\), where the coefficient of \(x^j\) counts the number of cells of height \(j\) across all restricted growth functions with \(n\) parts are deduced. In this case, also bivariate generating restricted growth functions for rgfs with \(k\) blocks were found, where the generating functions track the number of cells at a given height as well as the number of parts. The authors also establish an interesting connection between cells at height \(i\) in Catalan words with \(n\) letters and central binomial coefficients. An open question concludes the paper.