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 matchesArticle
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)$.
Volume: DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Section: Proceedings
Published on: January 1, 2011
Imported on: January 31, 2017
Keywords: 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]
Funding:
Source : OpenAIRE Graph
Combinatorial Structures for Permutation Enumeration and Macdonald Polynomials; Funder: National Science Foundation; Code: 0654060
Bibliographic References
3 Documents citing this article
Anthony Mendes;Jeffrey Remmel, Developments in mathematics, The Reciprocity Method, pp. 263-278, 2015, 10.1007/978-3-319-23618-6_8.
Anthony Mendes;Jeffrey Remmel, Developments in mathematics, Counting with the Elementary and Homogeneous Symmetric Functions, pp. 79-120, 2015, 10.1007/978-3-319-23618-6_3.
Miles Eli Jones;Jeffrey B. Remmel, 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, https://doi.org/10.1016/j.disc.2013.08.010.