Ordered Partitions Avoiding a Permutation of Length 3

Abstract

An ordered partition of $[n]=\{1,2,\dots ,n\}$ is a partition whose blocks are endowed with a linear order. Let ${\mathcal{O}\mathcal{P}}_{n,k}$ be set of ordered partitions of $[n]$ with $k$ blocks and ${\mathcal{O}\mathcal{P}}_{n,k}(\sigma )$ be set of ordered partitions in ${\mathcal{O}\mathcal{P}}_{n,k}$ that avoid a pattern $\sigma$. 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 $|{\mathcal{O}\mathcal{P}}_{n,k}(\sigma )|=|{\mathcal{O}\mathcal{P}}_{n,k}(123)|$ for any permutation $\sigma$ of length 3, and raised the question concerning the enumeration of ${\mathcal{O}\mathcal{P}}_{n,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 $|{\mathcal{O}\mathcal{P}}_{n,k}(123)|$ and we prove the conjecture on the recurrence relation.

12 pages