The study of patterns in permutations in a very active area of current research. Klazar defined and studied an analogous notion of pattern for set partitions. We continue this work, finding exact formulas for the number of set partitions which avoid certain specific patterns. In particular, we enumerate and characterize those partitions avoiding any partition of a 3-element set. This allows us to conclude that the corresponding sequences are P-recursive. Finally, we define a second notion of pattern in a set partition, based on its restricted growth function. Related results are obtained for this new definition.
Let P be a partially ordered set and consider the free monoid P* of all words over P. If w and w' are in P* then w' is a factor of w if there are words u and v with w = uw'v. Define generalized factor order on P* by letting u ≤ w if there is a factor w' of w having the same length as u such that u ≤ w', where the comparison of u and w' is done componentwise using the partial order in P. One obtains ordinary factor order by insisting that u=w' or, equivalently, by taking P to be an antichain.
Given u in P*, we prove that the language {w : w ≥ u} is accepted by a finite state automaton. If P is finite then it follows that the generating function F(u) = ∑w ≥ u w is rational. This is an analogue of a theorem of Björner and Sagan for generalized subword order.
We consider the case when P is the positive integers with the usual total order, so that P* is the set of compositions. In this case one obtains a weight generating function F(u;t,x) by substituting t xn each time the positive integer n appears in F(u). We show that this generating function is also rational by using the transfer-matrix method. Words u and v are said to be Wilf equivalent if F(u;t,x) = F(v;t,x) and we prove various Wilf equivalences combinatorially.
Bj\"orner found a recursive formula for the M\"obius function of ordinary factor order on P*. It follows that one always has μ(u,w) = 0, 1, -1. Using the Pumping Lemma we show that the generating function M(u) = ∑w ≥ u |μ(u,w)| w can be irrational.
It is shown that a refined version of a q-analogue of the Eulerian numbers together with the action, by conjugation, of the subgroup of the symmetric group Sn generated by the n-cycle (1,2,...,n) on the set of permutations of fixed cycle type and fixed number of excedances provides an instance of the cyclic sieving phenonmenon of Reiner, Stanton and White. The main tool is a class of symmetric functions recently introduced in work of two of the authors.
Let s and t be variables. Define polynomials {n} in s,t by {0}=0, {1}=1, and {n}=s{n-1}+t{n-2} for n≥2. If s,t are integers then the corresponding sequence of integers is called a Lucas sequence. Define a an analogue of the binomial coefficients by
where {n}!={1}{2}...{n}. It is easy to see that C{n,k} is a polynomial in s and t. The purpose of this note is to give two combinatorial interpretations for this polynomial in terms of statistics on integer partitions inside a k by n-k rectangle. When s=t=1 we obtain combinatorial interpretations of the fibonomial coefficients which are simpler than any that have previously appeared in the literature.