Abstract
We introduce the combinatorial notion of heaps of pieces, which gives a geometric interpretation of the Cartier-Foata's commutation monoid. This theory unifies and simplifies many other works in Combinatorics : bijective proofs in matrix algebra (MacMahon Master theorem, inversion matrix formula, Jacobi identity, Cayley-Hamilton theorem), combinatorial theory for general (formal) orthogonal polynomials, reciprocal of Rogers-Ramanujan identities, graph theory (matching and chromatic polynomials). Heaps may bring new light on classical subjects as poset theory. They are related to other fields as Theoretical Computer Science (parallelism) and Statistical Physics (directed animals problem, lattice gas model with hard-core interactions). Complete proofs and definitions are given in sections 2, 3,4,5. Other sections give a summary of possible applications of heaps.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
G. ANDREWS, The Theory of partitions, Encyclopedia of Maths. and its applications, G.C. Rota ed., vol 2, Addison Wesley, Reading, 1976
G. ANDREWS, The Rogers-Ramanujan reciprocal and Minc's partition function, Pacific J.Math, 95 (1981)251–256.
G. ANDREWS, The hard-hexagon model and Rogers-Ramanujan identities, Proc.Nat.Acad.Sci.U.S.A., 78 (1981)5290–5292.
D.ARQUES, J.FRANCON, M.T.GUICHET and P.GUICHET, Comparison of Algorithms controlling concurrent access to a data base: A combinatorial approach, Research rep. no38, Mulhouse Univ. to appear in Proc.ICALP 1986.
D.ARQUES, P.GUICHET, Asymptotic behaviour and comparison of algorithms controlling concurrent access to a data base, Research report no 40, Mulhouse Univ.,Jan.1986.
R.J. BAXTER, Exactly solved models in statistical mechanics, Academic Press, New-York, 1982.
A.BERTONI, G.MAURI and N.SABADINI, Equivalence and membership problems for regular trace languages, Proc. of the 9th ICALP 1982, Lecture Notes in Comp.Sci. no140(1982) 61–71, Springer-Verlag.
J.BOURRET, Applications algébriques des empilements de pièces et de la méthode involutive en Combinatoire, Mémoire de Maîtrise, UQAM, Montréal, Mai 1985.
P. CARTIER and D. FOATA, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Maths. no 85, Springer-Verlag, New-York/Berlin, 1969.
T. S. CHIHARA, An introduction to orthogonal polynomials, Gordon and Breach, New-York, 1978.
M. CONTENT, F. LEMAY and P. LEROUX, Catégories de Möbius et fonctorialités: un cadre général pour l'inversion de Möbius, J. of Combinatorial Th.A, 28 (1980) 169–190.
R. CORI and Y. METIVIER, Rational subsets of some partially abelian monoids, Theor. Comp. Sci. 35 (1985) 179–189.
R. CORI and D. PERRIN, Sur la reconnaissabilité dans les monoīdes partiellement commutatifs libres, R.A.I.R.O. Info.Th. 19 (1985) 21–32.
M. DESAINTE-CATHERINE, Couplages et Pfaffiens en Combinatoire Physique et Informatique, thèse 3ème cycle, Université Bordeaux I, 1983.
M. DESAINTE-CATHERINE and G. X. VIENNOT, Heaps of pieces, III: Matching polynomials of graphs, in preparation.
D. DHAR, equivalence of the two-dimensional directed-site animal problem to Baxter's hard-square lattice-gas model, Phys.Rev.Lett., 49 (1982) 959–962.
D. DHAR, Exact solution of a directed site-animals enumeration problem in three dimensions, J. Phys. A 15 (1982) 1849–1859.
S. DULUCQ and G. X. VIENNOT, Heaps of pieces, II: the Cartier-Foata flow monoid revisited and combinatorial proofs in matrix algebra, in preparation.
C. DUBOC, Some properties of commutation in free partially commutative monoids, Inform.Proc.Let. 20 (1985) 1–4.
E. J. FARREL, An introduction to matching polynomials, J. Combinatorial Theory B, 27 (1979) 75–86.
E. J. FARRELL, A survey of the unifying effects of F-polynomials in “Combinatorics and Graph Theory”, Proc. 4th Yugoslav Seminar on Graph Theory, Novi Sad, (1983), 137–150.
P. FLAJOLET, Combinatorial aspects of continued fractions, Discrete Math., 32 (1980) 125–161.
M. P. FLE and G. ROUCAIROL, Maximal serializability of iterated transactions, ACM SIGACT SIGOPS, (1982) 194–200.
D. FOATA, Etude algébrique de certains problèmes d'Analyse Combinatoire et du calcul des Probabilités, Publ. Inst. Stat. Univ. Paris, 14 (1965) 81–24.
D. FOATA, "La série génératrice exponentielle dans les problèmes d'énumérations", Les Presses de l'Univ. de Montréal, 1974
D. FOATA, A non-commutative version of the matrix inversion formula, Adv. in Maths., 31 (1979) 330–349.
D. FOATA, A combinatorial proof of Jacobi's identity, Annals of Discrete Math., 6 (1980), 125–135.
J. FRANÇON, Une approche quantitative de l'exclusion mutuelle to appear in R.A.I.R.O.
J. FRANÇON, Sérialisabilité, commutation, mélange et tableaux de Young, Research report no 27, Mulhouse Univ., 1985.
I. GESSEL, Personnal communication.
C. D. GODSIL, Matchings and walks in graphs, J. of Graph Th., 5 (1981) 285–291.
C. D. GODSIL and I. GUTMAN, On the theory of the matching polynomial, J. of Graph Th., 5 (1981) 137–144.
D. GOUYOU-BEAUCHAMPS and G. X. VIENNOT, Equivalence of the 2d directed animals problem to a 1d path problem, preprint 1985, submitted to Adv. in Maths.
V. HAKIM and J. P. NADAL, exact results for 2d directed animals on a strip of finite width, J.Phys. A: Math. Gen.; 16 (1983) L 213–218.
O. T. HEILMANN and E. H. LIEB, Monomers and dimers, Phys. Rev. Lett., 24 (1970) 1412–1414.
D. M. JACKSON, The Combinatorial interpretation of the Jacobi identity from Lie algebras, J. Combinatorial Th.A, 23 (1977) 233–257.
S. N. JONI and G. C. ROTA, Coalgebras and bialgebras in Combinatorics, studies in Applied Maths, 61 (1979) 93–134.
A. JOYAL, Une théorie combinatoire des séries formelles, Advances in Maths., 42 (1981) 1–82.
G. LALLEMENT, Semigroups and Combinatorial applications, John Wiley, New-York, 1979
M. LOTHAIRE, Combinatorics on words, Encyclopedia Maths. and its applications, G. C. Rota ed., vol. 2, Addison-Wesley, Reading, 1983.
J. P. NADAL, B. DERRIDA and J. VANNIMENUS, Directed lattice animals in 2 dimensions: numerical and exact results, J. Physique, 43 (1982) 1561.
C. H. PAPADIMITRIOU, Concurrency control by Locking, SIAM J. on Comp., 12 (1983) 215–226.
D. PERRIN, Words over a partially commutative monoid, in “Combinatorial algorithms on words”, eds. A. Apostolics and Z. Galil, NATO ASI Series, vol F12, Springer-Verlag, Berlin Heidelberg, 1985, 329–340.
G. C. ROTA, On the foundations of combinatorial theory I. Theory of Möbius functions, Z. Wahrsch., 2 (1964) 340–368.
R. STANLEY, Acyclic orientations of graphs, Discrete Maths. 5 (1973) 171–178.
H. STRAUBING, A combinatorial proof of the Cayley-Hamilton theorem, Discrete Math. 43 (1983) 273–279.
G. X. VIENNOT, Une théorie combinatoire des polynômes orthogonaux généraux, lecture Notes, Université du Québec à Montréal, Dpt. de Maths. 1984, 215p.
G. X. VIENNOT, A combinatorial theory for general orthogonal polynomials with extensions and applications, in “Polynômes orthogonaux and Applications”, Proc. Bar-le-duc 1984, eds C. Brezinski, A. Draux A.P. Magnus P. Maroni and A. Ronveaux, Lecture Notes in Maths. no 1171, 139–157, Springer-Verlag, Berlin, 1985.
G. X. VIENNOT, Problèmes combinatoires posés par la physique statistique, Séminaire N.BOURBAKI, exposé no 626 36è année, in Astérisque no121–122 (1985) 225–246, SMF.
G. X. VIENNOT, Heaps of pieces, IV: Combinatorial solution of the directed animal problem, in preparation.
G. X. VIENNOT, Heaps of pieces, V: Combinatorial interpretation of the density of a gas with hard-core interactions, in preparation.
D. ZEILBERGER, A combinatorial approach to matrix algebra, Discrete Maths, 56 (1985) 61–72.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag
About this paper
Cite this paper
Viennot, G.X. (1986). Heaps of pieces, I : Basic definitions and combinatorial lemmas. In: Labelle, G., Leroux, P. (eds) Combinatoire énumérative. Lecture Notes in Mathematics, vol 1234. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0072524
Download citation
DOI: https://doi.org/10.1007/BFb0072524
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-17207-9
Online ISBN: 978-3-540-47402-9
eBook Packages: Springer Book Archive