Sergi Elizalde ; Marc Noy - 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) - https://doi.org/10.46298/dmtcs.3036
Consecutive patterns in permutations: clusters and generating functionsArticle

Authors: Sergi Elizalde ORCID1; Marc Noy 2

  • 1 Department of Mathematics [Dartmouth]
  • 2 Departament de Matemàtica Aplicada II

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
Imported on: January 31, 2017
Keywords: Pattern avoidance, Consecutive patterns, Cluster method.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 244 times.
This article's PDF has been downloaded 294 times.