<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

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

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns"}

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...

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

Publié en ligne: 06 août 2018

Pages: 32 - 61

Reçu: 03 mai 2017

DOI: https://doi.org/10.1515/puma-2015-0026

Mots clés
pattern avoidance, generating function, generating tree, kernel method

© 2018 David Callan et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

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

Publié en ligne: 06 août 2018

Pages: 32 - 61

Reçu: 03 mai 2017

DOI: https://doi.org/10.1515/puma-2015-0026

Mots cléspattern avoidance, generating function, generating tree, kernel method

© 2018 David Callan et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
pattern avoidance, generating function, generating tree, kernel method