×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baxter, R.J., Exactly solved models in statistical mechanics, (1982), Academic Press New York · Zbl 0538.60093
[2] Berge, C., Graphes et hypergraphes, (1968), Dunod Paris · Zbl 0213.25702
[3] Cartier, P.; Foata, D., Prolbèmes combinatoires de commutations et réarrangements, () · 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.
[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.
[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, () · 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, ()
[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, (), 243-262 · Zbl 0476.05029
[18] Knuth, D.E., The art of computers programming, vol. 3, sorting and searching, (1973), Addison-Wesley Reading, MA · Zbl 0302.68010
[19] Lothaire, M., ()
[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, ()
[23] Penaud, J.G., Arbres et animaux, (1990), 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). · Zbl 1084.82566
[25] Schützenberger, M.P., Certain elementary families of automata, (), 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., ()
[28] Viennot, X.G., Problèmes combinatoires posés par la physique statistique, Séminaire bourbaki n∘ 626, 36^ème année, (), 225-246, n∘ 121-122
[29] Viennot, X.G., Enumerative combinatorics and algebraic languages, (), 450-464
[30] Viennot, X.G., Heaps of pieces, I: basic definitions and combinatorial lemmas, (), 210-245, Lecture Notes in Math.
[31] Viennot, X.G., Combinatoire énumérative, (1989), 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. 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.