×

Animaux et arbres guingois. (Animals and guingois trees). (French) Zbl 0780.68098

Summary: The directed animals are put in a one-to-one correspondence with a kind of lop-sided trees, called guingois trees. Through this bijection, we get a simple coding for the animals; we show that this coding is related to a representation of animals by heaps of dimers.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
05C05 Trees
68Q45 Formal languages and automata
05B50 Polyominoes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baxter, R. J., Exactly Solved Models in Statistical Mechanics (1982), Academic Press: Academic Press New York · Zbl 0538.60093
[2] Berge, C., Graphes et Hypergraphes (1968), Dunod: Dunod Paris · Zbl 0213.25702
[3] Cartier, P.; Foata, D., Prolbèmes combinatoires de commutations et réarrangements, (Lecture Notes in Math., Vol. 85 (1969), Springer: Springer Berlin) · Zbl 0186.30101
[4] Chottin, L.; Cori, R., Une preuve combinatoire de la rationalité d’une série génératrice associée aux arbres, RAIRO, 16, 2, 113-128 (1982) · Zbl 0509.05006
[5] R. Conil et J.G. Penaud, Génération aléatoire et dessin d’animaux 2D et 3D, en préparation.; R. Conil et J.G. Penaud, Génération aléatoire et dessin d’animaux 2D et 3D, en préparation.
[6] M.P. Delest et S. Dulucq, Enumeration of directed column-convex animals with given perimeter and area, Rapport n∘ 86-15, Université de Bordeaux I.; M.P. Delest et S. Dulucq, Enumeration of directed column-convex animals with given perimeter and area, Rapport n∘ 86-15, Université de Bordeaux I.
[7] Derrida, B.; Nadal, J. P., On a model of directed compact animal, J. Physique Lett., 45, 701 (1984)
[8] Dhar, D., Equivalence of the two-dimensional directed animal problem to Baxter hard-square lattice-gas model, Phys. Rev Lett., 49, 959-962 (1982)
[9] Dhar, D., Exact solution of a directed-site animals enumeration in 3 dimensions, Phys. Rev. Lett., 59, 853-856 (1983)
[10] Dhar, D.; Phani, M. K.; Barma, M., Enumeration of directed site animals on two-dimensional lattice, J. Phys. A.: Math Gen., 15, L 279-L 284 (1982)
[11] Duchamp, G.; Krob, D., L’algèbre de Lie partiellement commutative libre: des bases et des rangs, (Rapport LITP n∘ 89-92 (1989), Université de Paris VII) · Zbl 0763.17003
[12] Dulucq, S., Etude combinatoire de problèmes d’énumération d’algorithmique sur les arbres et de codage par des mots, (Thèse d’Etat (1987), Université de Bordeaux I)
[13] Françon, J., Sur le nombre de registres nécessaire à l’évaluation d’une expression arithmétique, RAIRO Inform. Théor., 18, 355-364 (1984) · Zbl 0547.68041
[14] 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
[15] Hakim, V.; Nadal, J. P., Exact results for 2D directed lattice animals on a strip of finite with, J. Phys. A: Math. Gen., 16, L 213-L 218 (1983)
[16] Hickey, T.; Cohen, J., Uniform random generation of strings in a context-free language, SIAM J. Comput., 12, 645-655 (31983) · Zbl 0524.68046
[17] Klarner, D. A., My life among polyominoes, (The Mathematical Gardner (1981), Wadsworth: Wadsworth Belmont, CA), 243-262 · Zbl 0476.05029
[18] Knuth, D. E., The Art of Computers Programming, Vol. 3, Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010
[19] Lothaire, M., (Rota, Gian-Carlo, Combinatorics on Words, Encylopedia of Mathematics and its Applications (1983), Addison-Wesley: Addison-Wesley Amsterdam) · Zbl 0514.20045
[20] Lubensky, T. C.; Vannimenus, J., Flory approximation for directed branched polymers and directed percolation, J. Physique, 43, L 377-L 381 (1982)
[21] Nadal, J. P.; Derrida, B.; Vannimenus, J., Directed lattice animals in 2 dimensions: numerical and exact results, J. Physique, 43, 1561 (1982)
[22] Penaud, J. G., Une nouvelle bijection pour les animaux dirigés, (Actes du \(22^{ème}\) Séminaire Lotharingien de Combinatoire (1989), Université de Strasbourg)
[23] Penaud, J. G., Arbres et animaux (1990), Mémoire d’habilitation à diriger des recherches: Mémoire d’habilitation à diriger des recherches Bordeaux Mai · Zbl 0780.68098
[24] V. Privman et N.M. Svrakic, Directed models of polymers, interfaces, and clusters: scaling and finite-size properties, Lecture Notes in Physics, Vol. 338 (Springer, Berlin).; V. Privman et N.M. Svrakic, Directed models of polymers, interfaces, and clusters: scaling and finite-size properties, Lecture Notes in Physics, Vol. 338 (Springer, Berlin). · Zbl 1084.82566
[25] Schützenberger, M. P., Certain elementary families of automata, (Proc. Symp. on Math. Theory of Automata (1962), Polytechnic Institute of Brooklyn), 139-153 · Zbl 0221.94080
[26] Schützenberger, M. P., Context-free languages and pushdown automata, Inform. and Control, 6, 246-264 (1963) · Zbl 0123.12502
[27] Temperley, H. N.V., (Horwood, E., Graph Theory and Applications (1981), Wiley: Wiley New York) · Zbl 0481.05001
[28] Viennot, X. G., Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki n∘ \(626, 36^{ème}\) année, (Astérisque (1985), Soc. Math. France), 225-246, n∘ 121-122
[29] Viennot, X. G., Enumerative combinatorics and algebraic languages, (Budach, L., Proc. FCT’85. Proc. FCT’85, Lecture Notes in Computer Science, Vol. 199 (1985), Springer: Springer Berlin), 450-464
[30] Viennot, X. G., Heaps of pieces, I: basic definitions and combinatorial lemmas, (Labelle, G.; Leroux, P., Combinatoire énumérative, Vol. 1234 (1986), Springer: Springer Berlin), 210-245, Lecture Notes in Math. · Zbl 0618.05008
[31] Viennot, X. G., Combinatoire énumérative (1989), cours ENS Ulm: cours ENS Ulm Paris
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.