Counting $r\times s$ rectangles in (Catalan) words

Abstract

Generalizing previous results, we introduce and study a new statistic on words, that we call rectangle capacity. For two fixed positive integers $r$ and $s$, this statistic counts the number of occurrences of a rectangle of size $r\times s$ in the bargraph representation of a word. We find the bivariate generating function for the distribution on words of the number of $r\times s$ rectangles and the generating function for their total number over all words. We also obtain the analog results for Catalan words.

20 pages