×
Bousquet-Mélou, Mireille; Viennot, Xavier Gérard

Empilements de segments et \(q\)-énumération de polyominos convexes dirigés. (Heaps of segments and \(q\)-enumeration of directed convex polyominoes). (French) Zbl 0753.05023

J. Comb. Theory, Ser. A 60, No. 2, 196-224 (1992).
Summary: We enumerate parallelogram polyominoes and directed and convex polyominoes by construting a bijection between parallelogram polyominoes and some heaps of segments. An extension of a Möbius inversion theorem then gives the generating functions.

Cited in 3 Reviews
Cited in 21 Documents

MSC:

05B50 Polyominoes

Keywords:

heaps of segments; directed convex polynominoes; parallelogram polyominoes; Möbius inversion theorem
PDF BibTeX XML Cite
\textit{M. Bousquet-Mélou} and \textit{X. G. Viennot}, J. Comb. Theory, Ser. A 60, No. 2, 196--224 (1992; Zbl 0753.05023)
Full Text: DOI

References:

[1] Andrews, G. E., (Rota, G. C., “The Theory of Plane Partitions,” Vol. 2, Encyclopedia of Math. and Its Applications (1976), Addison-Wesley: Addison-Wesley Reading, MA)
[2] Bender, E., Convex \(n\)-ominoes, Discrete Math., 8, 219-226 (1974) · Zbl 0284.05009
[5] Cartier, P.; Foata, D., Problèmes combinatoires de commutations et réarrangements, (Lect. Notes in Math., Vol. 85 (1969), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0186.30101
[6] Chang, S. J.; Lin, K. Y., Rigourous results for the number of convex polygons on the square and honeycomb lattices, J. Phys. A: Math. Gen., 21, 2635-2642 (1988)
[7] Dhar, D., Equivalence of the two-dimensional directed animal problem to Baxter hard-square lattice-gas model, Phys. Rev. Lett., 49, 959-962 (1982)
[8] Dhar, D., Exact solution of a directed-site animals enumeration in 3 dimensions, Phys. Rev. Lett., 59, 853-856 (1983)
[11] Delest, M. P.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci., 34, 169-206 (1984) · Zbl 0985.68516
[12] Derrida, B.; Nadal, J. P.; Vannimenus, J., Directed lattices animals in 2 dimensions: Numerical and exact results, J. Phys., 43, 1561 (1982)
[13] Fedou, J. M., Grammaires et \(q\)-énumération de polyominos, (Thèse de Doctorat (1989), Université Bordeaux I) · Zbl 0771.05008
[14] Fedou, J. M., Enumeration of skew Ferrers diagrams and basic Bessel functions, à paraître dans les actes de, (Second Conference on Lattice Paths and Combinatorics and Applications. Second Conference on Lattice Paths and Combinatorics and Applications, Hamilton (1990)) · Zbl 0771.05008
[16] Flajolet, P., Combinatorial aspects of continued fractions, Discrete Math., 41, 145-153 (1982) · Zbl 0492.05003
[18] Gessel, I., A noncommutative generalization and \(q\)-analog of the Lagrange inversion formula, Trans. Amer. Math. Soc., 257, 455-482 (1980) · Zbl 0459.05014
[19] Gouyou-Beauchamps, D.; Viennot, X. G., Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math., 9, 334-357 (1988) · Zbl 0727.05036
[20] Hakim, V.; Nadal, J. P., Exact result for 2D directed lattice animals on a strip of finite width, J. Phys. A: Math. Gen., 16, L213-L218 (1983)
[21] Klarner, D. A.; Rivest, R. L., A procedure for improving the upper bound for the number of \(n\)-ominoes, Canad. J. Math., 25, 585-602 (1973) · Zbl 0261.05113
[22] Klarner, D. A.; Rivest, R. L., Asymptotic bounds for the number of convex \(n\)-ominoes, Discrete Math., 8, 31-40 (1974) · Zbl 0274.05111
[23] Perrin, D., Partial commutations, (Lect. Notes in Comput. Sci., Vol. 372 (1989), Springer-Verlag: Springer-Verlag Berlin), 637-651
[24] Privman, V.; Svrakic, N. M., Exact generating function for fully directed compact lattice animals, Phys. Rev. Lett., 60, No. 12, 1107-1109 (1988)
[25] Rota, G. C., On the foundations of combinatorial theory I, Theory of Möbius functions, Z. Wahrsch. Verw. Gebiete, 2, 340-368 (1964) · Zbl 0121.02406
[26] Temperley, H. N.V, Phys. Rev., 103, 1-16 (1956)
[27] Viennot, X. G., “Problèmes combinatoires posés par la physique statistique,” Séminaire Bourbaki \(n^o 626, 36^{ème}\) année, Astérisque, 121-122, 225-246 (1985)
[28] Viennot, X. G., Heaps of pieces I: Basic definitions and combinatorial lemmas, (Labelle, G.; Leroux, P., Combinatoire énumérative. Combinatoire énumérative, Lect. Notes in Math., Vol. 1234 (1986), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0792.05012
[29] Wright, E. M., Stacks, Quart. J. Math. Oxford (2), 19, 313-320 (1968) · Zbl 0253.05007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.