Animals and 2-Motzkin Paths

Wen-jin Woan^{1} Department of Mathematics Howard University Washington, DC 20059 USA

                       wwoan@howard.edu

Abstract

We consider an animal S as a set of points in the coordinate plane that are reachable from the origin (0, 0) through points in S by steps from {(1, 0), (0, 1), (1, 1), (−1, −1)}. In this paper, we give a combinatorial bijection with 2-Motzkin paths, i.e., the Motzkin paths with two different horizontal steps.

1 Introduction

We start by dividing the plane into eight equal octants. In this paper we count animals A_{i}, 1 ≤ i ≤ 3, in the first i octants . The count of A_{1} was first done by Gouyou-Beauchamps and Viennot [5] and the idea of classifying it by the number of points lying on the x-axis is due to Aigner [1]. Bousquet-Melou [3] includes the possibility of diagonal steps, which changes the count of A_{3} from 3^{n} to 4^{n}, and that is the case we will consider here. In Theorems 8, 13, and 18 we give a bijection between animals and 2-Motzkin paths. For definitions and references, see Stanley [7].

Definition 1 An animal S is a set of points in the xy-plane with integer coordinates that satisfy the following conditions:

1. (0, 0) ∈ S,

2. if (a, b) ∈ S and b ≠ −a, let C(a, b) := {(a−1, b), (a, b−1), (a−1, b−1)}, then C(a, b)∩ S ≠ ∅,

3. if (0, 0) ≠ (−b, b) ∈ S, then (−(b − 1), (b − 1)) ∈ S.

1Author’s current address: 2103 Opal Ridge, Vista, CA 92081, USA.

For A_{1} we require also that 0 ≤ b ≤ a, i.e., the first octant. For A_{2} we want 0 ≤ a, b, i.e., the first quadrant or the first two octants. Then A_{3} is defined by 0 ≤ b and a + b ≥ 0, i.e., the first three octants.

Definition 2 We start with partial Motzkin paths beginning at (0, 0) with steps from {U = (1, 1), D = (1, −1), H = (1, 0)}. Then bicoloring the horizontal steps we have partial 2-Motzkin paths with steps from {U = (1, 1), D = (1, −1), H_{r} = (1, 0) and H_{g} = (1, 0)}, where H_{r} is a horizontal step colored red and where H_{g} is a horizontal step colored green. Let M(n) = M_{3}(n) be the set of all partial 2-Motzkin paths of n steps, let M_{2}(n) ⊂ M_{3}(n) be the set of paths that never go below the x-axis and let M_{1}(n) ⊂ M_{2}(n) denote the set of paths that end on x-axis at (n, 0) and let m_{i}(n) = |M_{i}(n)| and m_{i}(n, k) = |M_{i}(n, k)|, where M_{i}(n, k) is the set of partial 2-Motzkin paths that end at (n, k).

For m, k ≤ 6, the entries (m_{3}(n, k)) and (m_{2}(n, k)) are as follows:

(m_{3}(n, k)) = [ \begin{matrix}n/k & −5 & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 \\ 4 & 0 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 \\ 5 & 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 \end{matrix} ] ,

(m_{2}(n, k)) = [ \begin{matrix}n/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 14 & 6 & 1 & 0 & 0 \\ 4 & 42 & 48 & 27 & 8 & 1 & 0 \\ 5 & 132 & 165 & 110 & 44 & 10 & 1 \end{matrix} ] .

Let A(n) be the set of all animals of size n = |S − {(0, 0)}| , i.e., we do not count the origin (0, 0) for the size. Let A_{i}(n) be the set of animals in the first i octants of size n and a_{i}(n) = |A_{i}(n)| be the number of elements. We shall construct a bijection between A_{i}(n) and M_{i}(n).

Example 3 For n = 2, we illustrate the 5 elements in A_{1}(2), and their counterparts in M_{1}(2); × marks source points on the line y = −x. Note that the lowest source point is the origin, (0, 0).

× • • → H_{r}H_{r}, \begin{aligned}& • \\ × & • \end{aligned} → UD, \begin{aligned}& & • \\ × & • \end{aligned} → H_{r}H_{g},

\begin{aligned}& • & • \\ × \end{aligned} → H_{g}H_{r}, \begin{aligned}& & • \\ & • \\ × \end{aligned} → H_{g}H_{g}.

Both A_{2}(2) and M_{2}(2) have 10 elements. The following 5 elements are those not in A_{1}(2):

\begin{aligned}& • \\ & • \\ × \end{aligned} → H_{g}U, \begin{matrix}• \\ × & • \end{matrix} → H_{r}U, \begin{matrix}• & • \\ × \end{matrix} → UH_{r}

\begin{aligned}& • \\ • \\ × \end{aligned} → UH_{g}, \begin{matrix}• \\ • \\ × \end{matrix} → UU.

We have 16 elements in A_{3}(2), M_{3}(2). The following 6 elements are those not in A_{2}(2)

\begin{aligned}× \\ & × & • \end{aligned} → H_{r}D, \begin{aligned}× & • \\ & × \end{aligned} → DH_{r}, \begin{aligned}× & & • \\ & × \end{aligned} → H_{g}D,

\begin{aligned}& • \\ × \\ & × \end{aligned} → DH_{g}, \begin{aligned}• \\ × \\ & × \end{aligned} → DU, \begin{aligned}× \\ & × \\ & & × \end{aligned} → DD.

Algorithm 4 We describe a decomposition method of an animal into two smaller parts, the top T and the bottom B. The bottom part is an animal while the top part will be an animal after we apply Algorithm 5. Let S be an animal and start the partition path at P_{S}(a_{0}, a_{0}) at a point (a_{0}, a_{0}) with the least a_{0} > 0. If (a_{i}, b_{i}) ∈ S, go E = (1, 0) one unit; otherwise go diagonally D = (1, 1) one unit. Keep going until there are no more points in S with larger first coordinate than this point. Let T ⊂ S be the set of points on or above the path and let B ⊂ S denote the set of points below the path.

Algorithm 5 Let us define T (i) inductively: T (1) = T, and T (i + 1) is constructed from T (i) by replacing each (a, b) ∈ T (i) with (a − 1, b − 1) whenever C(a, b) ∩ T (i) = ∅ and a, b > 0. Continue until T (i + 1) = T (i) = T′.

Example 6 For the following example S, we start with (2, 2) and by Algorithm 4 the partition path of S is P = EEDEEDE, i.e., (2, 2) → (3, 2) → (4, 2) → (5, 3) → (6, 3) → (7, 3) → (8, 4) → (9, 4),

S = \begin{aligned}& & & & & ∘4 & & ∘6 & ∘7 \\ & & & & & ∘3 & ∘5 \\ & & ∘1 & ∘2 & & • \\ & & • & • & • & • \\ × & • & • & • \end{aligned} ,

The partition path partitions S into B, T as follows:

B = \begin{aligned}& & & & & • \\ & & • & • & • & • \\ × & • & • & • \end{aligned} ,

T = \begin{aligned}& & & ∘4 & & ∘6 & ∘7 \\ & & & ∘3 & ∘5 \\ & ∘1 & ∘2 \\ × \end{aligned} ,

Applying Algorithm 5 on T, we have

T′ = \begin{aligned}& & ∘4 & & ∘6 & ∘7 \\ ∘1 & ∘2 & ∘3 & ∘5 \end{aligned} .

2 Animals A_{1}(m) and 2-Motzkin Paths M_{1}(m)

Here we construct a bijection between animals and 2-Motzkin paths. For other bijections and partitions, see [2, 4]. Example 7 For m = 1, 2. A_{1}(m) ⇔ M_{1}(m)

× • → H_{r}, \begin{aligned}& • \\ × \end{aligned} → H_{g} ,

× • • → H_{r}H_{r}, \begin{aligned}& & • \\ × & • \end{aligned} → H_{r}H_{g}, \begin{aligned}& • \\ × & • \end{aligned} → UD,

\begin{aligned}& • & • \\ × \end{aligned} → H_{g}H_{r}, \begin{aligned}& & • \\ & • \\ × \end{aligned} → H_{g}H_{g}.

Theorem 8 The number of the animals in the first octant of size n is given by c_{n+1}, the (n + 1)^{th} Catalan number.

Proof. By induction, assume that the theorem is true for size less than n. Let S ∈ A_{1}(n). We apply Algorithm 4 by starting at the smallest d > 0 such that (d, d) ∈ S to partition S into T, B. We apply Algorithm 5 to obtain the T′. Let B → B′ ∈ A_{1}(k − 1), by removing the first point (the origin). If T′ = ∅, then B′ is of size k − 1 = n − 1, the first step is H_{r} and by induction S → H_{r}B^{∗}. If B′ = ∅, then the first step is H_{g} and by induction S → H_{g}T^{∗}. Otherwise, the first step is U and the k^{th} step is D, by induction fill in steps 2 to (k − 1) by B′ → B^{∗} and steps (k + 1)^{th} to the n^{th} by T′ → T^{∗}, i.e., S → P = U(B^{∗})D(T^{∗}).

Conversely, by induction let P = a_{1}a_{2} ⋯ a_{n} ∈ M_{1}(n). If a_{1} = H_{r}, then P′ = a_{2}a_{3} ⋯ a_{n} is of size m − 1, by induction P′ → S^{∗} and S = (S^{∗} + (1, 0)) ∪ {(0, 0)} ∈ A_{1}(n) (shift S^{∗} to the right one unit). If a_{1} = H_{g}, then S = {S^{∗} + (1, 1) ∪(0, 0)} (shift S^{∗} diagonally up one unit). If a_{1} is U, then find the first k such that a_{1}a_{2} ⋯ a_{k} ∈ M(k), B = a_{2}a_{3} ⋯ a_{k−1} and T = a_{k+1}a_{k+2} ⋯ a_{n}. By induction T → T^{∗}, B → B^{∗} → B′ = (B^{∗} + (1, 0)) ∪ {(0, 0)}. Let T′ = T^{∗} + (j + 1, j + 1), where j = max{b : (a, b) ∈ B}, and then apply Algorithm 5 by starting with the union of B′ and T′. By induction the total count is

a_{1}(n) = a_{1}(n − 1) + a_{1}(n − 2)a_{1}(0) + a_{1}(n − 3)a_{1}(1) + a_{1}(n − 4)a_{1}(2) + ⋯
= c_{n}c_{0} + c_{n−1}c_{1} + c_{n−2}c_{2} + ⋯ + c_{0}c_{n−1}
= ∑_{i=0}^{n} c_{n−i}c_{i} = c_{n+1},

where the first term represents the case that T is empty and the second term represents the case that T is one point. Similarly, the last term represents the case that B is empty and next-to-last term represents the case that B is one point.

The generating function is ∑ a_{1}(n)x^{n} = 1 + 2x + 5x^{2} + 14x^{3} + 42x^{4} + ⋯ = C^{2}.

Example 9 This example is for the first part of the proof in Theorem 8. The partition path is (2, 2) → (3, 2) → (4, 2) → (5, 3) → (6, 3), which partitions S into two animals T, B. By induction we produce 2-Motzkin paths T^{∗} and B^{∗}, and by Theorem 8 we produce a 2-Motzkin path P for S.

S = \begin{aligned}& & & & & ∘ \\ & & & & & ∘ \\ & & ∘ & ∘ & & • \\ & & • & & • & • \\ × & • & • & • \end{aligned} → T = \begin{aligned}& & ∘ \\ × & ∘ & ∘ \end{aligned} , B = \begin{aligned}& & & & • \\ & • & & • & • \\ × & • & • \end{aligned} ,

P = U(B^{∗})D(T^{∗}) → U(UH_{r}H_{g}UDD)D(H_{r}UD).

Example 10 This example is for the converse of the bijection. We start with a 2-Motzkin path P = U(UH_{r}DH_{r}H_{r}UD)D(H_{r}UH_{r}H_{g}H_{r}D), locate the first D such that the path P comes back to x-axis. The subpath B = UH_{r}DH_{r}H_{r}UD is the section of P between the first step(U) and this D, the section after this D is the subpath T = H_{r}UH_{r}H_{g}H_{r}D. By induction we produce subanimals T^{∗} and B^{∗}, using Theorem 8 we produce the animal S for P.

T → T^{∗} = \begin{aligned}& & ∘4 & & ∘6 & ∘7 \\ ×1 & ∘2 & ∘3 & ∘5 \end{aligned} , B → B^{∗} → B′ = \begin{aligned}& & & & & • \\ & & • & • & • & • \\ × & • & • & • \end{aligned} ,

B′ ∪ T′ = \begin{aligned}& & & & & ∘4 & & ∘6 & ∘7 \\ & & & ×1 & ∘2 & ∘3 & ∘5 \\ & & & & & • \\ & & • & • & • & • \\ × & • & • & • \end{aligned} ,

P → S = \begin{aligned}& & & & & ∘4 & & ∘6 & ∘7 \\ & & & & & ∘3 & ∘5 \\ & & ×1 & ∘2 & & • \\ & & • & • & • & • \\ × & • & • & • \end{aligned} .

Remark 11 Let us partition A_{1}(n) by the number points on the line y = x. Let A_{1}(n, k) = {S ∈ A_{1}(n) : |S ∩ {(x, x) : x > 0}| = k} and a_{1}(n, k) = |A_{1}(n, k)|. Then the following is the matrix (a_{1}(n, k)) for n, k up to 5:

[ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 2 & 1 & 0 & 0 & 0 \\ 3 & 5 & 5 & 3 & 1 & 0 & 0 \\ 4 & 14 & 14 & 9 & 4 & 1 & 0 \\ 5 & 42 & 42 & 28 & 14 & 5 & 1 \end{matrix} ] .

We say that an infinite lower triangular matrix L = (g, f) is a Riordan matrix if the generating function of the k^{th} column is gf^{k} for all k. Here (a_{1}(n, k)) = (C, xC). For more about the Riordan matrix, see [6].

Remark 12 By using the Lagrange Inversion Formula (Wilf [8]) with some index adjustment we derive the explicit formula a_{1}(n, k) = \frac{k+1}{2n−k+1} \binom{2n−k+1}{n−k}.

3 Animals A_{2}(m) and 2-Motzkin PathsM_{2}(m)

Here we construct a bijection between animals and 2-Motzkin paths. For other bijections and partitions, see [2, 4].

Theorem 13 There is a bijection between M_{2}(m) and A_{2}(m). Moreover, for all m ≥ 0, we have a_{2}(m) = \binom{2m+1}{m}.

Proof. Let S ∈ A_{2}(m), we apply Algorithm 4 by starting at (0, 1) to partition S into T, B. Then B ∈ A_{1}(k) and by applying Algorithm 5, T → T′. If T = ∅, then S ∈ A_{1}(m) and by Theorem 8 we are done. Otherwise, T′ → T^{∗} = T′ − (0, 1), B → B^{∗}; and S → P = B^{∗}UT^{∗}.

Conversely, by induction let P = a_{1}a_{2} ⋯ a_{m} ∈ M_{2}(m) − M_{1}(m). We look for the largest k such that (k, 0) ∈ P, i.e., the last time P is on the x-axis. By induction a_{1}a_{2} ⋯ a_{k} → B and a_{k+2} ⋯ a_{m} → T. T → T′ = T + (0, 1) → T^{∗} = T′ + (j + 1, j + 1), where j = max{b : (a, b) ∈ B}. Apply Algorithm 5 by starting with B ∪ T^{∗}; we have P → S = (B ∪ T^{∗})′.

The generating function of the counts of A_{2}(m) is

C^{2}(1 + xC^{2} + (xC^{2})^{2} + (xC^{2})^{3} + ⋯) = \frac{C^{2}}{1 − xC^{2}} = \frac{C^{2}}{C\sqrt{1 − 4x}} = \frac{C}{\sqrt{1 − 4x}}.

These numbers appear as the nonzero entries in column one in the Pascal’s Triangle.

Example 14 This example is for the first part of Theorem 13. We start an animal S with the partition path (2, 3) → (3, 3) → (4, 3) → (5, 4) → (6, 4) → (7, 5) → (8, 5), which partitions S into B, T. By induction B → B^{∗}, T → T^{∗} we derive the path P.

S = \begin{aligned}& & & & & & & ∘4 \\ & & & & & & & ∘3 \\ & & & ∘ & ∘ & & & ∘2 \\ & & & ∘ & & ∘1 & & • \\ & & ∘ & ∘ & & • & & • \\ & & • & & & • & • \\ & & • & • & • \\ × & • \end{aligned} ,

B = \begin{aligned}& & & & & & & • \\ & & & & & • & & • \\ & & • & & & • & • \\ & & • & • & • \\ × & • \end{aligned} → B^{∗} = U(H_{g}H_{r}UH_{g}H_{r}H_{g}DH_{r})D,

T = \begin{aligned}& ∘ & ∘ & ∘4 \\ & ∘ & & ∘3 \\ × & ∘ & ∘1 & ∘2 \end{aligned}  → T^{∗} = (U(H_{r}UD)D)UH_{r}H_{r} →

P = (B^{∗})U(T^{∗}) = (UH_{g}H_{r}UH_{g}H_{r}H_{g}DH_{r}D)U(UH_{r}UDDUH_{r}H_{r}).

Remark 15 Let us partition A_{2}(m) by

A_{2}(m, k) = {S ∈ A_{2}(m) : k = max{b − a : (a, b) ∈ S}}

and a_{2}(m, k) = |A_{2}(m, k)|. By using the Lagrange Inversion Formula (Wilf [8]) and simple algebraic operations we obtain the explicit formula a_{2}(m, k) = \frac{2k+2}{2m+2} \binom{2m+2}{m−k}. Then by Theorem 13 the following is the matrix (a_{2}(m, k)) = (C^{2}, xC^{2}) for m, k up to 5:

[ \begin{matrix}m/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 01 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 14 & 6 & 1 & 0 & 0 \\ 4 & 42 & 48 & 27 & 8 & 1 & 0 \\ 5 & 132 & 165 & 110 & 44 & 10 & 1 \end{matrix} ] .

Remark 16 Let us partition A_{2}(m) by

A_{2}^{∗}(m, k) = {S ∈ A_{2}(m) : k = max{b : (0, b) ∈ S}}

and a_{2}^{∗}(m, k) = |A_{2}^{∗}(m, k)| . The set A_{2}^{∗}(m, 0) consists of two copies of A_{2}(m − 1); one copy consists of those with no points on x-axis except the origin and the other copy with such points. Hence the generating function is

1 + \frac{2xC}{\sqrt{1 − 4x}} = \frac{\sqrt{1 − 4x} + 2xC}{\sqrt{1 − 4x}} = \frac{\frac{2−C}{C} + 2xC}{\sqrt{1 − 4x}} = \frac{1}{\sqrt{1 − 4x}}.

Note that if (0, 1) ∈ S, the partition is T, B in Theorem 13 with B containing no point on y = x > 0. By using the Lagrange Inversion Formula (Wilf [8]) and simple algebraic operations we can derive the explicit formula a_{2}^{∗}(m, k) = \binom{2m−k}{m−k}.

The generating function for B is C and the following is the matrix (a_{2}^{∗}(m, k)) = (\frac{1}{\sqrt{1−4x}}, xC) for m, k up to 5:

[ \begin{matrix}m/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 6 & 3 & 1 & 0 & 0 & 0 \\ 3 & 20 & 10 & 4 & 1 & 0 & 0 \\ 4 & 70 & 35 & 15 & 5 & 1 & 0 \\ 5 & 252 & 126 & 56 & 21 & 6 & 1 \end{matrix} ] .

Remark 17 Let us go a step further. Let D(m) = A_{2}(m, 0), the set of animals in the first quadrant containing no point on the y-axis except the origin and partition D(m) by the number of points on the x-axis D(m, k) = {S ∈ D(m) : (k, 0) ∈ S, (k + 1, 0) ∉ S}. Let d(m, k) = |D(m, k)|. Then by using the Lagrange Inversion Formula (Wilf [8]) and simple algebraic operations we can derive the explicit formula d(m, k) = \binom{2m−k−1}{m−k} for k > 0 and d(m, 0) = \binom{2m−1}{m−1}.

The following is the matrix (d(m, k)) for m, k up to 5:

[ \begin{matrix}m/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 2 & 1 & 0 & 0 & 0 \\ 3 & 10 & 6 & 3 & 1 & 0 & 0 \\ 4 & 35 & 20 & 10 & 4 & 1 & 0 \\ 5 & 126 & 70 & 35 & 15 & 5 & 1 \end{matrix} ] = ( 1 + \frac{xC}{\sqrt{1 − 4x}}, xC(x)).

4 Animals A_{3}(m) and 2-Motzkin Paths M_{3}(m)

Here we construct a bijection between animals and 2-Motzkin paths. For other bijections and partitions, please see [2, 4].

Theorem 18 There is a bijection between M_{3}(m) = M(m) and A_{3}(m) = A(m). Moreover, the number of animals in the first three octants of size m is 4^{m}, m ≥ 0.

Proof. Let S ∈ A_{3}(m), apply Algorithm 4 by starting at (−1, 1) to partition S into T, B. Then B ∈ A_{1}(k) and apply Algorithm 5 to T → T′ ∈ A_{3}(m − k − 1). Then T′ → T^{∗} = T′ + (1, −1). If S ∈ A_{2}(m), then by Theorem 13 we are done. Otherwise, by induction S → (B^{∗})D(T^{∗}) ∈ M_{3}(m).

Conversely, let P = a_{1}a_{2} ⋯ a_{m} ∈ M_{3}(m). If P ∈ M_{2}(m), then by Theorem 13, we are done. Otherwise, we look for the first k such that (k, 0) ∈ P and P goes under the xaxis after that. Then by induction a_{1}a_{2} ⋯ a_{k} → B^{∗} and a_{k+2} ⋯ a_{m} → T , T → T′ = T + (−1, 1). T^{∗} = E ∪ ((T′ − E) + (j + 1, j + 1)), where E is the set of points in T′ that are not in the first quadrant and j = max{(b : (a, b) ∈ B}. Apply Algorithm 5 by starting with B^{∗} ∪ T^{∗}. We have P → S.

In terms of generating functions we have

\frac{C}{\sqrt{1 − 4x}}((1+xC^{2}+(xC^{2})^{2}+(xC^{2})^{3}+⋯) = \frac{C}{\sqrt{1 − 4x}} \frac{1}{1 − xC^{2}} = \frac{C}{\sqrt{1 − 4x}} \frac{1}{C\sqrt{1 − 4x}} = \frac{1}{1 − 4x}.

Example 19 This example is the converse of the proof of Theorem 18. Let

P = (UUDH_{r}H_{g}H_{g}DH_{g}H_{r})D(H_{r}H_{r}DH_{r}H_{g}H_{g}H_{r})

be a 2-Motzkin path and locate the first D step, where the path goes below the x-axis. The section of P before the D is B and the section after the D is T. Then by induction we derive the animal S for P.

B = U(UDH_{r}H_{g}H_{g})D(H_{g}H_{r}) → B^{∗} = \begin{aligned}& & & & & • \\ & & & • & & • \\ & & • & & • \\ & & • & • \\ × & • & • \end{aligned} ,

(H_{r}H_{r})D(H_{r}H_{g}H_{g}H_{r}) → T = \begin{aligned}& & & ∘4 & ∘5 \\ & & ∘ \\ × & ∘ \\ & ×1 & ∘2 & ∘3 \end{aligned} ,

T′ = \begin{aligned}& & & ∘4 & ∘5 \\ & & ∘ \\ × & ∘ \\ & ×1 & ∘2 & ∘3 \\ & & × \end{aligned} ,

P = (UUDH_{r}H_{g}H_{g}DH_{g}H_{r})D(H_{r}H_{r}DH_{r}H_{g}H_{g}H_{r}) = (B^{∗})D(T^{∗}),

→ S = \begin{aligned}& & & & & ∘5 & & ∘3 \\ & & & ∘4 & & ∘2 & & • \\ & & ∘ & & & • & & • \\ × & ∘ & & & • & & • \\ & ×1 & & & • & • \\ & & × & • & • \end{aligned} .

Remark 20 Let us partition A(m) by the number of source points on the line y = −x > 0. Let A(m, k) = {S ∈ A(m) : (−k, k) ∈ S, (−(k + 1), k + 1) ∉ S} and a(m, k) = |A(m, k)| . By using the Lagrange Inversion Formula (Wilf [8]) and simple algebraic operations we obtain the explicit formula a(m, k) = \binom{2m+1}{m−k}.

The following is the matrix (a(m, k)) for m, k up to 5:

(a(m, k)) = [ \begin{matrix}m/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 10 & 5 & 1 & 0 & 0 & 0 \\ 3 & 35 & 21 & 7 & 1 & 0 & 0 \\ 4 & 126 & 84 & 36 & 9 & 1 & 0 \\ 5 & 462 & 330 & 165 & 55 & 11 & 1 \end{matrix} ] = (\frac{C}{\sqrt{1 − 4x}}, xC^{2}).

The k^{th} column is the condensed version of the (2k + 1)^{th} column of Pascal’s Triangle.

5 Acknowledgment

The author wishes to thank Lou Shapiro for introduction of the subject and subsequent help and encouragement.

The author also would like to thank Emeric Deutsch for his helpful discussions about this subject.

References

[1] M. Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663–675.

[2] E. Barcucci, A. Del Lungo, E. Pergola and R. Panzani, Directed animals, forests and permutations, Discrete Math. 204 (1999), 41–71.

[3] M. Bousquet-Mèlou, New enumerative results on two dimensional directed animals, Discrete Math. 180 (1998), 73–106.

[4] M. Bousquet-Melou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (2002), 235–274.

[5] D. Gouyou-Beauchamps and G. Viennot, Equivalence of the two dimensional animal problems to one dimensional path problems, Adv. Appl. Math. 9 (1988), 334–357.

[6] L. W. Shapiro, Seyoum Getu, Wen-jin Woan and Leon C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[7] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[8] H. S. Wilf, Generatingfunctionology, Academic Press, 1994.

2000 Mathematics Subject Classification: Primary 05A15. Keywords: animals, directed animals, Motzkin paths, Catalan paths, binomial coefficients.

(Concerned with sequence \underline{A000108}.) Received October 2 2005; revised version received November 1 2005. Published in Journal of Integer Sequences, November 1 2005. Return to Journal of Integer Sequences home page.