Directed animals, forests and permutations

In this paper, we illustrate a method to enumerate two-dimensional directed animals, with compact sources, on both the square and the triangular lattice. We give a recursive description of these structures from which we deduce their generating function, according to various parameters: the area, the right half-width and the number of compact sources. We determine the average number of compact sources in both lattices. Referring to single-source animals on the square lattice, we show the bijections connecting them to the forests of 1-2 frees and to permutations with the forbidden subsequence: 321, 4 (1) over bar 523. In a similar way we describe the bijections between single-source animals on the triangular lattice and forests of binary flees. Each of these two objects presents a bijection with two permutations with the forbidden subsequences: 4132, 4231, 4312, 4321. (C) 1999 Elsevier Science B.V. All rights reserved.