A reciprocity approach to computing generating functions for permutations with no pattern matches
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 per...
Main Authors: | , |
---|---|
Other Authors: | , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-01215054 https://inria.hal.science/hal-01215054/document https://inria.hal.science/hal-01215054/file/dmAO0149.pdf https://doi.org/10.46298/dmtcs.2933 |
id |
ftccsdartic:oai:HAL:hal-01215054v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01215054v1 2024-02-11T10:05:17+01:00 A reciprocity approach to computing generating functions for permutations with no pattern matches Jones, Miles Eli Remmel, Jeffrey 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 Reykjavik, Iceland 2011 https://inria.hal.science/hal-01215054 https://inria.hal.science/hal-01215054/document https://inria.hal.science/hal-01215054/file/dmAO0149.pdf https://doi.org/10.46298/dmtcs.2933 en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2933 hal-01215054 https://inria.hal.science/hal-01215054 https://inria.hal.science/hal-01215054/document https://inria.hal.science/hal-01215054/file/dmAO0149.pdf doi:10.46298/dmtcs.2933 info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-01215054 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.551-562, ⟨10.46298/dmtcs.2933⟩ 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] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic https://doi.org/10.46298/dmtcs.2933 2024-01-14T01:38:24Z 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)$. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) Gauche ENVELOPE(-62.500,-62.500,-64.233,-64.233) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
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] |
spellingShingle |
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] Jones, Miles Eli Remmel, Jeffrey A reciprocity approach to computing generating functions for permutations with no pattern matches |
topic_facet |
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] |
description |
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)$. |
author2 |
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 |
author |
Jones, Miles Eli Remmel, Jeffrey |
author_facet |
Jones, Miles Eli Remmel, Jeffrey |
author_sort |
Jones, Miles Eli |
title |
A reciprocity approach to computing generating functions for permutations with no pattern matches |
title_short |
A reciprocity approach to computing generating functions for permutations with no pattern matches |
title_full |
A reciprocity approach to computing generating functions for permutations with no pattern matches |
title_fullStr |
A reciprocity approach to computing generating functions for permutations with no pattern matches |
title_full_unstemmed |
A reciprocity approach to computing generating functions for permutations with no pattern matches |
title_sort |
reciprocity approach to computing generating functions for permutations with no pattern matches |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://inria.hal.science/hal-01215054 https://inria.hal.science/hal-01215054/document https://inria.hal.science/hal-01215054/file/dmAO0149.pdf https://doi.org/10.46298/dmtcs.2933 |
op_coverage |
Reykjavik, Iceland |
long_lat |
ENVELOPE(-62.500,-62.500,-64.233,-64.233) |
geographic |
Gauche |
geographic_facet |
Gauche |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://inria.hal.science/hal-01215054 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.551-562, ⟨10.46298/dmtcs.2933⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.2933 hal-01215054 https://inria.hal.science/hal-01215054 https://inria.hal.science/hal-01215054/document https://inria.hal.science/hal-01215054/file/dmAO0149.pdf doi:10.46298/dmtcs.2933 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.46298/dmtcs.2933 |
_version_ |
1790602219162173440 |