Equivalence of the two-dimensional directed animal problem to a one- dimensional path problem. (English) Zbl 0727.05036

Gouyou-Beauchamps, D.; Viennot, G.

Adv. Appl. Math. 9, No. 3, 334-357 (1988).

Summary: We introduce a one-to-one correspondence between directed animals on a square lattice and a class of one-dimensional paths. We derive very simply the formulae giving the exact number of directed animals of given size and the average width of such animals. The more surprising result is the fact that the number of compact-rooted directed animals of size n is \(3^{n-1}\).

MSC:

05C38	Paths and cycles
82B20	Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics

Keywords:

directed animals

References:

[1]	Baxter, R., Exactly Solved Models in Statistical Mechanics (1982), Academic Press: Academic Press New York · Zbl 0538.60093
[2]	Baxter, R. J., Hard hexagons: Exact solution, J. Phys. A, 13, L61-L70 (1980)
[3]	Breuer, N., Corrections to scaling for directed branched polymers (lattice animals), preprint, Z. Phys. B (1983), in press
[4]	Breuer, N.; Jansen, H. K., Critical behaviour of directed branched polymers and the dynamics at the Yang-Lee edge singularity, Z. Phys. B, 48, 347-350 (1982)
[5]	Cardy, J. L., Directed lattice animals and the Lee-Yang edge singularity, J. Phys. A, 15, 593-595 (1982)
[6]	Day, A. R.; Lubensky, T. C., ε expansion for directed animals, J. Phys. A, 15, 285-290 (1982)
[7]	Derrida, B.; Nadal, J. P., A model of directed compact animals, J. Phys. Lett., 45, L701-L706 (1984)
[8]	Dhar, D., Equivalence of the two-dimensional directed-site animal problem to the Baxter’s Hard-Square Lattice-Gas model, Phys. Rev. Lett., 49, 959-962 (1982)
[9]	Dhar, D., Exact solution of a directed-site animals-enumeration problem in 3 dimensions, Phys. Rev. Lett., 59, 853-856 (1983)
[10]	Dhar, D.; Phani, M. K.; Barma, M., Enumeration of directed site animal on two-dimensional lattices, J. Phys. A, 15, 279-284 (1982)
[11]	(Domb, C.; Green, M. S., Phase Transition and Critical Phenomena (1974), Academic Press: Academic Press New York)
[12]	Duarte, J. A.M. S., The percolation perimeter for two-dimensional directed animals, Z. Phys. B, 58, 69-70 (1984)
[13]	Duarte, J. A.M. S., The singularity structure of fixed cycle directed site animals, preprint (1985)
[14]	Family, F., Relation between size and shape of isotropic and directed percolation clusters and lattice animals, J. Phys. A, 15, 583-592 (1982)
[15]	Green, J. E.; Moore, M. A., Application of directed lattice animal theory to river network, J. Phys. A, 15, 597-599 (1982)
[16]	Hakim, V.; Nadal, J. P., Exact results for 2D directed animals on a strip for finite width, J. Phys. A, 16, 213-218 (1983)
[17]	Hermann, H.; Family, F.; Stanley, H. E., Position-space renormalisation group for polymers, J. Phys. A, 16, 375-379 (1983)
[18]	Lubensky, T. C.; Vannimenus, J., Flory approximation for directed branched polymers and directed percolation, J. Physique, 43, 377-381 (1982)
[19]	Nadal, J. P., Etude de systèmes dirigés en physique statistique, (Thèse 3ème cycle (1983), Univ. d’Orsay)
[20]	Nadal, J. P.; Derrida, B.; Vannimenus, J., Directed lattice animals in 2 dimensions: Numerical and exact results, J. Physique, 43, 1561 (1982)
[21]	Nadal, J. P.; Derrida, B.; Vannimenus, J., Directed diffusion-controlled aggregation versus directed animals, preprint (1983)
[22]	Privman, V.; Barma, M., Radi of gyration of fully and partially directed lattice animals, preprint (1985)
[23]	Redner, S.; Coniglio, A., Flory theory for directed lattice animals and directed percolation, J. Phys. A, 15, 273-278 (1982)
[24]	Redner, S.; Yang, Z. R., Size and shape of directed lattice animals, J. Phys. A, 15, 177-187 (1982)
[25]	Ruelle, D., Statistical Mechanics, Rigorous Results, Benjamin (1974), New York
[26]	Sahimi, M., Critical exponents and thresholds for percolation and conduction, (The Mathematics and Physics of Disordered Media. The Mathematics and Physics of Disordered Media, Lecture Notes in Math., Vol. 1035 (1983), Springer-Verlag: Springer-Verlag New York/Berlin), 314-346
[27]	Stanley, H. E.; Redner, S.; Yang, Z. R., Site and bond directed branched polymers for arbitrary dimensionality: Evidence supporting a relation with the Lee-Yang edge arbitrary, J. Phys. A, 15, 569-573 (1982)
[28]	Viennot, G., (Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki, 36ème année, 1983/84, exposé n∘626. Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki, 36ème année, 1983/84, exposé n∘626, Astérisque, 121/122 (1985)), 225-246
[31]	Cori, R.; Viennot, G., A synthesis of bijection related to Catalan numbers (1983), unpublished
[32]	Donaghey, R.; Shapiro, L. W., Motzkin numbers, J. Combin. Theory Ser. A, 23, 291-301 (1977) · Zbl 0417.05007
[33]	Sloane, (A Handbook of Integer Sequences (1973), Academic Press: Academic Press New York) · Zbl 0286.10001
[34]	Viennot, G., Une théorie combinatoire des polynomes orthogonaux généraux, (Notes de conférences à l’Université de Montréal (1984), UQAM)