Permutation Statistics of Indexed Permutations

✍ Scribed by Einar Steingrı́msson

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 648 KB
• Volume: 15
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1994.1021

✦ Synopsis

The definitions of descent, excedance, major index, inversion index and Denert's statistic for the elements of the symmetric group (\mathscr{S}{d}) are generalized to indexed permutation, i.e. the elements of the group (S{d}^{n}:=\mathbf{Z}{n} \backslash \mathscr{S}{d}), where (\backslash) is the wreath product with respect to the usual action of (\mathscr{S}_{d}) by permutation of ({1,2, \ldots, d}).

It is shown, bijectively, that excedances and descents are equidistributed, and the corresponding descent polynomial, analogous to the Eulerian polynomial, is computed as the (f)-eulerian polynomial of a simple polynomial. The descent polynomial is shown to equal the (h)-polynomial (essentially the (h)-vector) of a certain triangulation of the unit (d)-cube. This is proved by a bijection which exploits the fact that the (h)-vector of the simplicial complex arising from the triangulation can be computed via a shelling of the complex. The famous formula (\sum_{d z 0} E_{d} x^{d} / d !=\sec x+\tan x), where (E_{d}) is the number of alternating permutations in (\mathscr{C}{d}), is generalized in two different ways, one relating to recent work of V. I. Arnold on Morse theory. The major index and inversion index are shown to be equidistributed over (S{d \text { t }}^{n}). Likewise, the pair of statistics ( (d), maj) is shown to be equidistributed with the pair ( (\varepsilon), den), where den is Denert's statistic and (\varepsilon) is an alternative definition of excedance. A result relating the number of permutations with (k) descents to the volume of a certain 'slice' of the unit (d)-cube is also generalized.