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