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

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
PDF
BibTeX
XML
Cite

\textit{D. Gouyou-Beauchamps} and \textit{G. Viennot}, Adv. Appl. Math. 9, No. 3, 334--357 (1988; Zbl 0727.05036)

Full Text:
DOI

### Online Encyclopedia of Integer Sequences:

Number of directed animals of size n (or directed n-ominoes in standard position).Number of directed animals of size n (k=1 column of A038622); number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, where s(0) = 2; also sum of row n+1 of array T in A026323.

Number of compact-rooted directed animals of size n having 3 source points.

Triangular array that counts rooted polyominoes.

The fourth column of A038622, triangular array that counts rooted polyominoes.

Triangle read by rows: T(n,k) gives the number of domino towers of height k consisting of n bricks.

### 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) |

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.