A reciprocity approach to computing generating functions for permutations with no pattern matches
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 symmet...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2011-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/2933/pdf |
_version_ | 1797270325577121792 |
---|---|
author | Miles Eli Jones Jeffrey Remmel |
author_facet | Miles Eli Jones Jeffrey Remmel |
author_sort | Miles Eli Jones |
collection | DOAJ |
description | 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)$. |
first_indexed | 2024-04-25T02:02:29Z |
format | Article |
id | doaj.art-0a6ddf46764a4a8b8c347458c8f04eea |
institution | Directory Open Access Journal |
issn | 1365-8050 |
language | English |
last_indexed | 2024-04-25T02:02:29Z |
publishDate | 2011-01-01 |
publisher | Discrete Mathematics & Theoretical Computer Science |
record_format | Article |
series | Discrete Mathematics & Theoretical Computer Science |
spelling | doaj.art-0a6ddf46764a4a8b8c347458c8f04eea2024-03-07T14:49:33ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502011-01-01DMTCS Proceedings vol. AO,...Proceedings10.46298/dmtcs.29332933A reciprocity approach to computing generating functions for permutations with no pattern matchesMiles Eli Jones0Jeffrey Remmel1Department of Mathematics [Univ California San Diego]Department of Mathematics [Univ California San Diego]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)$.https://dmtcs.episciences.org/2933/pdfpattern matchdescentleft to right minimumsymmetric polynomialexponential generating functionpermutation[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
spellingShingle | Miles Eli Jones Jeffrey Remmel A reciprocity approach to computing generating functions for permutations with no pattern matches Discrete Mathematics & Theoretical Computer Science pattern match descent left to right minimum symmetric polynomial exponential generating function permutation [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
title | 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_short | 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 |
topic | pattern match descent left to right minimum symmetric polynomial exponential generating function permutation [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
url | https://dmtcs.episciences.org/2933/pdf |
work_keys_str_mv | AT mileselijones areciprocityapproachtocomputinggeneratingfunctionsforpermutationswithnopatternmatches AT jeffreyremmel areciprocityapproachtocomputinggeneratingfunctionsforpermutationswithnopatternmatches AT mileselijones reciprocityapproachtocomputinggeneratingfunctionsforpermutationswithnopatternmatches AT jeffreyremmel reciprocityapproachtocomputinggeneratingfunctionsforpermutationswithnopatternmatches |