Ordered partitions avoiding a permutation pattern of length 3

DOI10.1016/J.EJC.2013.09.001MaRDI QIDQ2441648zbMATH OpenOpenAlexFDO

Authors William Y. C. Chen, Alvin Y. L. Dai, Robin D. P. Zhou

Publication date 25 March 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.3187

zbMATH Keywords

bivariate generating functionpattern avoiding set partitions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partitions of sets (05A18)

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

Recommendations

• Patterns in words of ordered set partitions
• Pattern avoidance in ordered set partitions and words
• Pattern avoidance in ordered set partitions
• Avoiding type \((1,2)\) or \((2,1)\) patterns in a partition of a set
• Avoidance of partitions of a three-element set

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Avoidance of partitions of a three-element set
• Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
• On \(abab\)-free and \(abba\)-free set partitions
• On pattern-avoiding partitions
• Pattern avoidance in ordered set partitions
• Pattern avoidance in ordered set partitions and words
• Pattern avoidance in set partitions.
• Priority queues and multisets
• The descent statistic on 123-avoiding permutations

Cited in

(5)

• Pattern avoidance in ordered set partitions
• The (ordinary) generating functions enumerating 123-avoiding words with r occurrences of each of 1, 2, , n are always algebraic
• Pattern avoidance in ordered set partitions and words
• Restricted generating trees for weak orderings
• scientific article; zbMATH DE number 7106992 (Why is no real title available?)

Describes a project that uses

Uses Software

• FindRec

This page was built for publication: Ordered partitions avoiding a permutation pattern of length 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441648)