## Patterns and Statistics on Set Partitions and Restricted Growth Functions

##### Abstract

We consider partitions π of the set [n] = {1; 2,….., n}and denote the set of these parti- tions by _n. We use the notation _ = B1=B2/ : : : =Bk ` [n] to indicate that [n] = ωiBi and call the Bi blocks. If S _ [n] and _ ` [n], then the partition _0 of S obtained by intersecting the blocks of _ with S is called a subpartition of _. We standardize _0 to a set partition _ ` [k], k = jSj, by replacing the smallest element of _0 with 1, the next smallest with 2, and so forth. In this case we say that _ contains _. We say that _ avoids _ if _ does not contain _ and let _n(_) = f_ 2 _n : _ avoids _g. To obtain the standard form of _ = B1=B2= : : : =Bk we list the blocks in the order so that minB1 < minB2 < _ _ _ < minBk. Given _ in standard form, the restricted growth function (RGF) of _ is the word w = w(_) = w1w2 : : :wn where wi = j if i 2 Bj . Wachs and White introduced four fundamental statistics on set partitions via their RGFs. For example, one such statistic is lb(w) = P i lbi(w) where lbi(w) is the number of integers to the left of wi which are also bigger than wi. We let lb(_) = lb(w(_)). Letting q be a variable, we study the generating functions defined by LBn(_) = P _2_n(_) qlb(_) for all _ ` [3] as well as the analogous polynomials for the other statistics. In particular, we determine their coefficients, degrees, and other properties. Similar analysis can be done strictly using restricted growth functions. Specifically, this paper highlights a bijection with Ferrer's diagrams using pattern avoidance in restricted growth functions.