The generating function for total displacement

MaRDI QIDQ743648zbMATH OpenFDO

Authors Mathieu Guay-Paquet, Kyle Petersen

Publication date 30 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4674, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p37

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

generating functionMotzkin pathpermutation statistic

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: 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.

Recommendations

• On computing the total displacement number via weighted Motzkin paths
• Total relative displacement of permutations
• A study of total relative displacements of permutations in paths and cycles
• An interesting new Mahonian permutation statistic
• New permutation statistics: Variation and a variant

Cites work

• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• The depth of a permutation.

Cited in

(5)

• Moments of permutation statistics and central limit theorems
• On computing the total displacement number via weighted Motzkin paths
• Permutations in two dimensions that maximally separate neighbors
• Canonical reduced words and signed descent length enumeration in Coxeter groups
• Depth in classical Coxeter groups

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The generating function for total displacement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q743648)