HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

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

Abstract : 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)$.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [12 references]

https://hal.inria.fr/hal-01215054
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, October 13, 2015 - 3:05:46 PM
Last modification on : Wednesday, August 7, 2019 - 12:18:06 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:22:15 AM

File

dmAO0149.pdf
Publisher files allowed on an open archive

Citation

Miles Eli Jones, Jeffrey Remmel. A reciprocity approach to computing generating functions for permutations with no pattern matches. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.551-562, ⟨10.46298/dmtcs.2933⟩. ⟨hal-01215054⟩

Record views