Skip to main content
SpringerLink
Log in

Heaps of pieces, I : Basic definitions and combinatorial lemmas

  • Conference paper
  • First Online:
Book cover Combinatoire énumérative

Part of the book series: Lecture Notes in Mathematics ((LNM,volume 1234))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 44.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 59.95
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. G. ANDREWS, The Theory of partitions, Encyclopedia of Maths. and its applications, G.C. Rota ed., vol 2, Addison Wesley, Reading, 1976

    Google Scholar 

  2. G. ANDREWS, The Rogers-Ramanujan reciprocal and Minc's partition function, Pacific J.Math, 95 (1981)251–256.

    Article  MathSciNet  MATH  Google Scholar 

  3. G. ANDREWS, The hard-hexagon model and Rogers-Ramanujan identities, Proc.Nat.Acad.Sci.U.S.A., 78 (1981)5290–5292.

    Article  MathSciNet  MATH  Google Scholar 

  4. 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.

    Google Scholar 

  5. 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.

    Google Scholar 

  6. R.J. BAXTER, Exactly solved models in statistical mechanics, Academic Press, New-York, 1982.

    MATH  Google Scholar 

  7. 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.

    Google Scholar 

  8. 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.

    Google Scholar 

  9. 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.

    Chapter  Google Scholar 

  10. T. S. CHIHARA, An introduction to orthogonal polynomials, Gordon and Breach, New-York, 1978.

    MATH  Google Scholar 

  11. 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.

    Article  MathSciNet  MATH  Google Scholar 

  12. R. CORI and Y. METIVIER, Rational subsets of some partially abelian monoids, Theor. Comp. Sci. 35 (1985) 179–189.

    Article  MathSciNet  MATH  Google Scholar 

  13. 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.

    MathSciNet  Google Scholar 

  14. M. DESAINTE-CATHERINE, Couplages et Pfaffiens en Combinatoire Physique et Informatique, thèse 3ème cycle, Université Bordeaux I, 1983.

    Google Scholar 

  15. M. DESAINTE-CATHERINE and G. X. VIENNOT, Heaps of pieces, III: Matching polynomials of graphs, in preparation.

    Google Scholar 

  16. 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.

    Article  MathSciNet  Google Scholar 

  17. D. DHAR, Exact solution of a directed site-animals enumeration problem in three dimensions, J. Phys. A 15 (1982) 1849–1859.

    Article  MathSciNet  Google Scholar 

  18. S. DULUCQ and G. X. VIENNOT, Heaps of pieces, II: the Cartier-Foata flow monoid revisited and combinatorial proofs in matrix algebra, in preparation.

    Google Scholar 

  19. C. DUBOC, Some properties of commutation in free partially commutative monoids, Inform.Proc.Let. 20 (1985) 1–4.

    Article  MathSciNet  MATH  Google Scholar 

  20. E. J. FARREL, An introduction to matching polynomials, J. Combinatorial Theory B, 27 (1979) 75–86.

    Article  MathSciNet  Google Scholar 

  21. 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.

    Google Scholar 

  22. P. FLAJOLET, Combinatorial aspects of continued fractions, Discrete Math., 32 (1980) 125–161.

    Article  MathSciNet  MATH  Google Scholar 

  23. M. P. FLE and G. ROUCAIROL, Maximal serializability of iterated transactions, ACM SIGACT SIGOPS, (1982) 194–200.

    Google Scholar 

  24. 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.

    MathSciNet  MATH  Google Scholar 

  25. 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

    Google Scholar 

  26. D. FOATA, A non-commutative version of the matrix inversion formula, Adv. in Maths., 31 (1979) 330–349.

    Article  MathSciNet  MATH  Google Scholar 

  27. D. FOATA, A combinatorial proof of Jacobi's identity, Annals of Discrete Math., 6 (1980), 125–135.

    Article  MathSciNet  MATH  Google Scholar 

  28. J. FRANÇON, Une approche quantitative de l'exclusion mutuelle to appear in R.A.I.R.O.

    Google Scholar 

  29. J. FRANÇON, Sérialisabilité, commutation, mélange et tableaux de Young, Research report no 27, Mulhouse Univ., 1985.

    Google Scholar 

  30. I. GESSEL, Personnal communication.

    Google Scholar 

  31. C. D. GODSIL, Matchings and walks in graphs, J. of Graph Th., 5 (1981) 285–291.

    Article  MathSciNet  MATH  Google Scholar 

  32. C. D. GODSIL and I. GUTMAN, On the theory of the matching polynomial, J. of Graph Th., 5 (1981) 137–144.

    Article  MathSciNet  MATH  Google Scholar 

  33. 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.

    Google Scholar 

  34. 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.

    Article  MathSciNet  Google Scholar 

  35. O. T. HEILMANN and E. H. LIEB, Monomers and dimers, Phys. Rev. Lett., 24 (1970) 1412–1414.

    Article  Google Scholar 

  36. D. M. JACKSON, The Combinatorial interpretation of the Jacobi identity from Lie algebras, J. Combinatorial Th.A, 23 (1977) 233–257.

    Article  MathSciNet  MATH  Google Scholar 

  37. S. N. JONI and G. C. ROTA, Coalgebras and bialgebras in Combinatorics, studies in Applied Maths, 61 (1979) 93–134.

    Article  MathSciNet  MATH  Google Scholar 

  38. A. JOYAL, Une théorie combinatoire des séries formelles, Advances in Maths., 42 (1981) 1–82.

    Article  MathSciNet  MATH  Google Scholar 

  39. G. LALLEMENT, Semigroups and Combinatorial applications, John Wiley, New-York, 1979

    MATH  Google Scholar 

  40. M. LOTHAIRE, Combinatorics on words, Encyclopedia Maths. and its applications, G. C. Rota ed., vol. 2, Addison-Wesley, Reading, 1983.

    Google Scholar 

  41. J. P. NADAL, B. DERRIDA and J. VANNIMENUS, Directed lattice animals in 2 dimensions: numerical and exact results, J. Physique, 43 (1982) 1561.

    Article  MathSciNet  Google Scholar 

  42. C. H. PAPADIMITRIOU, Concurrency control by Locking, SIAM J. on Comp., 12 (1983) 215–226.

    Article  MathSciNet  MATH  Google Scholar 

  43. 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.

    Chapter  Google Scholar 

  44. G. C. ROTA, On the foundations of combinatorial theory I. Theory of Möbius functions, Z. Wahrsch., 2 (1964) 340–368.

    Article  MathSciNet  MATH  Google Scholar 

  45. R. STANLEY, Acyclic orientations of graphs, Discrete Maths. 5 (1973) 171–178.

    Article  MathSciNet  MATH  Google Scholar 

  46. H. STRAUBING, A combinatorial proof of the Cayley-Hamilton theorem, Discrete Math. 43 (1983) 273–279.

    Article  MathSciNet  MATH  Google Scholar 

  47. 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.

    Google Scholar 

  48. 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.

    Chapter  Google Scholar 

  49. 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.

    Google Scholar 

  50. G. X. VIENNOT, Heaps of pieces, IV: Combinatorial solution of the directed animal problem, in preparation.

    Google Scholar 

  51. G. X. VIENNOT, Heaps of pieces, V: Combinatorial interpretation of the density of a gas with hard-core interactions, in preparation.

    Google Scholar 

  52. D. ZEILBERGER, A combinatorial approach to matrix algebra, Discrete Maths, 56 (1985) 61–72.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université de Bordeaux I U.E.R. de Mathématiques et d'Informatique, Talence Cedex, France

    Gérard Xavier Viennot

Authors
  1. Gérard Xavier Viennot
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Gilbert Labelle Pierre Leroux

Rights and permissions

Reprints 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

Publish with us

Policies and ethics

Search

Navigation