Commutation and Rearrangements

An electronic reedition of the monograph

Problèmes combinatoires de commutation et réarrangements

by Pierre Cartier and Dominique Foata

(originally published in Lecture Notes in Mathematics, 85, Berlin, Springer-Verlag, 1969)

with three new appendices by D. Foata, B. Lass and Ch. Krattenthaler

Foreword. The monograph "Problèmes combinatoires de commutation et réarrangements" 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öbius") it is shown how to go from the Möbius inversion formula for a partially commutative monoid to the Möbius 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|\chiG(-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 polynomials and in the calculation of multivariable generating functions for polyominoes. The equivalence of the theory of heaps and the theory of partially commutative monoids is explicitly established.

Dominique Foata, July 2006

foata a t math dot u - strasbg dot fr
The following versions are available: