Ordered Partitions Avoiding a Permutation Pattern of Length 3
William Y.C. Chen, Alvin Y.L. Dai and Robin D.P. Zhou
Abstract: An ordered partition of [n]={1, 2,..., n} is a partition whose blocks are endowed with a linear order. Let OP_{n,k} be set of ordered partitions of [n] with k blocks and OP_{n,k}(σ) be set of ordered partitions in OP_{n,k} that avoid a pattern σ. For any permutation pattern σ of length 3, Godbole, Goyt, Herdan and Pudwell obtained formulas for the number of ordered partitions of [n] with 3 blocks avoiding σ as well as the number of ordered partitions of [n] with n-1 blocks avoiding σ. They showed that |OP_{n,k}(σ)|=|OP_{n,k}(123)| for any permutation σ of length 3. Moreover, they raised a question concerning the enumeration of OP_{n,k}(123), and conjectured that the number of ordered partitions of [2n] with blocks of size 2 avoiding σ satisfied a second order linear recurrence relation. In answer to the question of Godbole, et al., we establish a connection between |OP_{n,k}(123)| and the number e_{n,d} of 123-avoiding permutations of [n] with d descents. Using the bivariate generating function of e_{n,d} given by Barnabei, Bonetti and Silimbani, we obtain the bivariate generating function of |OP_{n,k}(123)|. Meanwhile, we confirm the conjecture of Godbole, et al. by deriving the generating function for the number of 123-avoiding ordered partitions of [2n] with n blocks of size 2. AMS Classification: 05A15, 05A18 Keywords: pattern avoidance, ordered partition, descent Download: pdf |