Axel Bacher

Average site perimeter of directed animals on the two-dimensional lattices

We introduce new combinatorial (bijective) methods that enable us to compute the average value of three parameters of directed animals of a given area, including the site perimeter. Our results cover directed animals of any one-line source on the square lattice and its bounded variants, and we give counterparts for most of them in the triangular lattices. We thus prove conjectures by Conway and Le Borgne. The techniques used are based on Viennot's correspondence between directed animals and heaps of pieces (or elements of a partially commutative monoid).

Introduction

Let Γ be an oriented graph and S a nonempty finite set of vertices of Γ. A directed animal of source S on Γ is a finite set of vertices A that contains S and such that for every vertex v of A, there exists a vertex s of S and a path from s to v going only through vertices of A. The vertices of a directed animal A are called sites. The area of A, denoted by |A|, is the number of sites of A.

On Figure 1 are depicted single-source directed animals on the three twodimensional regular lattices: the square lattice, the triangular lattice, and the honeycomb lattice. Single-source directed animals constitute a subclass of animals (an animal on a non-oriented graph Γ is simply a finite connected set of vertices of Γ). While the enumeration of animals on any lattice is an open problem despite extensive research for decades, directed animals are fairly easier to enumerate. As we will not deal with general animals in this paper, we will abusively use the term animal instead of directed animal.

Single-source directed animals on the square and triangular lattices have been enumerated [START_REF] Dhar | Equivalence of the two-dimensional directed-site animal problem to Baxter's hard-square lattice-gas model[END_REF][START_REF] Gouyou-Beauchamps | Equivalence of the twodimensional directed animal problem to a one-dimensional path problem[END_REF][START_REF] Bétréma | Modèles avec particules dures, animaux dirigés et séries en variables partiellement commutatives[END_REF]. Specifically, let a(n) and ā(n) be the number of animals of source {(0, 0)} and area n on the square and triangular lattice, respectively. The generating functions of these numbers are:

n≥1 a(n)t n = 1 2 1 + t 1 -3t -1 ; (1) n≥1 ā(n)t n = 1 2 1 √ 1 -4t -1 . ( 2
)
Even then, much remains unclear. The enumeration of directed animals on the honeycomb lattice is an open problem, and according to [START_REF] Guttmann | Hexagonal lattice directed site animals[END_REF], the generating function is probably not D-finite; on the square and triangular lattices, comparatively very little is known when one tries to take into account parameters other than area.

Today, two enumeration methods account for almost every known result on directed animals. One of them is the gas model technique, originally used by Dhar [START_REF] Dhar | Equivalence of the two-dimensional directed-site animal problem to Baxter's hard-square lattice-gas model[END_REF]. This technique was further developed by Bousquet-Mélou [START_REF] Bousquet-Méelou | New enumerative results on two-dimensional directed animals[END_REF]; see also [START_REF] Borgne | Directed animals and gas models revisited[END_REF][START_REF] Albenque | A note on the enumeration of directed animals via gas considerations[END_REF] for more recent work.

The method used in this paper is the second one, based on a correspondence, due to Viennot [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF], between animals and other objects called heaps of dominoes. The basic idea is to replace each site of an animal by a 2×1 domino, so that each domino either lies on the ground or sits on one or two other dominoes (Figure 2). As we will see later, this method works for the triangular lattice as well. However, no simple model of heaps of dominoes has been found to correspond to animals on the honeycomb lattice. This may explain the lack of knowledge on the subject.

The purpose of this paper is to study three other parameters of directed animals, introduced below, and illustrated in Figure 3: • two sites of an animal on the square or triangular lattice are adjacent if they are of the form (i+1, j) and (i, j +1). We denote by j(A) the number of pairs of adjacent sites of A. • a loop consists of two adjacent sites (i + 1, j) and (i, j + 1), along with a third site at (i + 1, j + 1). We denote by ℓ(A) the number of loops of A. • a neighbour of an animal A of source S is a vertex v not in A, such that A ∪ {v} is still a directed animal of source S. The number of neighbours of A is called the site perimeter of A and is denoted by p(A). Taking, for instance, the site perimeter, we may consider the bivariate generating function counting single-source animals according to both area and perimeter on the square lattice:

A p (t, u) = A t |A| u p(A) .
This generating function is not known, and is believed not to be D-finite [START_REF] Jensen | Series expansions for two-dimensional directed percolation[END_REF]. Instead, we will consider the generating function giving the total number of neighbours in the animals of a fixed area:

A p(A)t |A| =
∂A p ∂u (t, 1).

By dividing the total site perimeter of the animals of area n by the number of these animals, one gets the average site perimeter in animals of a fixed area.

Alternatively, this generating function may be seen as counting single-source directed animals with a marked neighbour. This function, and the ones that similarly give the average number of adjacent sites and loops, turns out to be easier to derive. Specifically, the value of the generating function counting the total number of loops of single-source animals on the square lattice was obtained by Bousquet-Mélou using gas model methods [START_REF] Bousquet-Méelou | New enumerative results on two-dimensional directed animals[END_REF]:

A ℓ(A)t |A| = 1 2 1 - 1 -4t + t 2 + 4t 3 √ 1 + t(1 -3t) 3/2 . ( 3
)
As for the total site perimeter on the square lattice, it was the object of a conjecture by Conway in 1996 [START_REF] Conway | Some exact results for moments of 2D directed animals[END_REF]:

A p(A)t |A| = 1 2t(1 + t) -1 + t + t 2 + 1 -3t + 2t 2 + t 3 -3t 4 √ 1 + t(1 -3t) 3/2 . ( 4
)
Le Borgne [START_REF] Borgne | Conjectures for the first perimeter moment of directed animals[END_REF] also conjectured the value of similar generating functions counting the site perimeter of animals on square and triangular lattices of bounded width.

In Section 4, we prove these conjectures and give a new proof of (3) using combinatorial methods; moreover, we show that the total number of adjacent sites is given by:

A j(A)t |A| = 1 2t(1 + t) 1 - 1 -4t + t 2 + 4t 3 √ 1 + t(1 -3t) 3/2 . ( 5
)
Actually, our results are more general than that: the same methods can be used on different kinds of lattices, obtained by adding one or two vertical walls (the half-lattice, cylindrical lattices and rectangular lattices, defined in Section 3), and on animals with any fixed source. Knowing, say, the total site perimeter of single-source animals of area n on the square lattice, we get their average perimeter by dividing by the number a(n) of these animals:

p(n) = 1 a(n) |A|=n p(A).
This quantity may thus be computed using ( 1) and ( 4). The numbers of adjacent sites and loops are handled similarly. From these generating functions, singularity analysis [START_REF] Flajolet | Analytic combinatorics[END_REF] yields estimates on these quantities as n tends to infinity:

j(n) ∼ n 4 ; ℓ(n) ∼ n 9 ; p(n) ∼ 3n 4 .
The paper is organized as follows. In Section 2, we introduce in detail the notion of heaps of pieces and give several lemmas useful for animal enumeration. In Section 3, we enumerate directed animals of any source on several kinds of square and triangular lattices, according to area alone. In Section 4, we give a general method to derive the generating functions giving the average number of adjacent sites, number of loops, and site perimeter of directed animals on the square lattice, as well as counterparts of most of these results on the triangular lattice. We derive asymptotic results in Section 5. Finally, we illustrate our formulae with a few examples in Section 6.

Heaps of pieces

The notion of heaps of pieces is due to Viennot, and this topic is covered in detail in [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF]. We repeat the definitions for convenience, and make a few minor additions which we use later.

Basics

Intuitively, a heap is a finite set of pieces. It is built by dropping successively the pieces at certain positions, chosen from a given set. When the positions of two pieces overlap, the second piece falls on the first, like in Figure 2. A formal definition is given below. Definition 2.1. Let Q be a set and C a reflexive symmetric relation on

Q. A heap of the model (Q, C) is a finite subset H of Q × N satisfying:
1. if (q, i) and (q ′ , i) with q = q ′ are in H, then (q, q ′ ) is not in C;

2. if (q, i) is in H and i > 0, then there exists (q ′ , i -1) in H such that (q, q ′ ) is in C.
The relation C is called the concurrency relation, and two positions q and q ′ are concurrent if (q, q ′ ) is in C (in the above intuitive definition, this means that they overlap). The elements of a heap are called pieces. If (q, i) is a piece of a heap, q is called its position and i its height.

The pieces of a heap are naturally equipped with a poset structure: define the relation ≺ such that (q, i) ≺ (q ′ , i ′ ) whenever q and q ′ are concurrent and i < i ′ . Let ≤ be the reflexive transitive closure of ≺. We say that a piece x is below a piece y, or y is above x, if x ≤ y. The pieces x and y are independent if neither is above the other.

The partial order ≤ may be viewed more intuitively: let H be a heap and x a piece of H. If one takes the piece x and push it upwards, it pushes along some pieces in the way. If one pushes it high enough, the moved pieces are exactly the pieces above x.

The pieces of a heap H that are minimal for the order ≤ are called minimal pieces; they are exactly the pieces of height 0. The set of their positions is called the base of H, and denoted by b(H). Likewise, the pieces that are maximal for ≤ are called maximal pieces; we denote by m(H) the set of their positions.

We now define generating functions counting the heaps of a model; we denote by |H| the number of pieces of the heap H. Definition 2.2. Let (Q, C) be a model of heaps and S a finite subset of Q. We denote by H S (t) and H [S] (t) the generating functions (provided they exist) of heaps respectively of base S and with base included in S:

H S (t) = b(H)=S t |H| ; H [S] (t) = b(H)⊆S t |H| .
These two generating functions are obviously linked by:

H [S] (t) = T ⊆S H T (t);
Conversely, the inclusion-exclusion principle yields:

H S (t) = T ⊆S (-1) |S T | H [T ] (t).
Let us now assume that the set of positions Q of the model is finite. In this case, the generating functions above may be computed using a result due to Viennot [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF], which we present below.

A heap is called trivial if all its pieces have height 0. This means that a trivial heap may be identified with the set of the positions of its pieces, which must be pairwise nonconcurrent. As Q is a finite set, there is only a finite number of trivial heaps. We denote by T [S] (t) the alternating generating function of trivial heaps included in S:

T [S] (t) = T ⊆S, T trivial (-t) |T | .
Since Q is finite, this generating function is actually a polynomial, and is usually relatively easy to compute. Lemma 2.3 (Inversion Lemma). Let (Q, C) be a finite heap model and S a subset of Q. The generating function of heaps of base included in S is:

H [S] (t) = T [Q S] (t) T [Q] (t) .
Thanks to this lemma, we see that in a finite model, the generating function H [S] (t) is a quotient of two polynomials, and is therefore rational.

Strict and inflated heaps

In this section, we define families of heaps which we use in the correspondence with directed animals. Let H be a heap, and let (q, i) and (q ′ , i ′ ) be two pieces. We say that (q ′ , i ′ ) sits on (q, i) if q and q ′ are concurrent and i ′ = i + 1. Thus, Condition 2 of Definition 2.1 states that any non-minimal piece must sit on another piece.

The objects obtained by relaxing this condition, keeping only Condition 1, are called pre-heaps. Definition 2.4. A heap or pre-heap is strict if it has no piece sitting on another at the same position, i.e. no two pieces (q, i) and (q, i + 1). Definition 2.5. An inflated heap is a strict pre-heap H, such that for every piece (q, i) satisfying i > 0, at least one of the following pieces is in H:

(a) a piece (q ′ , i -1), such that q and q ′ are concurrent (and q = q ′ );

(b) the piece (q, i -2).

Examples are found in Figure 7. Let H be a heap. A stack of H is a maximal set of pieces all at the same position, with consecutive heights. Thus, a heap is strict if all its stacks have only one piece.

Any heap may be built in a unique manner from a strict heap by replacing each piece by a stack consisting of an arbitrary positive number of pieces; in turn, any inflated heap may be built from a heap by "inflating" each stack, pushing along all pieces above it (see Figure 4).

These remarks enable us to derive from Lemma 2.3 the generating functions of strict and inflated heaps. First, as inflating a stack does not change its base or number of pieces, the generating functions of inflated heaps are the same as those of general heaps. Notation 2.6. Let (Q, C) be a model of heaps. We denote by H S (t) and H [S] (t) the generating functions of strict heaps with base S and base included in S, respectively1 . The construction of Figure 4 translates into a link between the generating functions of strict and general heaps:

H S (t) = H S t 1 -t ,
or equivalently:

H S (t) = H S t 1 + t .
These links remain valid between generating functions of heaps with base included in S.

Factorized heaps

We now present a monoid structure, again due to Viennot, on the set of heaps of a given model. Let H be a heap and q a position. Let H • q be the heap formed by dropping a piece at position q on top of H; more formally, let H • q be H ∪ {(q, i)}, where i is the largest integer such that this is a heap. In this way, a heap may be built one piece at a time. This may be done by adding the pieces in any order compatible with the partial order ≤. This idea is used to define the product of two heaps. Definition 2.7. Let H 1 and H 2 be two heaps. The product H 1 • H 2 is built by letting all pieces of H 2 fall on H 1 , in any order compatible with ≤.

A factorized heap is a heap H, with a distinguished factorization

H = H 1 •H 2 . We denote such a heap (H = H 1 • H 2 ) or (H 1 • H 2 ). A factorized heap (H = H 1 • H 2 ) is strict if H is strict; it is almost strict if both H 1 and H 2 are strict.
The monoid structure induced by this product is isomorphic to the partially commutative monoid [START_REF] Cartier | Problèmes combinatoires de commutation et réarrangements[END_REF] on the alphabet Q, with concurrency relation C. The product is illustrated in Figure 5. We now give a way to compute the base of a factorized heap. If H is a heap, let the neighbourhood of H, denoted v(H), be the set of positions concurrent to at least one piece of H.

Lemma 2.8. Let (H = H 1 • H 2 ) be a factorized heap. The base of the heap H is given by: b(H) = b(H 1 ) ∪ b(H 2 ) \ v(H 1 ) .
Proof. As the heap H is built by dropping all pieces of H 1 , then all pieces of H 2 , no piece of H 1 can be above a piece of H 2 . Therefore, all minimal pieces of H 1 are also minimal pieces in H.

A minimal piece of H 2 is minimal in H if and only if it is not above a piece of H 1 . This happens if and only if its position is not in the neighbourhood of H 1 , hence the given formula.

Given a heap H with base S, we may factorize H as H = S • H 2 . Lemma 2.8 asserts that the base of H 2 is included in v(S). This yields:

H S (t) = t |S| H [v(S)] (t). (6)

Heaps marked with a set of pieces

A number of our problems in animal enumeration can be seen as enumeration of heaps marked with a set of pieces; for example, computing the average number of adjacent sites in animals is linked to enumerating animals with two adjacent sites marked, which is in turn linked to enumerating heaps with some pieces marked. Here, we give a means to link such marked heaps to factorized heaps, which prove to be more manageable.

Definition 2.9. A marked heap (H, X) is a heap H, marked with a set X of pairwise independent pieces. Definition 2.10. Let (H, X) be a marked heap. Let F ↓ (H, X) be the factorized heap

(H = H 1 • H 2 )
where H 1 consists of all pieces below at least a piece of X.

Let F ↑ (H, X) be the factorized heap (H = H 1 • H 2 )
where H 2 consists of all pieces above at least a piece of X.

Definition 2.11. An almost strict marked heap is a marked heap (H, X) such that no piece of H sits on an unmarked piece at the same position.

We call marked stack a stack of an almost strict marked heap containing a marked piece; such a stack may have one or two pieces, and the marked piece is always the lowest piece of the stack. Definition 2.12. Let (H, X) be an almost strict marked heap. Let X + be the set consisting of the highest piece of each marked stack. Define the following factorized heaps: Lemma 2.13. The mappings F ↓ and F ↑ (resp. F ↓ and F ↑ ) are bijections from the set of marked heaps to the set of factorized heaps (resp. almost strict marked heaps to almost strict factorized heaps).

F ↓ (H, X) = F ↓ (H, X); F ↑ (H, X) = F ↑ (H, X + ).
Their inverse bijections are as follows. Let (H = H 1 • H 2 ) be a factorized heap, let X be the set of maximal pieces of H 1 and Y the set of minimal pieces of H 2 . We have:

(H 1 • H 2 ) = F ↓ (H, X) = F ↑ (H, Y ). If (H = H 1 • H 2
) is an almost strict factorized heap, let Y -be the set consisting of the lowest piece of each stack of H containing a piece of Y . We have:

(H 1 • H 2 ) = F ↓ (H, X) = F ↑ (H, Y -).
Proof. Let us first do the case of marked heaps. This fact easily stems from the poset structure on the pieces of a heap: the set X of maximal pieces of H 1 is the only set of pairwise independent pieces such that every piece of H 1 is below a piece of X. The case of F ↑ is identical. We handle almost strict marked heaps similarly. Pulling downwards the lowest piece of each marked stack, or pushing upwards the highest piece, ensures that H 1 and H 2 are strict in the resulting factorized heap; conversely, as the pieces of X and Y -are the lowest of their stacks, (H, X) and (H, Y -) are almost strict marked heaps.

As a first application, we give a means to compute the generating functions of heaps marked with one piece at a fixed position. Definition 2.14. Let q be a position and S a set of positions. We denote by H (q)

[S] (t) the generating function of heaps with base included in S, marked with a piece at position q. We denote by V q

[S] (t) the set of heaps with base included in S avoiding q, i.e. such that no piece is concurrent to q. As usual, we use analogous notations for strict heaps.

Lemma 2.15. The generating functions counting heaps of base included in S marked with a piece at position q is given by:

H (q) [S] (t) = H [S] (t)H {q} (t) if q ∈ S, H [S] (t) -V q [S] (t) H {q} (t) otherwise; H (q) [S] (t) = 1 1 + t H [S] (t)H {q} (t) if q ∈ S, H [S] (t) -V q
[S] (t) H {q} (t) otherwise. Proof. Let (H, x) be a heap with a marked piece at position q. We use the bijection F ↑ to turn it into a factorized heap (H 1 • H 2 ). We know that H 2 has base {q}, and that H 1 • H 2 has base included in S. According to Lemma 2.8, we have:

b(H 1 • H 2 ) = b(H 1 ) ∪ {q} \ v(H 1 ) .
If q is in S, this simply means that b(H 1 ) is included in S; if not, it means that q must be in v(H 1 ) as well, so that H 1 must not avoid q. We thus get the result for general heaps.

Let

H (q) *
[S] (t) be the generating function of almost strict marked heaps, with exactly one marked piece at position q. The bijection F ↑ turns these heaps into almost strict factorized heaps, on which we apply the same reasoning. Moreover, as only one piece may be duplicated, we have the identity:

H (q) * [S] (t) = (1 + t)H (q)
[S] (t). This yields the second formula.

Directed animals and heaps of dominoes

Definitions

Definition 3.1. Let Q be either a subset of Z or of the form Z/mZ with m an even number. The square lattice over Q, denoted by Γ Q , is the oriented graph with vertices (q, i) ∈ Q×N such that q +i is even, and edges (q, i) → (q +1, i+1) and (q, i) → (q -1, i + 1). The triangular lattice over Q, denoted by ∆ Q , is Γ Q with additionnal edges (q, i) → (q, i + 2). Definition 3.2. Let Q be a subset or quotient of Z in the same conditions as above. Let C be the relation defined by (q, q ′ ) ∈ C if and only if |q -q ′ | ≤ 1. The model of heaps (Q, C) is called the model of heaps of dominoes with set of positions Q.

Up to a translation, there are four kinds of models and associated lattices:

• the full model is the model Q = Z; • the half model is the model Q = N; • the cylindrical model of width m is the model Q = Z/mZ, with m even; • the rectangular model of width m is the model Q = {0, . . . , m -1}.
As seen in Figure 7, directed animals of source S on the square lattice Γ Q are identical to strict heaps of dominoes of base S in the model (Q, C), while directed animals on the triangular lattice ∆ Q are inflated heaps.

We say that a heap H of dominoes is aligned if all its pieces (q, i) are such that q + i is even. In particular, all heaps and inflated heaps corresponding to directed animals are aligned. Let Γ Q be a square lattice and ∆ Q its associated triangular lattice; let S be a one-line source, i.e., a set of vertices of the form (q, 0). We denote by A S (t) and A S (t) the generating functions of animals of source S in the lattices Γ Q and ∆ Q , respectively. These two generating functions also count strict and inflated heaps of base S in the model of heaps of dominoes Q.

In this section, we give means to compute A S (t); the generating function A S (t) is then given by performing the substitution t → t 1+t . Of course, we compute in the same way the generating functions A [S] (t) and A [S] (t) of animals with a source included in S.

Bounded lattices

The bounded lattices correspond to finite models of heaps of dominoes, that is, the cylindrical models and the rectangular models. Let Q be a finite model and S be a set of positions. The identity (6) and Lemma 2.3 give the value of the generating function of heaps of base S:

A S (t) = t |S| T [Q v(S)] (t) T [Q] (t) .
All we need is therefore to compute the generating functions of trivial heaps. Do do this, we define two sequences of polynomials.

Definition 3.3. Define the sequences (F m (t)) m≥0 and ( F m (t)) m≥2 of polyno- mials by F 0 (t) = 1, F 1 (t) = 1 -t,
and for all m ≥ 2:

F m (t) = F m-1 (t) -tF m-2 (t); F m (t) = F m-1 (t) -tF m-3 (t).
The polynomials F m (t) are often called the Fibonacci polynomials. With these polynomials, we can compute the generating function T [S] (t), in any finite model Q and for any set S, using the two lemmas below. We state them without proof, and refer to [START_REF] Viennot | Heaps of pieces. I. Basic definitions and combinatorial lemmas[END_REF] for more detail. Examples are also given in Section 6.

T [S] (t) = F |S1| (t) • • • F |S k | (t).
We now give explicit formulae for the special case S = {0}. In the following, we call zero-source animals the animals of source {0, 0} in any model. Let A m (t) and D m (t) be the generating functions of zero-source animals in the cylindrical and rectangular triangular lattices of width m, respectively. We have:

A m (t) = F m-1 (t) F m (t) -1; (7)
D m (t) = F m-1 (t) F m (t) -1. ( 8
)
The generating functions A m (t) and D m (t) counting zero-source animals on the square lattices are derived by performing the substitution t → t 1+t .

Unbounded lattices

We now address the unbounded lattices, i.e. the full and half lattices. We start with zero-source animals, defined above, which are simplest. In the rectangular and half models, such animals are also called half-animals.

Definition 3.6. Let A(t) and D(t) be the generating functions of zero-source animals on the full square lattice and the half square lattice, respectively. Let A(t) and D(t) be their counterparts on the triangular lattices.

These four generating functions are given below (see [START_REF] Dhar | Equivalence of the two-dimensional directed-site animal problem to Baxter's hard-square lattice-gas model[END_REF][START_REF] Gouyou-Beauchamps | Equivalence of the twodimensional directed animal problem to a one-dimensional path problem[END_REF][START_REF] Bétréma | Modèles avec particules dures, animaux dirigés et séries en variables partiellement commutatives[END_REF]):

Proposition 3.7. The generating functions of zero-source animals on the infinite models are:

A(t) = 1 2 1 √ 1 -4t -1 ; (9)
D(t) = 1 - √ 1 -4t 2t -1; (10)
A(t) = 1 2 1 + t 1 -3t -1 ; ( 11
)
D(t) = 1 -t -(1 + t)(1 -3t) 2t . ( 12
)
Of course, as usual, the generating functions counting animals on the square lattices can be obtained by performing the substitution t → t 1+t in the ones counting animals on the triangular lattices. Definition 3.8. In the full model, a compact source is a finite set of consecutive even positions. In the half model, a compact source is a finite set of consecutive even positions, starting at 0. The next result gives the generating function of animals with a given compact source. The proof may be found in [START_REF] Bétréma | Modèles avec particules dures, animaux dirigés et séries en variables partiellement commutatives[END_REF]. Proposition 3.9. Let C be a compact source with k sites. The generating function of animals of source C on the full triangular lattice is:

A C (t) = D(t) k-1 A(t).
On the half lattice, this generating function is:

A C (t) = D(t) k .
Remark. From this, it can be proved that the number of animals of area n with any compact source on the triangular lattice is 4 n-1 , and 3 n-1 on the square lattice. See [START_REF] Gouyou-Beauchamps | Equivalence of the twodimensional directed animal problem to a one-dimensional path problem[END_REF][START_REF] Bétréma | Modèles avec particules dures, animaux dirigés et séries en variables partiellement commutatives[END_REF].

Finally, we are able to compute the generating function of animals with an arbitrary source S. Proposition 3.10. Let Q = Z or N. Let S ⊆ Q be a one-line source and C be the smallest compact source containing S. The generating function of animals of source S in ∆ Q is:

A S (t) = t |S|-|C| T [v(C) v(S)] (t)A C (t).
Proof. Let us address the full lattice. Let Q m be a cylindrical model large enough so that C ⊆ Q m . The generating function of heaps of base S in the model Q m is:

A S,m (t) = t |S| T [Qm v(S)] (t) T [Qm] (t) .
As C is the smallest compact source containing S, v(C) is also the smallest interval containing v(S), which ensures that no position of Q m \ v(C) can be concurrent to v(C) \ v(S). Therefore, Lemma 3.5 entails that:

T [Qm v(S)] (t) = T [v(C) v(S)] (t)T [Qm v(C)] (t),
and thus:

A S,m (t) = t |S|-|C| T [v(C) v(S)] (t)A C,m (t).
We conclude by letting m tend to infinity.

In the case of the half-lattice, we repeat the same reasoning, this time taking for Q m a rectangular model large enough so that C ⊆ Q m .

Average number of adjacent sites, loops and neighbours of directed animals 4.1 Notations and results

In this section, Γ is a square lattice (full, half, cylindrical or rectangular), and S is a one-line source of Γ. In Section 3, we have computed the generating functions A S (t) and A [S] (t) counting directed animals on Γ of source S and with a source included in S.

We are now interested in three parameters of the directed animals: number of adjacent sites, number of loops, and site perimeter. The first two are defined in Section 1; we denote by j(A) and ℓ(A) the number of pairs of adjacent sites and number of loops of the animal A, respectively. Definition 4.1. Let A be an animal on Γ with a source included in S. An S-neighbour of A is a vertex v of Γ not in A such that A ∪ {v} is still a directed animal with a source included in S.

Assume now that the graph Γ is embedded in a larger graph Γ ′ . An internal S-neighbour of A is an S-neighbour of A seen as an animal on Γ. An external S-neighbour of A is an S-neighbour of A seen as an animal on Γ ′ .

Finally, a vertex of Γ is at the edge of the lattice if it has outdegree 1.

For the purpose of this definition, we regard the half-lattice and the rectangular lattices as embedded in the full lattice. The full and cylindrical lattices are not naturally embedded in any larger graph, so in these lattices internal and external neighbours are identical. Moreover, if S is the source of A, the S-neighbours of A coincide with the usual neighbours of A, as defined in Section 1.

Assuming no ambiguity on the set S, we denote by p i (A) the number of internal S-neighbours of A (or internal site perimeter) and by p e (A) its number of external S-neighbours (or external site perimeter). We also denote by e(A) the number of sites of A at the edge of the lattice Γ.

The generating functions defined below are linked to the average value of each parameter in animals of a given area.

Definition 4.2. Define the following generating functions, counting animals with a source included in S:

• Let J [S] (t) be the generating function of animals marked with two adjacent sites.

• Let L [S] (t) be the generating function of animals marked with a loop.

• Let P e [S] (t) be the generating function of animals marked with an external S-neighbour.

• Let P i

[S] (t) be the generating function of animals marked with an internal S-neighbour. Also define J S (t), L S (t), P e S (t) and P i S (t) the analogous generating functions of animals of source S.

To compute these generating functions, we again use the correspondence between animals and heaps of dominoes. We denote by (Q, C) the model of heaps of dominoes associated with the lattice Γ; we also denote by S the aligned set of positions associated to the source S.

We now define some generating functions counting heaps. As usual, a generating function with a subscript [S] counts heaps with a base included in S, and one with a subscript S counts heaps with base S, so this precision will often be omitted from the definition.

In some cases, we consider heaps having a minimal piece outside S; we call such a piece an illegal minimal piece. Note that an illegal minimal piece does not have to be aligned with S.

Definition 4.3. Define the following generating functions:

• Let M [S] (t) be the generating function of strict heaps marked with a piece at a position q, such that q + 2 is in Q.

• If q is in S, let W q [S] (t) be the generating function of strict heaps with a minimal piece at position q and an illegal minimal piece at q + 2. Let W [S] (t) be the sum of W q

[S] (t) over all q ∈ S such that q + 2 ∈ S. • Let E [S] (t) be the generating function of strict heaps marked with a piece at a position q, such that either q -1 or q + 1 is not in Q.

Also define the analogues M S (t), W S (t) and E S (t); thus, W S (t) is the generating functions of strict heaps of base S ∪ {q + 2}, such that q is in S but q + 2 is not.

We now show that these generating functions can be computed using previous results. First, we have:

W [S] (t) = q∈S q+2 ∈S T ⊆S q∈T A T ∪{q+2} (t), (13)
where A T ∪{q+2} (t) counts strict heaps with base T ∪ {q + 2}, and is computed using the results of Section 3. Next, the generating function of strict heaps with base included in S marked with a single piece is tA ′ [S] (t). Thus, we have:

M [S] (t) = tA ′ [S] (t) - q+2 ∈Q A (q)
[S] (t); ( 14)

E [S] (t) = q-1 ∈Q or q+1 ∈Q A (q) [S] (t), (15)
where A (q)

[S] (t) counts strict heaps with base included in S marked with a piece at position q and is computed using Lemma 2.15. In all three equations, the sum goes over a finite number of positions q, which ensures that all three generating functions can be computed. In this regard, the full and cylindrical models are the simplest, as

M [S] (t) is equal to tA ′ [S] (t) and E [S] (t) is zero.
Theorem 4.4. In square lattices, the generating functions counting the total number of adjacent pieces, loops and site perimeters of the animals with source included in S are given by:

J [S] (t) = tM [S] (t) -W [S] (
P i S (t) = P e S (t) -E S (t), ( 23
)
where j(S) denotes the number of pairs of adjacent sites in the source S.

Applications of this theorem are given in Section 6.

Site perimeters

We first prove the four identities (18), ( 19), ( 22) and ( 23) dealing with the internal and external site perimeter. First, we remark that a vertex (q, i) of Γ has outdegree 1 if and only if either q -1 or q + 1 is not in Q. Thus, the generating function E [ S](t) satisfies:

E [S] (t) = A e(A)t |A| , ( 24
)
where the sum goes over all animals of source included in S. The same goes for the generating function E S (t).

Lemma 4.5. The number of external and internal S-neighbours of every directed animal A with source included in S satisfy:

p e (A) = |S| + |A| -j(A); p i (A) = p e (A) -e(A).
By summing the identities of this lemma over all animals of source included in S, and using (24), we prove the identities (18) and (19). By summing them over all animals of source S, we get ( 22) and (23).

Proof. When dealing with the external site perimeter, the lattice Γ is embedded in a lattice Γ ′ which is either the full lattice or a cylindrical lattice. Let Z be the number of pairs of vertices (v, w) such that v is a site of A and w is a child of v (i.e., v → w is an edge of Γ ′ ), whether in A or not. As every vertex has outdegree 2, we have Z = 2|A|. Now, as A is a directed animal, a child of a site of A is either a site of A or an external S-neighbour of A. The only sites and S-neighbours of A not counted are the ones in S; moreover, two sites have a child in common if and only if they are adjacent. Hence:

Z = |A| + p e (A) + j(A) -|S|,
which yields the announced formula for p e (A).

If Γ is either the half-lattice or a rectangular lattice, then each site on the edge of the lattice has one external neighbour not in Γ. Thus, we have:

p e (A) = p i (A) + e(A).

Average number of adjacent sites and loops

To prove the remaining identities of Theorem 4.4, dealing with the number of adjacent sites and loops, we use several bijections between various sets of heaps marked with certain pieces. Rather than strict marked heaps, it is convenient here to use almost strict marked heaps (see Definition 2.11).

Although the proof seems complicated due to the high number of sets and associated generating functions that we must consider, each bijection is actually very simple, consisting in adding/removing a single piece.

Each of these sets of heaps is illustrated in Figures 8 and9 with the relevant bijections. Definition 4.6. Define the following sets of almost strict marked heaps, assumed to have a base included in S:

• Let J * [S]
be the set of almost strict heaps marked with two adjacent pieces.

• Let L *

[S] be the set of almost strict heaps marked with the top piece of a loop.

• Let M *

[S] be the set of almost strict heaps marked with a piece at a position q, such that q + 2 is in Q.

• Let W *

[S] be the set of almost strict heaps marked with a minimal piece at a position q, and having an illegal minimal piece at position q + 2.

• Let I 2 * [S] (resp. I 3 * [S]
) be the set of almost strict heaps marked with two independent pieces at positions q and q + 2 (resp. q + 3).

• Let X 2 * [S] (resp. X 3 * [S]
) be the set of almost strict heaps marked with a piece x at a position q, and having an illegal minimal piece at position q + 2 (resp. q + 3) independent from x.

Let J * [S] (t), L * [S] (t), M * [S] (t), W * [S] (t), I 2 * [S] (t), I 3 * [S] , X 2 * [S] , X 3 *
[S] (t) be the generating functions of these sets.

The asterisks * are used above to denote sets of almost strict marked heaps; we link these heaps to strict marked heaps later. Note that we have the inclusions

J * [S] ⊆ I 2 * [S] and W * [S] ⊆ X 2 * [S]
. Lemma 4.7. The following identity holds:

L * [S] (t) = tJ * [S] (t).
Proof. To prove this result, we use a first bijection, which removes exactly one piece:

Φ 0 : L * [S] → J * [S] . Let (H, {x}) be a heap of L * [S]
. Pull the marked piece x downwards to form the factorized heap (

H 1 • H 2 ) = F ↓ (H, {x}), such that x is the only maximal piece of H 1 . Let H 1 = H ′ 1 • x and H ′ = H ′ 1 • H 2 .
As x is a loop, the heap H ′ 1 has two maximal pieces y and z, which are adjacent (see Figure 8, left). Moreover, as H 1 and H ′ 1 have same base and neighbourhood, Lemma 2.8 guarantees that H and H ′ have the same base. We may thus set:

Φ 0 H, {x} = H ′ , {y, z} .
This operation is easily reversible, by putting back the piece x.

Lemma 4.8. The following identity holds:

I 2 * [S] (t) -J * [S] (t) = tI 3 * [S] (t).
Proof. We again prove this result with a bijection removing one piece:

Φ 1 : I 2 * [S] \ J * [S] → I 3 * [S] ,
Let (H, {x, y}) be a heap of

I 2 * [S] \ J * [S]
. We set (H 1 • H 2 ) = F ↓ (H, {x, y}), pulling the pieces x and y downwards.

As the pieces x and y are not adjacent, one of them (say, x) is higher than the other. Let

H 1 = H ′ 1 • x.
As H 1 is strict, H ′ 1 must have a second maximal piece z, such that the positions of y and z are at distance 3 (Figure 8, middle). Let

H ′ = H ′ 1 • H 2 .
As H 1 and H ′ 1 have same base and neighbourhood, we may set:

Φ 1 (H, {x, y}) = (H ′ , {y, z}).
This operation is reversible: let (H ′ , {y, z}) be a heap of

I 3 * [S] , and let (H ′ 1 •H 2 ) = F ↓ (H ′ , {y, z}).
As the set of positions S is aligned, the heap H ′ 1 is also aligned. Therefore, y and z cannot be at the same height; say, z is higher. We set

H 1 = H ′ 1 •
x so that x sits on z and the positions of x and y are at distance 2, and H = H 1 • H 2 ; thus, we have Φ 1 (H, {x, y}) = (H ′ , {y, z}). Lemma 4.9. The following identity holds:

X 2 * [S] (t) -W * [S] (t) = tX 3 * [S] (t).
The generating function W T (t) may be found in Definition 4.3.

Proof. We use another bijection removing one piece:

Φ 2 : X 2 * [S] \ W * [S] → X 3 * [S] ,
Let (H, {x}) be a heap of

X 2 * [S] \ W * [S]
, and let y be the illegal minimal piece of H. We pull the pieces x and y downwards, forming the factorized heap (H 1 • H 2 ). As x is not a minimal piece of H 1 , it must sit on another piece z, at position q -1 (Figure 8, right). Let

H 1 = H ′ 1 • x and H ′ = H ′ 1 • H 2 . Again, H 1 and H ′ 1
have the same base and neighbourhood, so that y is still the only illegal minimal piece of H ′ . We set:

Φ 2 H, {x} = H ′ , {z} .
This operation is easily reversible by putting back the piece x.

x H1 y z

H ′ 1 x y H1 z y H ′ 1 y x H1 y z H ′ 1 x y H1 z y H ′ 1 L * [S] I 2 * [S] \ J * [S] X 2 * [S] \ W * [S]
J *

[S]

I 3 * [S] X 3 * [S]
Figure 8: On the left, the bijection Φ0: removing the piece x uncovers two adjacent pieces y and z. In the middle, the bijection Φ1: removing the piece x uncovers a piece z, with position at distance 3 from y and higher than y. On the right, the bijection Φ2, with the illegal minimal piece y colored gray. Removing the piece x uncovers a piece z, with position at distance 3 from y.

Lemma 4.10. The following identity holds:

I 2 * [S] (t) + X 2 * [S] (t) = t M * [S] (t) + I 3 * [S] (t) + X 3 * [S] (t) .

20

Proof. We use a fourth and final bijection removing one piece:

Φ 3 : I 2 * [S] ∪ X 2 * [S] → M * [S] ∪ I 3 * [S] ∪ X 3 * [S] .
In this proof, if x is a piece, we write x + to denote the highest piece of the stack of x, and x -to denote the lowest piece in the stack of x (see Section 2.4).

Let H be a heap of

I 2 * [S] or X 2 * [S]
. In the first case, let x be the left-hand marked piece, and y the right-hand one. In the second, let x be the marked piece and y the illegal maximal piece. In both cases, we set (H 1 , H 2 ) = F ↑ (H, {x, y}), pushing upwards the pieces x + and y + . Now, let

H 2 = y + • H ′ 2 and H ′ = H 1 • H ′ 2 .
We distinguish three cases, illustrated in Figure 9: (a) The piece x + is the only minimal piece of

H ′ 2 : the heap (H ′ , {x}) is in M * [S] . (b) The heap H ′
2 has a minimal piece z at position q + 3, and z is not an illegal minimal piece of

H ′ : the heap (H ′ , {x, z -}) is in I 3 * [S] . (c) The heap H ′
2 has a minimal piece z at position q + 3, and z is an illegal minimal piece of

H ′ : the heap (H ′ , {x}) is in X 3 * [S] .
Once again, this operation is easily reversible by putting back the piece y + and checking whether it is an illegal minimal piece.

x+ y+ H2 I 2 * [S]
x+ y+ H2

X 2 * [S] x+ H ′ 2 M * [S] x+ z H ′ 2 I 3 * [S] x+ z H ′ 2 X 3 * [S]
Figure 9: The bijection Φ3; illegal minimal pieces are colored gray. After removing the piece y + , either a new minimal piece z of H2 is uncovered at position 3 or not. If it is, the heap H ′ may be in

I 3 * [S] or X 3 * [S]
, depending on whether z is an illegal minimal piece. If not, the heap

H ′ is in M * [S] .
Finally, to prove the identity (20), we need a last lemma, given below.

Lemma 4.11. The following identity holds:

W [S] (t) = T ⊆S W T (t) -j(T )A T (t) .
Proof. Consider the generating function:

T ⊆S W T (t).
We write W T (t) as the sum of all W q T (t), for q ∈ T and q + 2 ∈ T . We then split the sum according to whether q + 2 is in S or not:

T ⊆S W T (t) = T ⊆S q∈T q+2 / ∈S W q T (t) + T ⊆S q∈T q+2 / ∈T q+2∈S W q T (t) .
In the first term of the right-hand side of this equation, we recognize the generating function W [S] (t). We rewrite the second term using the fact that W q T (t) = A T ∪{q+2} (t) and by posing T ′ = T ∪ {q + 2}:

T ⊆S W T (t) = W [S] (t) + T ′ ⊆S q∈T ′ q+2∈T ′ A T ′ (t) ; = W [S] (t) + T ′ ⊆S j(T ′ )A T ′ (t).
The lemma follows.

With the above lemmas, we are now able to prove the theorem.

Proof of Theorem 4.4. The identities (18), (19), ( 22) and (23) dealing with the site perimeters are proved in Section 4.2.

To prove the remaining identities, we first link the generating function counting almost strict marked heaps with the ones counting strict marked heaps. As each marked piece accounts for a 1 + t factor, we have:

J * [S] (t) = (1 + t) 2 J [S] (t); L * [S] (t) = (1 + t)L [S] (t); M * [S] (t) = (1 + t)M [S] (t); W * [S] (t) = (1 + t)W [S] (t).
Moreover, putting together the identities of Lemmas 4.7, 4.8, 4.9 and 4.10, we find:

L * [S] (t) = tJ * [S] (t); J * [S] (t) = tM * [S] (t) -W * [S] (t).
Thus, we derive the first two identities of the theorem, ( 16) and (17).

To prove the identities dealing with animals of source S, we remark that the generating function J [S] (t) verifies:

J [S] (t) = T ⊆S J T (t).
The generating functions L [S] (t) and M [S] (t) also behave in this manner. Using the inclusion-exclusion principle, this means that the equation ( 21) giving L S (t) is a consequence of (17).

To address the generating function W [S] (t), we use Lemma 4.11, rewriting (16) as:

T ⊆S J T (t) - tM T (t) + j(T )A T (t) -W T (t) 1 + t = 0.
The identity (20) is then derived using the inclusion-exclusion principle.

Triangular lattices

Let ∆ be the triangular lattice corresponding to Γ. A number of our results on the animals of Γ have counterparts on the animals of ∆. The results and proofs are very similar, and we go into slightly less detail. Given an animal A on ∆, we define its number j(A) of adjacent sites and its number ℓ(A) of loops. In this paper, a loop is still defined by two adjacent sites capped by another site. Note that this definition is different from the one used by Bousquet-Mélou [START_REF] Bousquet-Méelou | New enumerative results on two-dimensional directed animals[END_REF], who found similar results.

With our methods, we have been unable to address the site perimeter, which is not surprising as the generating function of animals marked with a neighbour is believed to be non-algebraic on the unbounded lattices [START_REF] Conway | Some exact results for moments of 2D directed animals[END_REF]. The best we could do is to compute bounds on the perimeter, using manipulations similar to Lemma 4.5, although we do not give further details in this paper.

As on the square lattice, we begin by defining generating functions, which are analogues to the ones of Definitions 4.2, 4.3 and 4.6. Definition 4.12. Let S ⊆ Q be an aligned set of positions. Define the following generating functions, counting animals with a source included in S (or inflated heaps with base included in S):

• J [S] (t) and L [S] (t), the generating functions of animals with a source included in S, marked respectively with two adjacent sites and a loop;

• M [S] (t) the generating function of inflated heaps marked with a piece at a position q such that q + 2 ∈ S;

• W [S] (t) the generating function of inflated heaps with a minimal piece at position q and an illegal minimal piece at position q + 2;

• I 2 [S] (t) (resp. I 3 [S] (t)) the generating function of inflated heaps marked with two independent pieces at positions q and q + 2 (resp. q and q + 3). Also let J S (t), L S (t), M S (t) and W S (t) be the analogous generating functions counting animals of source S and heaps of base S. Theorem 4.13. The generating functions counting the total number of adjacent sites and loops of animals of a given area on the triangular lattice are:

J [S] (t) = tM [S] (t) -W [S] (t) 1 + t ; (25) L [S] (t) = tJ [S] (t); (26)
J S (t) = tM S (t) + j(S)A S (t) -W S (t) 1 + t ; (27) L S (t) = tJ S (t). ( 28
)
To prove this theorem, we use the results of Section 4.3, along with an additional bijection.

Lemma 4.14. The following identity holds:

I 2 [S] (t) -J [S] (t) = t 1 -t 2J [S] (t) + I 3 [S] (t) .
Proof. We use a bijection Ψ, analogue to Φ 1 (see Lemma 4.8) and illustrated in Figure 10. Let (H, {x, y}) be a marked inflated heap, such that x and y are independent, with positions at distance 2, and not at the same height (say, x is higher). We use the bijection F ↓ to form a factorized heap (H 1 • H 2 ). We then remove from H 1 all pieces of the stack of x that are higher than y, thus forming the heap H ′ 1 . There are two possiblities:

(a) H ′ 1 has two maximal pieces, y and z, which are adjacent; (b) H ′ 1 has two maximal pieces, y and z, with positions at distance 3.

The inverse bijection is done by putting back the stack of x, which can have an arbitrary number of pieces. In case (b), as the inflated heap H ′ 1 is aligned, the pieces y and z cannot be at the same height. Therefore, z must be the higher maximal piece. In case (a), however, z can be either the left maximal piece or the right, leading to the factor 2 on the term J [S] (t).

Proof of Theorem 4.13. First, we derive the identities (26) and (28) dealing with loops, using a method identical to the proof of Lemma 4.7. When dealing with general heaps, there is no 1 + t factor due to the duplication of marked pieces.

We now prove the identity (25). Let (H, {x}) be a heap counted by M [S] (t). We use the bijection F ↓ to pull downwards the piece x, creating a factorized heap. We remark that such factorized heaps may be built by replacing each piece of an almost strict factorized heap by an arbitrary stack, leading to the link:

M [S] (t) = M * [S] t 1 -t . x y H1 z y H ′ 1 y x H1 y z H ′ 1 z y H ′ 1 y z H ′ 1 I 2 [S] (t) -J [S] (t) I 3 [S] (t) J [S] (t) J [S] (t)
Figure 10: The bijection Ψ: we remove all pieces of the stack of x which are higher than y. This uncovers a piece z, either adjacent with y or with a position at distance 3 and higher than y.

The generating functions I 2 [S] (t) and I 3 [S] (t) are also given in this manner. As W [S] (t), it satisfies:

W [S] (t) = W [S] t 1 -t = (1 -t)W * [S] t 1 -t .
Taking the identities of Lemmas 4.9 and 4.10 together and performing the substitution t → t 1-t , we thus find:

I 2 [S] (t) + W [S] (t) = t 1 -t M [S] (t) + I 3 [S] (t) .
Using now Lemma 4.14, this boils down to (25). Performing the same substitution on the identity of Lemma 4.11 yields:

W [S] (t) = T ⊆S W T (t) -j(T )A T (t) .
The last identity (27) is thus derived using an inclusion-exclusion argument.

5 Asymptotic results

Animals according to area

Here, we derive asymptotic estimates from the results of Section 3. First, consider the polynomials F m (t) and F m (t), defined in Definition 3.3. Let ρ m and σ m be their respective smallest root.

Lemma 5.1. For all m ≥ 0, the polynomials F m (t) and F m (t) have only real, simple roots. Their smallest roots ρ m and σ m verify:

1 ρ m = 4 cos 2 π m + 2 ; 1 σ m = 4 cos 2 π 2m .
Proof. We check by induction on m that the degrees of F m (t) and F m (t) are m 2 and m 2 , respectively. We also check by induction the following identities:

F m 1 4 cos 2 θ = sin[(m + 2)θ] (2 cos θ) m+1 sin θ ; F m 1 4 cos 2 θ = 2 cos(mθ) (2 cos θ) m .
By choosing appropriate values of θ in the interval [0, π/2), these identities account for all the roots of the polynomials. Thus, we prove that the roots are real and simple, and we derive the value of the smallest root. Now, let Γ be a square lattice and ∆ be its associated triangular lattice; let S be a one-line source. We denote by a(n) and ā(n) the number of animals of area n of source S on the lattices Γ and ∆ respectively. The result below is simply obtained by performing singularity analysis [START_REF] Flajolet | Analytic combinatorics[END_REF] on the formulae of Section 3.

Proposition 5.2. The general form of the asymptotic behaviour of a(n) and ā(n) is:

a(n) ∼ λµ n n ν ; ā(n) ∼ λμ n n ν ,
where the constants μ and ν are:

• in the full lattice, μ = 4 and ν = -1/2;

• in the half lattice, μ = 4 and ν = -3/2;

• in the cylindrical lattice of width m, μ = 1/σ m and ν = 0;

• in the rectangular lattice of width m, μ = 1/ρ m and ν = 0.

Moreover, in each case, µ is equal to μ -1 and λ and λ depend on the source S.

Notably, changing the source S only changes the behaviour of a(n) and ā(n) by a multiplicative constant.

Average number of adjacent sites and loops and average perimeter

Let now j(n) be the average number of adjacent sites in the animals of source S and area n in the lattice Γ. Let ℓ(n), p e (n), p i (n) be their average number of loops, external perimeter, and internal perimeter; let (n) and l(n) be the analogous quantities in the lattice ∆.

Corollary 5.3. Assume that Γ is either the full lattice, the half lattice, or a cylindrical bounded lattice. As n tends to infinity, we have the following estimates:

j(n) ∼ n µ + 1 ; (n) ∼ n μ + 1 ; ℓ(n) ∼ n µ 2 ; l(n) ∼ n μ(μ + 1)
;

p i (n) ∼ p e (n) ∼ µ µ + 1 n.
In the unbounded lattices, the growth constants are μ = 4 and µ = 3. Thus, these estimates become:

j(n) ∼ n 4 ; ℓ(n) ∼ n 9 ; p(n) ∼ 3n 4 ; (n) ∼ n 5 ; l(n) ∼ n 20 .
Proof. Let us begin with the number of adjacent pieces in the square lattice. This number is given by the identity (20):

J S (t) = tM S (t) + j(S)A S (t) -W S (t) 1 + t ,
where the generating functions are defined in Definitions 4.2 and 4.3. We examine the coefficients of these generating functions.

• The nth coefficient of J S (t) is j(n)a(n).

• As, in the full, half, and cylindrical models, the position q + 2 is always in Q as soon as q is, the generating function M S (t) simply counts animals marked with any site; its nth coefficient is na(n).

• As a corollary to Proposition 5.2, the nth coefficient of both A S (t) and W S (t) is O a(n) .

From this, it follows that the dominant term in the right-hand side is that of M S (t). We perform singularity analysis, letting t tend to the singularity 1/µ. We obtain, as n tends to infinity:

j(n)a(n) ∼ 1/µ 1 + 1/µ na(n).
The result follows; the other estimates are obtained with a similar analysis on the equations of Theorems 4.4 and 4.13.

Compact-source animals on the full lattice

As an illustration of how to deal with non-single source animals, we consider animals with any compact source (see Definition 3.8). Recall that the number of such animals of area n is 3 n-1 on the square full lattice, so that the generating function is:

A c (t) = t 1 -3t .
We only give the result for the number of adjacent sites of animals on the square full lattice, but other configurations can be handled similarly.

Corollary 6.3. The generating function counting the total number of adjacent sites of the compact-source directed animals on the full square lattice is:

J c (t) = 1 2 1 -2t √ 1 + t(1 -3t) 3/2 - 1 -3t -2t 2 (1 + t)(1 -3t) 2 .
Proof. Let C be a compact source with k sites. The generating function A C (t) is, according to Proposition 3.9:

A C (t) = D(t) k-1 A(t).
Moreover, M C (t) is simply equal to tA ′ C (t), j(C) is k -1, and W C (t) counts animals with a compact source with k + 1 sites, and is thus equal to D(t)A C (t). Therefore:

J C (t) = t 2 A ′ C (t) + (k -1)A C (t) -D(t)A C (t) 1 + t .
We sum this identity for all k ≥ 0:

J c (t) = 1 1 + t t 2 A ′ c (t) +

A(t)D(t)

1 -D(t) 2 -D(t)A c (t) .

This completes the proof.

Half-animals on the square rectangular lattices

Finally, we present our results on the external and internal site perimeter of half-animals (that is, animals of source {0}) on the square rectangular lattices. The former was the object of a conjecture by Le Borgne [START_REF] Borgne | Conjectures for the first perimeter moment of directed animals[END_REF]; from our formula, one can prove this conjecture. We denote by D m (t) the generating function of half-animals in square rectangular lattice of width m. Corollary 6.4. The generating functions giving the total external and internal site perimeter of half-animals on the square rectangular lattice of width m are: Proof. Let Q be the rectangular model {0, . . . , m-1} of width m. By symmetry, instead of considering animals with a source at position 0, we consider them to have a source at position m -1. This does not change the site perimeter of the animals.

P e m (t
The generating functions P e m (t) ≡ P e {m-1} (t) and P i m (t) ≡ P i {m-1} (t) are given by ( 22) and ( 23), which in turn require us to compute the generating function J {m-1} (t). The number j({m -1}) is again zero; moreover, as the position m+ 1 is not in Q, W {m-1} (t) is also zero. Thus, all we need to compute are the generating functions M {m-1} (t) and E {m-1} (t).

Let D (q) m (t) be the generating function of half-animals marked with a site at position q. Using Definition 4.2, we find: Finally, we derive the generating functions D (q) m (t) using Lemma 2.15; in the notations of this lemma, D (q) m (t) is equal to H (q)

[{m-1}] (t) as a marked heap cannot be empty. We must compute the following generating functions:

• H {m-1} (t) and H {0} (t) are both equal to D m (t) by symmetry;

• the only heap of base included in {m -1} avoiding m -2 is the empty heap, so that V m-2 [{m-1}] (t) = 1; • as a strict pyramid of base m -1 is either a single piece or a piece topped by a pyramid of base m -2, we have H {m-2} (t) = Dm(t) t -1;

• as a pyramid of base m -1 avoiding 0 lives in the model {2, . . . , m -1}, which has m -2 positions, we have V 0 [{m-1}] (t) = 1 + D m-2 (t). From this, we find:

D (m-1) m (t) = 1 1 + t 1 + D m (t) D m (t); D (m-2) m (t) = 1 1 + t D m (t) D m (t) t -1 ; D (0) m (t) = 1 1 + t D m (t) -D m-2 (t) D m (t).
Injecting these values into (20), ( 22) and (23), we get the announced results.

Figure 1 :

 1 Figure 1: Single-source directed animals on the square, triangular and honeycomb lattices. All edges point upwards.

1

 1

Figure 2 :

 2 Figure 2: A directed animal on the square lattice can be turned into a heap by replacing each site by a 2×1 domino.

Figure 3 :

 3 Figure 3: A directed animal on the square lattice with two adjacent sites, a loop, and a neighbour marked.

Figure 4 :

 4 Figure 4: By replacing each piece of a strict heap by a stack of pieces, one gets a general heap; by inflating each stack, one gets an inflated heap.

Figure 5 :

 5 Figure 5: The product of two heaps is obtained by dropping the second heap on top of the first.

Figure 6 :

 6 Figure 6: A marked heap and an almost strict marked heap (left), their image by F ↓ and F ↓ (middle) and by F ↑ and F ↑ (right).

Figure 7 :

 7 Figure 7: An animal on the square cylindrical lattice of width 6 and the triangular rectangular lattice of width 5, and their corresponding heaps of dominoes.

Lemma 3 . 4 .

 34 Let m ≥ 0. The generating function T [Q] (t) of trivial heaps in the rectangular model of width m is F m (t). If m is even, the generating function of trivial heaps in the cylindrical model of width m is F m (t). Lemma 3.5. Let S be a finite set of positions; write S = S 1 ∪ • • • ∪ S k , where the S i are intervals of Z, with k minimal. The generating function of trivial heaps included in S is:

M

  {m-1} (t) = tD ′ m (t) -D (m-1)

E

  {m-1} (t) = D (m-1) m (t) + D (0) m (t).

  ) = D m (t) + D m (t) -D m-2 (t) ,where the generating function D m (t) is derived from[START_REF] Gouyou-Beauchamps | Equivalence of the twodimensional directed animal problem to a one-dimensional path problem[END_REF].29By letting m tend to infinity, we obtain the generating functions of animals on the half lattice:

	P i m (t) =	t 1 + t	t 1 + t D m (t) + D m (t) P e (t) = D(t) + D ′ m (t) + 1 1 + t D m (t) 2 ; t 1 + t D ′ m (t) -1 1 + t t 1 + t D ′ (t) + 1 1 + t P i (t) = t 1 + t D(t) + t 1 + t D ′ (t).	D(t) 2 ;

For the sake of clarity, all generating functions in this paper follow the same typographical pattern as Definitions

2.2 and 2.6: the generating functions of general (or inflated) heaps are denoted by calligraphic letters, while the ones of strict heaps are denoted by standard capital letters. Likewise, a subscript [S] is square brackets always indicates heaps with a base included in S, while a subscript S denotes heaps of base S.

Acknowledgments

I would like to thank Mireille Bousquet-Mélou for her precious help in the writing of this paper.

Examples

Single-source animals on the full lattice

We start with the simplest case, that of single-source animals on the full lattices. Corollary 6.1. The generating functions counting the total number of adjacent sites, number of loops and site perimeter of the single-source directed animals on the full square lattice are respectively given by:

The value of P (t) was conjectured by Conway [START_REF] Conway | Some exact results for moments of 2D directed animals[END_REF], and the value of L(t) was proved by Bousquet-Mélou using a gas model method [START_REF] Bousquet-Méelou | New enumerative results on two-dimensional directed animals[END_REF].

Proof. We use Theorem 4.4 to derive the generating functions. First, we use (20) to compute J(t) ≡ J {0} (t), which gives:

The generating function M {0} (t) is simply equal to tA ′ (t), j({0}) is zero, and W {0} (t) is equal to A {0,2} (t), in turn equal to D(t)A(t) using Proposition 3.9. This yields the announced formula; the other two generating functions follow from equations ( 21) and ( 22).

Similarly, Theorem 4.13 instantiates on single-source animals on the triangular full lattice. We omit the proof, which is identical to the square lattice case. Corollary 6.2. The generating functions counting the total number of adjacent sites and number of loops of single-source animals on the full triangular lattice are:

This time, the value of L(t) is different from the one found by Bousquet-Mélou [START_REF] Bousquet-Méelou | New enumerative results on two-dimensional directed animals[END_REF], who used a different definition of loops.


PhD Nanette Stroebele
email: nanette.stroebele@charite.de

Pia Dietze

Dr. med.; Peter Tinnemann

Prof Stefan N Willich

Assessing variety and pricing of selected foods in socioeconomic disparate districts of Berlin, Germany

Keywords: environment, fruit and vegetables, pricing, accessibility, variety Blinded

Aim: The neighbourhood environment appears to influence people's food consumption. Access, variety and pricing of foods play a role in the socioeconomic difference of fruit and vegetable consumption. This study compared differences in number of grocery stores, variety of fresh fruits and vegetables and food prices in districts with different Social Index (SI) in Berlin, Germany. Methods: The district with the lowest SIs was compared to the district with the highest SI. The number of grocery stores offering fresh produce, the variety of fresh fruits and vegetables, and prices of selected healthy and less healthy food items were assessed and compared. Results: The low SI district had more grocery stores per residents than the high SI district. Variety and prices of fruits and vegetables did not differ between the two districts but milk and whole wheat bread were less expensive in the high SI district. For all grocery stores, selected foods with higher energy density had lower energy costs than low energy density foods. Conclusion: Health inequalities in Germany might be less influenced by access to healthy foods than in other countries but nutrient rich foods such as fruits and vegetables have higher energy costs than high energy dense foods.

p. 5, 1st paragraph: The two areas Kreuzberg and Steglitz-Lankwitz are compared, but the population density is given for the three areas: Kreuzberg, Steglitz and Lankwitz. This is confusing and should be clarified.

-Official data only provides population density separately for Steglitz and Lankwitz but the authors hopefully clarified this confusion by calculating the mean for both areas. p. 5, 1st paragraph and p. 9, 3rd paragraph: information about the size of the two areas is inconsistent: p.5 ". roughly the same size. ", p. 9 ". size. differed." -The information regarding the size of the areas chosen was clarified. p. 5, 3rd paragraph: It should be explained in this paragraph why the variety of food items was determined only in non-organic food stores (compare p.6, 1st paragraph).

-A sentence explaining the reasons for choosing only non-organic food stores was added (p. 5, 3rd paragraph) p. 6, 1st paragraph: Which established criteria for the popularity for the chosen food products in the German population were used? -A reference was added. p. 7, 1st paragraph: ". framers´ markets. ", should use similar terms as of the rest of the text.

-For all markets, the expression "farmers' markets" was chosen.

p. 8, 2nd paragraph: The relationship between energy density and energy costs should be explained shortly in the part "results", only referring to the figure would not be sufficient.

-The results presented in figure 1 were explained in more details (p. 8, 2nd paragraph). p. 9, last paragraph and p. 11, 1st paragraph are identical.

-The last paragraph on page 9 was taken out.

Introduction

Unhealthy dietary behaviour, in particular the consumption of fruits and vegetables has been shown to be particularly low among socioeconomically disadvantaged populations [START_REF] Giskes | Socio-economic differences in fruit and vegetable consumption among Australian adolescents and adults[END_REF][START_REF] Hulshof | Socio-economic status, dietary intake and 10 y trends: the Dutch National Food Consumption Survey[END_REF]. A systematic review revealed that household income appears to be consistently positively related to fruit and vegetable intake [START_REF] Kamphuis | Environmental determinants of fruit and vegetable consumption among adults: a systematic review[END_REF]) and lower socioeconomic groups seem to be less likely to follow existing dietary guidelines [START_REF] Turrell | Socioeconomic differences in food purchasing behaviour and suggested implications for diet-related health promotion[END_REF].

Another factor that has been gaining attention recently is the possible influence of neighbourhood food environment. Recent studies from the U.S. suggest that residents of socioeconomically disadvantaged neighbourhoods have less access to affordable healthy food choices compared to high socioeconomic neighbourhoods [START_REF] Jetter | The availability and cost of healthier food alternatives[END_REF][START_REF] Hendrickson | Fruit and vegetable access in four low-income food deserts communities in Minnesota[END_REF][START_REF] Chung | Do the poor pay more for food? An analysis of grocery store availability and food price disparities[END_REF][START_REF] Moore | Associations of neighborhood characteristics with the location and type of food stores[END_REF][START_REF] Powell | Food store availability and neighborhood characteristics in the United States[END_REF]Zenk et al. 2009). Healthier food choices in deprived areas differ in their availability, variety and in price compared to healthier choices in less deprived areas. In deprived areas fewer variety of fresh fruits and vegetables is offered and fresh produce tend to be more expensive [START_REF] Hosler | Assessing retail fruit and vegetable availability in urban and rural underserved communities. Preventing Chronic Disease[END_REF]Zenk et al. 2005).

However, other studies show few or no differences in food prices, availability or access between deprived and affluent areas [START_REF] Cassady | Is price a barrier to eating more fruits and vegetables for low-income families?[END_REF]Smith et al. 2009;Winkler et al. 2006a;Winkler et al. 2006b). Two recent systematic reviews examining the empirical evidence found only little evidence for the influence of environmental factors on fruit and vegetable consumption [START_REF] Giskes | A systematic review of associations between environmental factors, energy and fat intakes among adults: is there evidence for environments that encourage obesogenic dietary intakes?[END_REF][START_REF] Kamphuis | Perceived environmental determinants of physical activity and fruit and vegetable consumption among high and low socioeconomic groups in the Netherlands[END_REF].

Another aspect of the food environment has been gaining attention in the public health sector; high energy dense foods, high fat foods and general convenience, processed foods including fast 3 food tend to be cheaper than healthy foods such as fresh fruits or vegetables [START_REF] Drewnowski | Poverty and obesity: the role of energy density and energy costs[END_REF][START_REF] Darmon | Energy-dense diets are associated with lower diet costs: a community study of French adults[END_REF]). Research on dietary behaviour and social inequalities suggest that low income households rather purchase energy dense foods that are nutrient poorer but are at an affordable cost compared to more expensive nutrient rich foods such as fresh fruits and vegetables [START_REF] Drewnowski | Food choices and diet costs: an economic analysis[END_REF]Drewnowski 2009). Data from the U.S. shows an inverse relationship between the energy density of foods and the energy costs measured in USD/1000kcal [START_REF] Drewnowski | Food choices and diet costs: an economic analysis[END_REF]. It is possible that lower food costs might be associated with higher energy dense diets which might lead to an increase in total energy intake. As a consequence, the higher prevalence of overweight and obesity in socio-economically disadvantaged groups could be explained by this imbalance of economics of food choice.

Research in the area of food environment and social inequality in Germany is lacking.

Although socioeconomic inequalities is less pronounced in Germany compared to other countries [START_REF] Van Doorslaer | Explaining the differences in income-related health inequalities across European countries[END_REF][START_REF] Hernandez-Quevedo | Socioeconomic inequalities in health: a comparative longitudinal analysis using the European Community Household Panel[END_REF], prior research has shown that people of low economic standing in Germany have above average rates of malnutrition, eating disorders and obesity [START_REF] Mackenbach | Socioeconomic inequalities in health in 22 European countries[END_REF][START_REF] Koch-Institut | Neighbourhood food environment and area deprivation: spatial accessibility to grocery stores selling fresh fruit and vegetables in urban and rural settings[END_REF]. The capital city of Germany, Berlin, consists of a number of districts where inhabitants live under conditions differing widely by their socioeconomic situation such as income, unemployment rate, and ethnic background as well as in their health and disease status (Senatsverwaltung für Gesundheit 2009).

In this pilot study, we sought to determine if differences in the food neighbourhood environment are apparent in Berlin, Germany. We analyzed the two districts with the largest social economic disparity and studied their availability of stores, produce prices and fruit and vegetable variety.

Methods

This study investigated access to food within two districts in Berlin comparing the districts with the lowest and highest socioeconomic population. The study examined (1) the number of grocery stores offering fresh produce; (2) the variety of fresh fruits and vegetables available to the consumers; and (3) the prices of a series of food items defined as healthy and unhealthy. Healthy food items included a series of popular fresh fruits and vegetables, milk and whole-wheat bread.

As unhealthy, energy dense food items, such as frozen pizza, chocolate, and potato chips were chosen.

Setting

Two areas in Berlin similar in size but with a widely different socioeconomic population were selected. The socioeconomic difference between the two areas was determined by a complex measuring tool called the Social Index (SI) created by the city of Berlin (Senatsverwaltung für Gesundheit 2009). The SI was developed to determine social differences between Berlin's neighbourhoods and to create a common ground for analysis and planning of social communities.

Among other things, the index is based on unemployment rates, average per capita income, number of people on social welfare, and life span expectancy. We chose to study the area of (10.4 km2 for Kreuzberg and 13.8 km 2 for Steglitz and Lankwitz) but population density is higher in Kreuzberg (14.239 residents/km 2 ) compared to Steglitz and Lankwitz (8.085 residents/km 2 ; Steglitz is 10.391 residents/km 2 and Lankwitz is 5.778 residents/km 2 ).

Availability

Within the districts the number of food stores including organic grocery stores and farmers' markets were counted. Food stores were identified through systematic investigation of each and every street within the established district borders. Farmers' markets were located through internet research. Food stores were defined as stores that offer at least one type of fresh vegetable and one type of fresh fruit (except lemons or limes). Food stores had to be open at least 5 days/week for 8 hours/day. Farmers' markets were included if they were open for at least 6 hours/week. Availability was defined as the number of food stores and farmers' markets per 10.000 residents.

Variety of fresh fruits and vegetables within food stores

Variety of food items was determined through the visual count of different kinds of fresh fruit and vegetables available at each store by a trained surveyor to all non-organic food stores during the months of May through July 2009. Given that organic food stores are still relatively rare as well as usually limited in their fruit and vegetable variety, only non-organic food stores and foods were assessed. The following fresh fruit and vegetable items were summarized into larger categories and counted as one: berries (strawberries, cranberries, raspberries, blackberries), lemon (lemon and limes), melons (watermelons, cantaloupes, honeydew), and cabbage (red cabbage, green cabbage, chinese cabbage). To control for seasonal variation and to increase comparability, we collected data concurrently in both districts and completed data collection within 12 weeks.

Pricing

For the purpose of price comparison between stores and districts, the most economical price for a sample of 12 products was recorded. The 12 products were chosen because of their popularity among the German population [START_REF] Fruchthandelsverband | Obst und Gemüse in Deutschland. Bonn Drewnowski A[END_REF]. Food prices of the following 12 food products were measured: apples, bananas, tomatoes, carrots, potatoes, whole wheat bread, fresh milk, frozen pizza, chocolate, potato chips, and beer. Since the most economical price for each food was often found in bulk quantities we calculated prices for predetermined amounts. Prices for fresh fruit and vegetable items were noted per one kilogram (1000 grams). Prices for whole wheat bread, chocolate and chips were recorded per 100 grams. Fresh milk prices were recorded as price per carton (1 liter), beer prices as the cost per 0.5 liter, and frozen pizza as price for one pizza (300 grams). Organic food stores were not entered to record prices or produce variety because high quality standards often cause costs to increase which makes sold items unaffordable to many people and high prices would result in distorted price averages.

Statistical Analysis

Analysis of variance was used to examine differences by district (low SI vs. high SI) in the mean number of fruits and vegetables and the mean lowest prices of the selected food items available in all stores. Using the average caloric content of selected food items (100g pizza = ca. 216kcal, 100g potato chips = ca. 547 kcal, 100g chocolate = ca. 536 kcal, 100g apples = ca. 49 kcal, 100g bananas = ca. 95 kcal, 100g carrots = ca. 25 kcal), the relationship between energy costs (Euro €/1,000 kcal) and energy density (kcal/g) of each food item was calculated.

Results

The low SI district (Kreuzberg) had greater access to supermarkets compared to the district with high SI (Steglitz + Lankwitz). Per 10,000 residents, in the low SI district 5.88 food stores (including farmer markets and organic food stores; N = 87) were available compared to only 4.42 food stores in the high SI district (N = 46). More organic food stores and farmers' markets were available in the low SI area compared to the high SI area.

Number of types of fruits and vegetables in the low SI district did not differ significantly from the number of types of fruits and vegetables in the high SI district (table 1).

-insert table 1 -

In the low SI district, prices of the selected food items were assessed in 72 grocery stores including 13 supermarkets, 23 discounters, and 36 farmers' markets. In the high SI district only 45 grocery stores including 18 supermarkets, 18 discounters, and nine farmers' markets were found. Including all types of food stores (super markets, discounters and farmers' markets) fruits and vegetables did not differ in pricing between the two districts. No differences were found for apples, bananas, tomatoes, carrots and beer. Potatoes (F= 9,122, p= 0.003), whole-wheat bread (F= 9,527, p = 0.003), fresh milk (F= 56,179, p = 0.000), chocolate (F= 40,489, p = 0.000), potato chips (F= 32,655, p = 0.000), and frozen pizza (F= 5,819, p = 0.018) were significantly cheaper in the high SI district compared to the low SI district (table 1). However, when the local farmers' markets which were more common in the low SI district were taken out of the analysis, the only four remaining items that were less expensive in the high SI district were whole-wheat bread (0,16 vs. 0,14; F=20,208, p = 0.000), fresh milk (0,50 vs. 0,48; F= 6,634, p= 0.012), and potato chips (0,29 vs. 0,28; F = 6,081, p = 0.016). Without the farmers' markets, bananas were cheaper in the low SI district compared to the high SI district (1,18 vs. 1,13; F= 10,589, p = 0.002).

To compare pricing of selected low and high energy dense foods, the mean prices of all grocery stores for the following food items were chosen: chocolate, potato chips, pizza, apples, bananas and carrots. Figure 1 shows the relationship between energy density (kcal/g) and energy costs (Euro€/1,000kcal) of a selection of low and high energy dense foods. It shows that energy costs for apples (3,26€/1,000kcal), bananas (4,10€/1,000kcal), and carrots (4,88€/1,000kcal) are higher than for pizza (2,16€/1,000kcal), potato chips (0,84€/1,000kcal), and chocolate (0,66€/1,000kcal) whereas energy density is higher for pizza (2,16kcal/g), potato chips (5,47kcal/g), and chocolate (5,36kcal/g) compared to apples (0,49kcal/g), bananas (0,95kcal/g) and carrots (0,25kcal/g).

-insert figure 1 -

Discussion

The variety and prices of the examined food items were similar in the high and low socioeconomic districts. More grocery stores per 10.000 residents were found in the low SI area compared to the high SI area. The variety of fruits and vegetables did not differ between the districts and no differences could be found in terms of fruit and vegetable prices. These findings are in line with several other studies (Smith et al. 2009;Zenk et al. 2009;[START_REF] Cassady | Is price a barrier to eating more fruits and vegetables for low-income families?[END_REF]) .

However, other food items such as fresh milk and whole wheat bread tended to be cheaper in the high SI district which in part supports the idea that healthy food choices tend to be more expensive in more disadvantaged neighbourhoods.

Looking at high-fat/energy-dense foods such as pizza, potato chips and chocolate significantly higher prices were observed in the low SI neighborhood. A possible explanation for the higher prices could be that grocery stores simply sell some of products at a higher price in neighbourhoods with a higher demand for these types of foods and products. Since this effect is mainly observed for unhealthy food items and not for fruits and vegetables it raises the question of the possibility of existing health inequity based on socio-economic standing.

In general, food pricing in Germany appears to be similar to food pricing in other nations with energy dense foods to be the lowest cost dietary options. For people with low SI, the financial aspect of foods most likely plays a crucial role in their purchase behaviour.

Limitations of this study

Several limitations of this study need to be mentioned. This was a pragmatic case-study approach with the focus on two geographically comparable areas in one particular city. Mainly the population density between the two districts differed. This approach does not allow the comparison of associations between neighbourhood deprivation and food accessibility for the full range of urban and rural settings across the world or even across Germany only.

The findings of this study can only be generalized to the study region and spatial inequality might exist in rural and small town settings in Germany. In addition, no information on residents' shopping behaviours was obtained and food quality was also not addressed. Other food outlets such as convenience stores without fresh fruits and vegetables, restaurants, snack bars that might play a role in determining food item pricing were also not examined.

Possible Implications and future research

To our knowledge, this is the first study in Germany looking at neighbourhood food environments. The findings showed that the food environment in a socioeconomically disadvantaged area was as conducive to buying healthier food choices as in a more advantaged area. One possible explanation could be that within the German population social inequality is less pronounced than in other countries such as the U.S. and therefore the difference of social status in the chosen urban districts was too small to be a factor in the food environment.

However, for the districts observed, energy dense foods were cheaper and therefore potentially more in demand in low SI districts than nutrient rich foods. Nevertheless, while prices for healthy foods appear to be similar in the districts, the purchase of such foods is determined by financial resources available to buyers. In particular, food inequity could be questioned since people with lower purchasing power have to pay similar prices for healthy foods compared to those with higher purchasing power.

Our findings could suggest that inequalities in food intake may have little to do with the food environment in Germany but rather the economics of food choice. Social inequality in Germany has been linked to obesity and other chronic disease and as Drewnowski and colleagues [START_REF] Drewnowski | Food choices and diet costs: an economic analysis[END_REF][START_REF] Drewnowski | Obesity and the food environment: dietary energy density and diet costs[END_REF]) have recently pointed out, more likely factors for the lower nutritional quality of diets of low-income households could be the low cost of energydense foods. Thus, as long as energy dense foods are highly palatable and cheaper we believe it

  Kreuzberg which lies within the community district of Kreuzberg-Friedrichshain and represents the neighborhood with one of lowest SI in Berlin based on the SI of 2008. The other area chosen was Steglitz and Lankwitz which is an area within the community district of Steglitz-Zehlendorf. Steglitz-Zehlendorf represents the neighborhood with the highest SI in Berlin in 2008. The net household income in Kreuzberg-Friedrichshain in 2006 was € 1,175 per months whereas the net household income in Steglitz-Zehlendorf was € 1,850. The areas are roughly of the same size

  Winkler E, Turrell G, Patterson C (2006b) Does living in a disadvantaged area entail limited opportunities to purchase fresh fruit and vegetables in terms of price, availability, and variety? Findings from the Brisbane Food Study. Health Place 12:741-748 Zenk SN, Lachance LL, Schulz AJ, Mentz G, Kannan S and Ridella W (2009) Neighborhood retail food environment and fruit and vegetable intake in a multiethnic urban population. Am J Health Promot 23:255-264 Zenk SN, Schulz AJ, Israel BA, James SA, Bao S and Wilson ML (2005) Neighborhood racial composition, neighborhood poverty, and the spatial accessibility of supermarkets in metropolitan Detroit. Am J Public Health 95:660-667

Table 1 .

 1 Fruit and vegetable variety and mean pricing in Euro (€) and Standard Error of the Mean (SEM) of foods by neighbourhood socioeconomic standing. Relationship between energy density (kcal/g) and energy costs (Euro€/1,000kcal) of selected food items

	Low SES	High SES
	(N=72)	(N=45)

will be difficult to change low-income household's food choices and health inequity through pricing remains.

Further research needs to be conducted not only in other geographical areas in Germany and Europe in general but also other mechanisms such as cooking skills and habits in households as well as food costs and its relationship with energy density need to be examined. Currently not enough is known if and how household and food shopping environments affect population intake of fruits and vegetables and its relationship to socioeconomic inequalities in food intake.

Conflict of interest statement

The authors declare that they have no conflict of interest.