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.
@article{10_37236_4329,
author = {Mathieu Guay-Paquet and Kyle Petersen},
title = {The generating function for total displacement},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/4329},
zbl = {1301.05010},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4329/}
}
TY - JOUR
AU - Mathieu Guay-Paquet
AU - Kyle Petersen
TI - The generating function for total displacement
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4329/
DO - 10.37236/4329
ID - 10_37236_4329
ER -
%0 Journal Article
%A Mathieu Guay-Paquet
%A Kyle Petersen
%T The generating function for total displacement
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4329/
%R 10.37236/4329
%F 10_37236_4329
Mathieu Guay-Paquet; Kyle Petersen. The generating function for total displacement. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/4329
