Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns

DOI10.1515/PUMA-2015-0026MaRDI QIDQ5218110zbMATH OpenOpenAlexWikidataFDO

Authors David Callan, Toufik Mansour

Publication date 26 February 2020

Published in Pure Mathematics and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

generating functiongenerating treekernel methodpattern avoidance

Mathematics Subject Classification ID

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

Abstract: Recently, it has been determined that there are 242 Wilf classes of triples of 4-letter permutation patterns by showing that there are 32 non-singleton Wilf classes. Moreover, the generating function for each triple lying in a non-singleton Wilf class has been explicitly determined. In this paper, toward the goal of enumerating avoiders for the singleton Wilf classes, we obtain the generating function for all but one of the triples containing 1324. (The exceptional triple is conjectured to be intractable.) Our methods are both combinatorial and analytic, including generating trees, recurrence relations, and decompositions by left-right maxima. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence amenable to the kernel method.

Recommendations

• Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns
• Enumeration and Wilf-classification of permutations avoiding four patterns of length 4
• Wilf classification of subsets of four letter patterns
• Enumeration and Wilf-classification of permutations avoiding five patterns of length 4
• Wilf classification of triples of 4-letter patterns. II
• Wilf classification of subsets of six and seven four-letter patterns
• Wilf classification of subsets of eight and nine four-letter patterns
• On permutations avoiding 1324, 2143, and another 4-letter pattern
• On permutations avoiding 1243, 2134, and another 4-letter pattern
• Enumeration of Wilf classes in S_n o C_r for two patterns of length 3

Cited in

(12)

• Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes
• Nine classes of permutations enumerated by binomial transform of Fine's sequence
• Egge triples and unbalanced Wilf equivalence
• Wilf classification of triples of 4-letter patterns
• Wilf classification of triples of 4-letter patterns. II
• Twelve subsets of permutations enumerated as maximally clustered permutations
• A Wilf class composed of 19 symmetry classes of quadruples of 4-letter patterns
• Enumeration and Wilf-classification of permutations avoiding four patterns of length 4
• Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns
• Enumeration of permutations avoiding a triple of 4-letter patterns is almost all done
• Wilf-collapse in permutation classes having two basis elements of size three
• Combinatorial exploration: an algorithmic framework for enumeration

This page was built for publication: Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns

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