A reciprocity approach to computing generating functions for permutations with no pattern matches

• Published in: Discrete Mathematics & Theoretical Computer Science
• Main Authors: Jones, Miles Eli, Remmel, Jeffrey
• Other Authors: Department of Mathematics Univ California San Diego (MATH - UC San Diego), University of California San Diego (UC San Diego), University of California (UC)-University of California (UC), Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2011
• Subjects: permutation; pattern match; descent; left to right minimum; symmetric polynomial; exponential generating function; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]; Gauche; Iceland
• Online Access: https://hal.inria.fr/hal-01215054; https://hal.inria.fr/hal-01215054/document; https://hal.inria.fr/hal-01215054/file/dmAO0149.pdf; https://doi.org/10.46298/dmtcs.2933

International audience In this paper, we develop a new method to compute generating functions of the form $NM_τ (t,x,y) = \sum\limits_{n ≥0} {\frac{t^n} {n!}}∑_{σ ∈\mathcal{lNM_{n}(τ )}} x^{LRMin(σ)} y^{1+des(σ )}$ where $τ$ is a permutation that starts with $1, \mathcal{NM_n}(τ )$ is the set of permutations in the symmetric group $S_n$ with no $τ$ -matches, and for any permutation $σ ∈S_n$, $LRMin(σ )$ is the number of left-to-right minima of $σ$ and $des(σ )$ is the number of descents of $σ$ . Our method does not compute $NM_τ (t,x,y)$ directly, but assumes that $NM_τ (t,x,y) = \frac{1}{/ (U_τ (t,y))^x}$ where $U_τ (t,y) = \sum_{n ≥0} U_τ ,n(y) \frac{t^n}{ n!}$ so that $U_τ (t,y) = \frac{1}{ NM_τ (t,1,y)}$. We then use the so-called homomorphism method and the combinatorial interpretation of $NM_τ (t,1,y)$ to develop recursions for the coefficient of $U_τ (t,y)$. Dans cet article, nous développons une nouvelle méthode pour calculer les fonctions génératrices de la forme $NM_τ (t,x,y) = \sum\limits_{n ≥0} {\frac{t^n} {n!}}∑_{σ ∈\mathcal{lNM_{n}(τ )}} x^{LRMin(σ)} y^{1+des(σ )}$ où τ est une permutation, $\mathcal{NM_n}(τ )$ est l'ensemble des permutations dans le groupe symétrique $S_n$ sans $τ$-matches, et pour toute permutation $σ ∈S_n$, $LRMin(σ )$ est le nombre de minima de gauche à droite de $σ$ et $des(σ )$ est le nombre de descentes de $σ$ . Notre méthode ne calcule pas $NM_τ (t,x,y)$ directement, mais suppose que $NM_τ (t,x,y) = \frac{1}{/ (U_τ (t,y))^x}$ où $U_τ (t,y) = \sum_{n ≥0} U_τ ,n(y) \frac{t^n}{ n!}$ de sorte que $U_τ (t,y) = \frac{1}{ NM_τ (t,1,y)}$. Nous utilisons ensuite la méthode dite "de l'homomorphisme'' et l'interprétation combinatoire de $NM_τ (t,1,y)$ pour développer des récursions sur le coefficient de $U_τ (t,y)$.