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 |