The Generating Function for Total Displacement
| Autor: | Kyle Petersen, Mathieu Guay-Paquet |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Distribution (number theory) Applied Mathematics Coxeter group Generating function Type (model theory) Theoretical Computer Science Combinatorics Permutation Computational Theory and Mathematics Simple (abstract algebra) Discrete Mathematics and Combinatorics Fraction (mathematics) Geometry and Topology Statistic Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 21 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/4329 |
| Popis: | In a 1977 paper, Diaconis and Graham studied what Knuth calls the total displacement of a permutation $w$, which is the sum of the distances $|w(i)-i|$. In recent work of the first author and Tenner, this statistic appears as twice the type $A_{n-1}$ version of a statistic for Coxeter groups called the depth of $w$. There are various enumerative results for this statistic in the work of Diaconis and Graham, codified as exercises in Knuth's textbook, and some other results in the work of Petersen and Tenner. However, no formula for the generating function of this statistic appears in the literature. Knuth comments that "the generating function for total displacement does not appear to have a simple form." In this paper, we translate the problem of computing the distribution of total displacement into a problem of counting weighted Motzkin paths. In this way, standard techniques allow us to express the generating function for total displacement as a continued fraction. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|