Cells of fixed height in Catalan words and restricted growth functions

A word w = w 1 w 2 ⋯ w n of length n over the set of positive integers is called a Catalan word whenever w 1 = 1 and 1 ≤ w k ≤ w k − 1 + 1 for k = 2 , 3 , … , n . A restricted growth function is defined as a word w = w 1 w 2 ⋯ w n of length n over the set of positive integers where w 1 = 1 and for k ≥ 2 we have 1 ≤ w k ≤ max ⁡ { w 1 , w 2 , ⋯ , w k − 1 } + 1 . We also define cells and heights of cells and we represent such words as bargraphs (otherwise known as polyominoes) where the i th column contains w i cells for 1 ≤ i ≤ n and where all columns have their bottom cell on the x -axis. In the case of Catalan words, we prove a relationship between the number of cells at different heights and first terms of the expanded polynomial ( 1 + x ) 2 n . In the case of restricted growth functions we find polynomials F n ( x ) where the coefficient of x j counts the number of cells of height j across all rgfs with n parts. In this case we also find bivariate generating functions for rgfs with k blocks, where the generating functions tracks the number of cells at a given height as well as the number of parts.