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.
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