Avoiding a pair of patterns in multisets and compositions

DOI10.1016/J.AAM.2021.102286MaRDI QIDQ2665759zbMATH OpenOpenAlexWikidataFDO

Authors Vít Jelínek, Toufik Mansour, José L. Ramírez, Mark Shattuck

Publication date 19 November 2021

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

compositionmultisetpattern avoidanceWilf-equivalence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: In this paper, we study the Wilf-type equivalence relations among multiset permutations. We identify all multiset equivalences among pairs of patterns consisting of a pattern of length three and another pattern of length at most four. To establish our results, we make use of a variety of techniques, including Ferrers-equivalence arguments, sorting by minimal/maximal letters, analysis of active sites and direct bijections. In several cases, our arguments may be extended to prove multiset equivalences for infinite families of pattern pairs. Our results apply equally well to the Wilf-type classification of compositions, and as a consequence, we obtain a complete description of the Wilf-equivalence classes for pairs of patterns of type (3,3) and (3,4) on compositions, with the possible exception of two classes of type (3,4).

Recommendations

• A new class of multiset Wilf equivalent pairs
• Avoiding patterns of length three in compositions and multiset permutations
• Some results on the avoidance of vincular patterns by multisets
• Pattern avoidance in compositions and multiset permutations
• Pattern avoidance and dominating compositions

Cites work

• A new class of Wilf-equivalent permutations
• Generating trees and the Catalan and Schröder numbers
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• scientific article; zbMATH DE number 5716637 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• On (shape-)Wilf-equivalence for words
• On pattern-avoiding partitions
• Pattern avoidance in compositions and multiset permutations
• Restricted permutations
• Wilf-equivalence for singleton classes
• Wilf-equivalence on \(k\)-ary words, compositions, and parking functions

Cited in

(8)

• Wilf-equivalence on \(k\)-ary words, compositions, and parking functions
• Large sets avoiding patterns
• Multiple pattern avoidance with respect to fixed points and excedances
• A new class of multiset Wilf equivalent pairs
• Avoiding patterns of length three in compositions and multiset permutations
• On restricted permutations on regular multisets
• Some results on the avoidance of vincular patterns by multisets
• Pattern avoidance and dominating compositions

This page was built for publication: Avoiding a pair of patterns in multisets and compositions

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