Wilf classification of triples of 4-letter patterns

MaRDI QIDQ4557838zbMATH OpenFDO

Authors David Callan, Toufik Mansour, Mark Shattuck

Publication date 26 November 2018

Full work available at URL https://arxiv.org/abs/1605.04969, https://dmtcs.episciences.org/3218/pdf

zbMATH Keywords

insertion encoding algorithmkernel methodpattern avoidanceWilf-equivalence

Mathematics Subject Classification ID

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

Abstract: We determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem reduces to showing that counting sequences that appear to be the same (agree in the first 16 terms) are in fact identical. The insertion encoding algorithm (INSENC) accounts for many of these and some others have been previously counted; in this paper, we find the generating function for each of the remaining 36 triples and it turns out to be algebraic in every case. Our methods are both combinatorial and analytic, including decompositions by left-right maxima and by initial letters. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence that succumbs to the kernel method. A particularly nice so-called cell decomposition is used in one case and a bijection is used for another.

Recommendations

• Wilf classification of triples of 4-letter patterns. II
• Wilf classification of subsets of four letter patterns
• Wilf classification of three and four letter signed patterns
• Wilf classification of subsets of six and seven four-letter patterns
• Wilf classification of subsets of eight and nine four-letter patterns
• A Wilf class composed of 19 symmetry classes of quadruples of 4-letter patterns
• Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns
• Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns
• Wilf classes of pairs of permutations of length 4
• Enumeration of permutations avoiding a triple of 4-letter patterns is almost all done

Cited in

(11)

• Permutation patterns and cell decompositions
• Wilf classification of subsets of four letter patterns
• Wilf classification of triples of 4-letter patterns. II
• 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 classification of subsets of six and seven four-letter patterns
• Combinatorial exploration: an algorithmic framework for enumeration
• Wilf-classification of mesh patterns of short length
• Wilf classification of three and four letter signed patterns

This page was built for publication: Wilf classification of triples of 4-letter patterns

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