کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653621 | 1632783 | 2014 | 9 صفحه PDF | دانلود رایگان |
An ordered partition of [n]={1,2,…,n}[n]={1,2,…,n} is a partition whose blocks are endowed with a linear order. Let OPn,kOPn,k be the set of ordered partitions of [n][n] with kk blocks and OPn,k(σ)OPn,k(σ) be the set of ordered partitions in OPn,kOPn,k that avoid a pattern σσ. For any permutation pattern σσ of length three, Godbole, Goyt, Herdan and Pudwell obtained formulas for the number of ordered partitions of [n][n] with 3 blocks avoiding σσ as well as the number of ordered partitions of [n][n] with n−1n−1 blocks avoiding σσ. They also showed that |OPn,k(σ)|=|OPn,k(123)||OPn,k(σ)|=|OPn,k(123)| for any permutation σσ of length 3. Moreover, they raised a question concerning the enumeration of OPn,k(123)OPn,k(123), and conjectured that the number of ordered partitions of [2n][2n] with nn blocks of size 2 avoiding σσ satisfies a second order linear recurrence relation. In answer to the question of Godbole, et al., we establish a connection between |OPn,k(123)||OPn,k(123)| and the number en,den,d of 123-avoiding permutations of [n][n] with dd descents. Using the bivariate generating function of en,den,d given by Barnabei, Bonetti and Silimbani, we obtain the bivariate generating function of |OPn,k(123)||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][2n] with nn blocks of size 2.
Journal: European Journal of Combinatorics - Volume 36, February 2014, Pages 416–424