Elizalde, Sergi and Noy, Marc - Consecutive patterns in permutations: clusters and generating functions

dmtcs:3036 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Consecutive patterns in permutations: clusters and generating functions

Authors: Elizalde, Sergi and Noy, Marc

We use the cluster method in order 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 length 4 and 5, as well as some infinite families of patterns of a given shape. Our main tool is the cluster method of Goulden and Jackson. We also prove some that, for a large class of patterns, the inverse of the exponential generating function counting occurrences is an entire function, but we conjecture that it is not D-finite in general.


Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Submitted on: January 31, 2017
Keywords: Pattern avoidance, Consecutive patterns, Cluster method.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 73 times.
This article's PDF has been downloaded 116 times.