Furthermore, MacMahon's result on the above two statistics, say, E ("exceedence") and D ("descent") vectors can be established by constructing an explicit bijection F of each rearrangement class C of words onto itself having the property that E(w)=F((D(w)) holds for each word from C. The construction of such a bijection is based upon an algebra that extends the classical cycle product decomposition of a permutation (without letter repetitions) to any word (with possible repetitions). The duality between exceedence and descent is further used in a probability context to establish an identity à la Spitzer between two sequences of characteristic functions. Finally, several classical combinatorial identities are reproved in the light of this non commutative environment of the Master Theorem.
The study of permutations of a multiset, involving a discussion on the intercalation product, is clearly developed in Knuth, D. E. (1973). Sorting and Searching. No. 3 in The Art of Computer Programming. Addison-Wesley, Reading, p. 24-31.
foata@unistra.fr