2013/04/11 by William Y. C. Chen, Chen, William Y. C., Alvin Y. L. Dai +3 · 1 citation
Engineering · Mathematics · #05A15 #05A18 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1304.3187
openalex publication_date 2013/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 σ. Recently, Godbole, Goyt, Herdan and Pudwell obtained formulas for the number of ordered partitions of [n] with 3 blocks and the number of ordered partitions of [n] with n-1 blocks avoiding a permutation pattern of length 3. They showed that |OPn,k(σ)|=|OPn,k(123)| for any permutation σ of length 3, and raised the question concerning the enumeration of OPn,k(123). They also conjectured that the number of ordered partitions of [2n] with blocks of size 2 avoiding a permutation pattern of length 3 satisfied a second order linear recurrence relation. In answer to the question of Godbole, et al., we obtain the generating function for |OPn,k(123)| and we prove the conjecture on the recurrence relation.