DMTCS Proceedings, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)

Font Size:  Small  Medium  Large

Consecutive patterns in permutations: clusters and generating functions

Sergi Elizalde, Marc Noy

Abstract


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.
Résumé. On utilise la méthode des clusters pour énumérer permutations qui évitent motifs consécutifs. On redémontre et on généralise d'une manière unifiée plusieurs résultats et on obtient de nouveaux résultats pour certains motifs de longueur 4 et 5, ainsi que pour certaines familles infinies de motifs. L'outil principal c'est la méthode des clusters de Goulden et Jackson. On démontre aussi que, pour une grande classe de motifs, l'inverse de la série génératrice exponentielle qui compte occurrences est une fonction entière, mais on conjecture qu'elle n'est pas D-finie en général.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional