Problèmes Combinatoires De Commutation Et Réarrangements

Commutation and Rearrangements An electronic reedition of the monograph Probl`emes combinatoires de commutation et r´earrangements by P. Cartier, D. Foata with three new appendices by D. Foata, B. Lass and Ch. Krattenthaler 2006 Foreword The monograph “Probl`emes combinatoires de commutation et r´earrangements” was originally published as no. 85 in the Springer-Verlag Lecture Notes in Mathematics Series, back in 1969. The algebraic and combinatorial techniques developed there have since been used in various branches of mathematics and also computer science. The notion of partially commutative monoid, that was first introduced for extending the MacMahon Master Theorem to the noncommutative case, has been used in other contexts. In particular, it has provided an appropriate mathematical model for the study of computer parallelism. The fundamental result deals with an inversion formula, that has been expressed in different algebraic structures, originally the algebra of a partially commutative monoid. It was then appropriate, with this electronic reedition of the monograph, to have three appendices which could illustrate how that fundamental inversion formula was implemented in other environments, explicitly and also implicitly. In the first appendix (“Inversions de M¨ obius”) it is shown how to go from the M¨ obius inversion formula for a partially commutative monoid to the M¨ obius formula for a locally finite partially ordered set, and conversely. In the second appendix Bodo Lass shows that by means of a simple specialization of the variables the fundamental inversion formula provides a noncommutative version of the celebrated chromatic polynomial identity for graphs : (−1)|V | χG (−1) = a(G). The third appendix, written by Christian Krattenthaler, presents Viennot’s theory of heaps of pieces, a theory that has been very fruitful in the combinatorial theory of orthogonal