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 functions

Authors: Sergi Elizalde ORCID-iD; Marc Noy

    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]

    Share

    Consultation statistics

    This page has been seen 162 times.
    This article's PDF has been downloaded 204 times.