Restricted growth function patterns and statistics

Abstract A restricted growth function (RGF) of length n is a sequence w = w 1 w 2 … w n of positive integers such that w 1 = 1 and w i ≤ 1 + max ⁡ { w 1 , … , w i − 1 } for i ≥ 2 . RGFs are of interest because they are in natural bijection with set partitions of { 1 , 2 , … , n } . An RGF w avoids another RGF v if there is no subword of w which standardizes to v . We study the generating functions ∑ w ∈ R n ( v ) q st ( w ) where R n ( v ) is the set of RGFs of length n which avoid v and st ( w ) is any of the four fundamental statistics on RGFs defined by Wachs and White. These generating functions exhibit interesting connections with multiset permutations, integer partitions, and two-colored Motzkin paths, as well as noncrossing and nonnesting set partitions.