Miles Eli Jones ; Jeffrey Remmel
-
A reciprocity approach to computing generating functions for permutations with no pattern matches
dmtcs:2933 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2011,
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
-
https://doi.org/10.46298/dmtcs.2933
A reciprocity approach to computing generating functions for permutations with no pattern matches
Authors: Miles Eli Jones 1; Jeffrey Remmel 1
NULL##NULL
Miles Eli Jones;Jeffrey Remmel
1 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)$.
A reciprocity method for computing generating functions over the set of permutations with no consecutive occurrence of \tau
3 Documents citing this article
Source : OpenCitations
Jones, Miles Eli; Remmel, Jeffrey B., 2013, A Reciprocity Method For Computing Generating Functions Over The Set Of Permutations With No Consecutive Occurrence Of A Permutation Pattern, Discrete Mathematics, 313, 23, pp. 2712-2729, 10.1016/j.disc.2013.08.010.
Mendes, Anthony; Remmel, Jeffrey, 2015, Counting With The Elementary And Homogeneous Symmetric Functions, Counting With Symmetric Functions, pp. 79-120, 10.1007/978-3-319-23618-6_3.
Mendes, Anthony; Remmel, Jeffrey, 2015, The Reciprocity Method, Counting With Symmetric Functions, pp. 263-278, 10.1007/978-3-319-23618-6_8.