×

Clusters, generating functions and asymptotics for consecutive patterns in permutations. (English) Zbl 1254.05007

Summary: We use the cluster method to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new ones, including some patterns of lengths 4 and 5, as well as some infinite families of patterns of a given shape. By enumerating linear extensions of certain posets, we find a differential equation satisfied by the inverse of the exponential generating function counting occurrences of the pattern. We prove that for a large class of patterns, this inverse is always an entire function.
We also complete the classification of consecutive patterns of length up to 6 into equivalence classes, proving a conjecture of Nakamura. Finally, we show that the monotone pattern asymptotically dominates (in the sense that it is easiest to avoid) all non-overlapping patterns of the same length, thus proving a conjecture of S. Elizalde and M. Noy [Adv. Appl. Math. 30, No.1–2, 110–125 (2003; Zbl 1016.05002)] for a positive fraction of all patterns.

MSC:

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
06A07 Combinatorics of partially ordered sets

Citations:

Zbl 1016.05002
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Baxter, B. Nakamura, D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive-Wilf classes, in: Ilias Kotsireas, Eugene Zima (Eds.), Proceedings of the W80 Conference, in press, arXiv:1101.3949; A. Baxter, B. Nakamura, D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive-Wilf classes, in: Ilias Kotsireas, Eugene Zima (Eds.), Proceedings of the W80 Conference, in press, arXiv:1101.3949 · Zbl 1273.05007
[2] Bóna, M., Non-overlapping permutation patterns, Pure Math. Appl., 22, 99-105 (2011) · Zbl 1265.05047
[3] Dotsenko, V.; Khoroshkin, A., Shuffle algebras, homology, and consecutive pattern avoidance, preprint · Zbl 1271.05101
[4] Duane, A.; Remmel, J., Minimal overlapping patterns in colored permutations, Electron. J. Combin., 18 (2011), #P25 · Zbl 1229.05017
[5] Ehrenborg, R.; Kitaev, S.; Perry, P., A spectral approach to consecutive pattern-avoiding permutations, J. Comb., 2, 305-353 (2011) · Zbl 1247.05013
[6] Elizalde, S., Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math., 36, 138-155 (2006) · Zbl 1089.05007
[7] Elizalde, S.; Noy, M., Consecutive patterns in permutations, Adv. in Appl. Math., 30, 110-123 (2003) · Zbl 1016.05002
[8] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 1165.05001
[9] Gessel, I., Symmetric functions and \(P\)-recursiveness, J. Combin. Theory Ser. A, 53, 257-285 (1990) · Zbl 0704.05001
[10] Goulden, I. P.; Jackson, D. M., An inversion theorem for cluster decompositions of sequences with distinguished subsequences, J. Lond. Math. Soc., 20, 567-576 (1979) · Zbl 0467.05008
[11] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York · Zbl 0519.05001
[12] Khoroshkin, A.; Shapiro, B., Using homological duality in consecutive pattern avoidance, Electron. J. Combin., 18 (2011), #P9 · Zbl 1217.05025
[13] Liese, J.; Remmel, J., Generating functions for permutations avoiding a consecutive pattern, Ann. Comb., 14, 123-141 (2010) · Zbl 1233.05016
[14] Mendes, A.; Remmel, J., Permutations and words counted by consecutive patterns, Adv. in Appl. Math., 37, 443-480 (2006) · Zbl 1110.05005
[15] Nakamura, B., Computational approaches to consecutive pattern avoidance in permutations, Pure Math. Appl., 22, 253-268 (2011) · Zbl 1265.05019
[16] Noonan, J.; Zeilberger, D., The enumeration of permutations with a prescribed number of “forbidden” patterns, Adv. in Appl. Math., 17, 381-407 (1996) · Zbl 0974.05001
[17] Noonan, J.; Zeilberger, D., The Goulden-Jackson cluster method: extensions, applications and implementations, J. Difference Equ. Appl., 5, 355-377 (1999) · Zbl 0935.05003
[18] Stanley, R., Enumerative Combinatorics, vol. II (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge
[19] Warlimont, R., Permutations avoiding consecutive patterns, Ann. Univ. Sci. Budapest. Sect. Comput., 22, 373-393 (2003) · Zbl 1108.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.