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 OPn,k be set of ordered partitions of [n] with k blocks and OPn,k(σ) be set of ordered partitions in OPn,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 |OPn,k(σ)|=|OPn,k(123)| for any permutation σ of length 3. Moreover, they raised a question concerning the enumeration of OPn,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 |OPn,k(123)| and the number en,d of 123-avoiding permutations of [n] with d descents. Using the bivariate generating function of en,d given by Barnabei, Bonetti and Silimbani, we obtain the bivariate generating function of |OPn,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   

Return