# 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|}*\chi*_{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 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: