Séminaire Lotharingien de Combinatoire 46 (2001), Article B46b

ECO method and hill-free generalized Motzkin paths

Elena Barcucci ^{∗}  Elisa Pergola ^{∗}  Renzo Pinzani ^{∗}

Simone Rinaldi ^{∗}

Abstract

In this paper we study the class of generalized Motzkin paths with no hills and prove some of their combinatorial properties in a bijective way; as a particular case we have the Fine numbers, enumerating Dyck paths with no hills. Using the ECO method, we define a recursive construction for Dyck paths such that the number of local expansions performed on each path depends on the number of its hills. We then extend this construction to the set of generalized Motzkin paths.

1 Introduction

Let k be any fixed positive integer. In the plane ℤ × ℤ we consider lattice paths using three step types: a rise step defined by (1, 1), a fall step defined by (1, −1) and a k-length horizontal step defined by (k, 0), and usually called k-horizontal step. A generalized Motzkin path is a sequence of rise, fall and k-horizontal steps, running from (0, 0) to (n, 0), and remaining weakly above the x-axis. Let M be the set of generalized Motzkin paths, and M_{n} the set of these paths terminating at (n, 0). The classes of Motzkin, Schröder and Dyck paths are obtained as particular cases for k = 1, k = 2 and k = ∞, respectively. The generating function for generalized Motzkin paths according to the their length is:

M(x) = ∑_{n≥0} |M_{n}| x^{n} = \frac{1 − x^{k} − \sqrt{1 − 2x^{k} + x^{2k} − 4x^{2}}}{2x^{2}} .  (1)

A hill of a generalized Motzkin path is a pair of consecutive rise and fall steps giving a peak of height 1. Dyck paths with no hills, according to the semi-length of the path, are counted by Fine numbers: 1, 0, 1, 2, 6, 18, 57, … (sequence M1624 of [10]). These numbers are extensively studied in the literature [3, 4, 6, 7, 8], as they are intimately related to Catalan numbers, and have many combinatorial interpretations; the main results are collected in a survey by Deutsch and Shapiro [5]. In particular, the Fine numbers enumerate Dyck paths with the leftmost peak of even height, ordered trees with no leaves at level 1, ordered trees with root of even degree, standard Young tableaux of shape (n, n), without columns of the

∗Dipartimento di Sistemi e Informatica, Via Lombroso 6/17, 50134 Firenze, Italy { barcucci, elisa, pinzani, rinaldi}@dsi.unifi.it

form \begin{matrix}k \\ k + 1 \end{matrix} .

In the first part of this work we study the class of hill-free generalized Motzkin paths, that is, generalized Motzkin paths with no hills, and extend some properties already known for Dyck paths with no hills. In particular, we bijectively prove the following linear recurrence relation:

f_{n} = 2s_{n} + s_{n−2} − s_{n−k},  n > k,  (2)

where s_{n} is the number of paths of M_{n} with no hills and f_{n} = |M_{n}|. For k = ∞, (2) reduces to the known, but not well-known, recurrence f_{n} = 2s_{n} + s_{n−2} involving Catalan and Fine numbers.

In Section 3 we apply the ECO method to Dyck paths. ECO (Enumerating Combinatorial Objects) [1] is a method for the enumeration and the recursive construction of a class of combinatorial objects, O, by means of an operator ϑ which performs “local expansions” on the objects of O. More precisely, let p be a parameter on O, such that |O_{n}| = |{O ∈ O : p(O) = n}| is finite. An operator ϑ on the class O is a function from O_{n} to 2^{O_{n+1}}, where 2^{O_{n+1}} is the power set of O_{n+1}.

Proposition 1 Let ϑ be an operator on O. If ϑ satisfies the following conditions:

1. for each O′ ∈ O_{n+1}, there exists O ∈ O_{n} such that O′ ∈ ϑ(O),

2. for each O, O′ ∈ O_{n} such that O ≠ O′, then ϑ(O) ∩ ϑ(O′) = ∅,

then the family of sets F_{n+1} = {ϑ(O) : O ∈ O_{n}} is a partition of O_{n+1}.

We refer to [1] for further details, proofs and definitions. Once the parameter p is fixed, if we are able to define an operator ϑ which satisfies conditions 1. and 2., then Proposition 1 allows us to construct each object O′ ∈ O_{n+1} from an object O ∈ O_{n}, and each object O′ ∈ O_{n+1} is obtained from one and only one O ∈ O_{n}.

The recursive construction determined by ϑ can be described by a generating tree [2], whose vertices are objects of O. The objects having the same value of the parameter p lie at the same level, and the sons of an object are the objects it produces through ϑ; the branches that join O with its sons have length 1. A generating tree can be described by means of a succession rule of the form:

\{ \begin{matrix}(b) \\ (h) ⇝ (c_{1})(c_{2}) … (c_{h}), \end{matrix}

where b, h, c_{i} ∈ ℕ, meaning that the root object has b sons, and the h objects O′_{1}, …, O′_{h}, produced by an object O are such that |ϑ(O′_{i})| = c_{i}, 1 ≤ i ≤ h.

The construction we propose for Dyck paths is determined by an operator ϑ which works on the set of hills of the paths. Therefore the set of paths obtained from a path P through ϑ entirely depends on the number of hills of P. The new succession rule defining Catalan numbers has the form:

\{ \begin{matrix}(1) \\ (1) ⇝ (2) \\ (2^{k}) ⇝ (1)^{2^{k−1}}(2)^{2^{k−2}}(4)^{2^{k−3}} … (2^{k−2})^{2}(2^{k−1})(2^{k+1}). \end{matrix}

In the last section we slighly extend the main concepts of ECO method, allowing the operator ϑ to produce objects of different sizes through a local expansion, that is, from O ∈ O_{n}, ϑ can produce objects in O_{n+i}, i ≥ 1. This idea is then suitably applied in order to generalize the construction given in Section 3 for Dyck paths to the class of generalized Motzkin paths.

2 Hill-free paths

The generating function S(x) for the sequence {s_{n}} of generalized Motzkin paths with no hills is easily determined. Indeed, all of these paths are constructed by means of the unambiguous object grammar in Fig.1, S being a generalized Motzkin path with no hills, and \overline{M} a non-empty generalized Motzkin path.

Figure 1: The object grammar generating generalized Motzkin paths with no hills.

Thus we have:

S(x) = 1 + x^{2}(M(x) − 1)S(x) + x^{k}S(x),  (3)

and from (1), we get:

S(x) = \frac{1 − x^{k} + 2x^{2} − \sqrt{1 − 2x^{k} + x^{2k} − 4x^{2}}}{2x^{2}(2 + x^{2} − x^{k})} .  (4)

Conversely, let M be a generalized Motzkin path, we have two cases:

1. M is a hill-free path;

2. there are a hill-free path S and a generalized Motzkin path M′, possibly empty, such that M = Sxx̄M′, where x and x̄ encode rise and fall steps, respectively.

These considerations suggest an unambiguous construction for generalized Motzkin paths, from which the following functional equation arises:

M(x) = S(x) + x^{2}M(x)S(x).  (5)

From (5) we get:

M(x) = \frac{S(x)}{1 − x^{2}S(x)} = ∑_{n≥0} x^{2n}S^{n+1}(x).  (6)

which can be combinatorially explained by observing that each term x^{2n}S^{n+1}(x) in (6) counts the generalized Motzkin paths having exactly n hills.

Example 1 Schröder paths with no hills are enumerated by the small Schröder numbers, whose first terms are 1, 1, 3, 11, 45, 197, 903, … (sequence M2898 in [10]). Let us prove the same result by establishing a bijection Φ between the Schröder paths with no hills and those having at least one hill (see Fig.2). We recall that Schröder paths are counted by large Schröder numbers, S_{n}: S_{0} = 1, S_{n} = 2s_{n}, n > 0 (sequence M1659 in [10]).

Figure 2: The bijection between Schröder paths having at least one hill and those with no hills.

Let R be a Schröder path having at least one hill. We distinguish the following two cases:

1. the path R has exactly one hill and the path begins with that hill. Therefore R can be represented as R = xx̄R′, where R′ is a Schröder path with no hills. The path Φ(R) is obtained from R by replacing its hill with a horizontal step (2, 0), that is, Φ(R) = aaR′, where aa encodes a 2-length horizontal step;

2. otherwise, we take into consideration the rightmost hill of R. Therefore, R can be represented as R′xx̄R′′, where R′ is a not empty Schr̈oder path, and R′′ is a hill-free Schröder path. The path Φ(R) is obtained from R by moving the rise step of the hill to the beginning of the path, that is Φ(R) = xR′x̄R′′ □.

The sequences obtained for k = 1, k = 3, k = 4 are not mentioned in Sloane’s Enciclopedia of Integer Sequences [10]:

k  Generating function  First terms of the sequence

1  \frac{1−x+2x^{2}−\sqrt{1−2x−3x^{2}}}{2x^{2}(2−x+x^{2})}  1, 1, 1, 2, 5, 12, 29, 72, 183, 473, 1239, ...
2  \frac{1+x^{2}−\sqrt{1−6x^{2}+x^{4}}}{4x^{2}}  1, 0, 1, 0, 3, 0, 11, 0, 45, 0, 197, 0, 903, 0, 4279, ...
3 \frac{1−x^{3}+2x^{2}−\sqrt{1−2x^{3}+x^{6}−4x^{2}}}{2x^{2}(2+x^{2}−x^{3})}  1, 0, 0, 1, 1, 1, 3, 5, 9, 17, 34, 64, 128, ...
4 \frac{1−x^{4}+2x^{2}+\sqrt{1−2x^{4}+x^{8}−4x^{2}}}{2x^{2}(2+x^{2}−x^{4})}  1, 0, 0, 0, 2, 0, 3, 0, 12, 0, 37, 0, 132, 0, 473, ...
∞  \frac{1+2x^{2}−\sqrt{1−4x^{2}}}{4+2x^{2}}  1, 0, 0, 0, 1, 0, 2, 0, 6, 0, 18, 0, 57, 0, 186, 0, 622, ...

For any fixed k ∈ ℕ and length n, the set of generalized k-Motzkin paths without hills is in bijection with the set of generalized k-Motzkin paths beginning with a horizontal step or having the first peak at even height. This bijection generalizes a result holding for Dyck paths [5]. Let S be a hill-free generalized Motzkin path, the bijection φ works as follows:

1. if S begins with a horizontal step or its first peak has even height, then φ(S) = S;

2. otherwise S can be represented as S = xAx̄B, where A and B are generalized k-Motzkin paths and B has no hills. Therefore, φ(S) = Axx̄B is a generalized Motzkin path having the first peak at even height (see Fig. 3).

The function φ can be trivially inverted.

Figure 3: The bijection between hill-free paths and those whose first peak has even height.

2.1 A linear recurrence for the number of hill-free paths

Equations (3) and (5) yield

M(x) = 2S(x) + x^{2}S(x) − x^{k}S(x) − 1,  (7)

therefore the numbers f_{n} of generalized Motzkin paths and s_{n} of hill-free paths are related by the linear recurrence relation:

f_{n} = 2s_{n} + s_{n−2} − s_{n−k},  n > k.  (8)

We wish to give a proof of (8) in a bijective way. For this purpose, we partition the paths of M_{n} into the following three sets:

1. the first set contains the paths of M_{n} without hills, which are counted by s_{n};

2. the second set contains the paths of M_{n} having exactly one hill, and beginning with such hill. These paths can be obtained from the paths without hills of length n − 2 simply by adding the initial hill. Therefore their number is s_{n−2};

3. the third set contains the remaining paths. We show that their number is s_{n} − s_{n−k} by establishing a bijection with the paths having no hills and not beginning with a horizontal step; a path S of such type can be represented as S = xAx̄B, where A is a non-empty path and B is a path without hills. The path S′ = Axx̄B has at least one hill, but not a unique initial one (see Fig. 4).

Figure 4: The bijection described in step 3.

Example 2 The recurrence relation (8) reduces to f_{n} = 2s_{n}−s_{n−1}+s_{n−2}, n > 1, for Motzkin paths (k = 1). Following the previous argument, for n = 4 we have f_{4} = s_{4} + s_{2} + (s_{4} − s_{3}), being f_{4} = 9 and s_{4} = 5, s_{3} = 2, s_{2} = 1. The corresponding combinatorial interpretation is given in Fig. 5. □

Figure 5: A combinatorial interpretation for f_{n} = 2s_{n} − s_{n−1} + s_{n−2}, n > 1 for n = 4.

3 Eco method and hill-free Dyck paths

The succession rule:

\{ \begin{matrix}(1) \\ (1) ⇝ (2) \\ (2^{h}) ⇝ (1)^{2^{h−1}}(2)^{2^{h−2}}(4)^{2^{h−3}} … (2^{h−2})^{2}(2^{h−1})(2^{h+1}), \end{matrix}  (9)

is equivalent to:

\{ \begin{matrix}(1) \\ (1) ⇝ (2) \\ (h) ⇝ (2)(3)(4) … (h)(h + 1), \end{matrix}  (10)

in the sense that the number of nodes at corresponding levels of their generating trees are Catalan numbers [1]. Instead of proving this equivalence by means of generating functions we show that (9) corresponds to a construction for Dyck paths. Moreover, the number f_{n,h} of labels 2^{h} at level n of the tree we obtain from (9) equals the number of Dyck paths of length 2n and with exactly h hills. The reader can check this property in the following table:

\begin{matrix}n & C_{n} & 2^{0} & 2^{1} & 2^{2} & 2^{3} & 2^{4} & 2^{5} \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 1 & 0 & 0 & 0 \\ 3 & 5 & 2 & 2 & 0 & 1 & 0 & 0 \\ 4 & 14 & 6 & 4 & 3 & 0 & 1 & 0 \\ 5 & 42 & 18 & 13 & 6 & 4 & 0 & 1 \end{matrix}

The infinite lower triangular matrix (f_{n,h})_{n,h≥0} is a Riordan array [9]. We recall that an infinite lower triangular matrix is called Riordan array if its bivariate generating function G(t, z) = ∑ f_{n,h}t^{n}z^{h} has the form G(t, z) = \frac{g(z)}{1−tj(z)}. The Riordan array (f_{n,h})_{n,h≥0} has

been studied in [5]. There G(t, z) = \frac{F (z)}{1−tzF (z)}, with F (z) being the generating function for the Fine numbers. The number sequence defined by the i-th column of (f_{n,h})_{n,h≥0} has x^{i}F (z)^{i+1} as generating function, since each path of length 2n with i hills has the form U_{0}xx̄U_{1}xx̄U_{2} … U_{h−1}xx̄U_{i}, where U_{j}, 0 ≤ j ≤ i is a hill-free path.

Since the number of nodes having label (2^{h}) at level n in the generating tree obtained through (9) is equal to the number of Dyck paths having length 2n and exactly h hills, then it is possible to use ECO method and determine an operator ϑ_{D} which satisfies Proposition 1 and produces 2^{h} Dyck paths from a path having h hills, such that:

- only one path has h + 1 hills;

- for each j = 1, …, h, there are exactly 2^{j−1} paths, having h − j hills,

according to the succession rule (9). In order to determine such a construction, let D be a Dyck path of length 2n and h hills. We can represent it as

D = U_{0}c_{1}U_{1}c_{2}U_{2} … U_{h−2}c_{h−1}U_{h−1}c_{h}U_{h},

where c_{i} = xx̄ denotes the i-th hill and U_{j} is a hill-free Dyck path. The operator ϑ_{D} works on D and produces 2^{h} paths of length 2(n + 1) in the following way (see Fig.6):

1. one Dyck path with h + 1 hills is obtained from D by adding a hill at its end.

2. 2^{j−1} paths with h − j hills, j = 1, …, h are obtained as described below, in agreement with the fact that there are 2^{j−1} combinations from a set of j − 1 elements, i.e.,

2^{j−1} = ∑_{i=0}^{j−1} \binom{j − 1}{i}.

Figure 6: The operator ϑ_{D} applied to a path with three hills, according to (2^{3}) ⇝ (1)(1)(1)(1)(2)(2)(2^{2})(2^{4})

Let j be fixed. We take into consideration the (h − j + 1)-th hill, we add a rise step before c_{h−j+1}, and a fall step at the end of D, thus obtaining a Dyck path D′ of length 2(n + 1) with h − j hills:

D′ = U_{0}c_{1}U_{1}c_{2}U_{2} … U_{h−j}xc_{h−j+1}U_{h−j+1} … c_{h}U_{h}x̄.

For each i = 0, …, j − 1, we consider the ( \begin{matrix}j − 1 \\ i \end{matrix} ) combinations of the j − 1 hills on

the right of c_{h−j+1}, and, for each combination, say c_{l_{1}}, …, c_{l_{i}}, h − j < l_{1} < … < l_{i} ≤ h we modify the path D′ by adding i rise steps before c_{h−j+1}, and replacing each c_{l_{r}}, r = 1, …, i, with a fall step. The path we obtain has h − j hills, and its form is:

U_{0}c_{1}U_{1}c_{2}U_{2} … U_{h−j}x^{i+1}c_{h−j+1}U_{h−j+1} … U_{l_{1}−1}x̄ … U_{l_{i}−1}x̄ … c_{h}U_{h}x̄.

It is easy to verify that ϑ_{D} satisfies Proposition 1, and then it recursively constructs Dyck paths of length 2(n + 1), starting from those of length 2n.

4 A construction for generalized Motzkin paths

In this section we extend the ECO method in order to obtain a construction for generalized Motzkin paths basing on the same method explained in the previous section. Let O be a class of combinatorial objects, and r and s, s ≤ r, positive integers. Let ϑ_{r}, ϑ_{s} be two operators on O:

ϑ_{s} : O_{n} → 2^{O_{n+s}}, ϑ_{r} : O_{n} → 2^{O_{n+r}},

and:

∀O, O′ ∈ O_{n}, O ≠ O′ ϑ_{s}(O) ∩ ϑ_{s}(O′) = ∅, ϑ_{r}(O) ∩ ϑ_{r}(O′) = ∅.

Moreover, let ϑ be an operator on O:

ϑ : O_{n} → 2^{O_{n+s}∪O_{n+r}}.

We say that ϑ is the direct sum of ϑ_{s} and ϑ_{r}, and write ϑ = ϑ_{s} ⊕ ϑ_{r}, if

1. ∀O ∈ O_{n}, ϑ(O) = ϑ_{s}(O) ∪ ϑ_{r}(O);

2. ∀O ∈ O_{n}, ϑ_{s}(O) ∩ ϑ_{r}(O) = ∅;

3. ∀O ∈ O_{n−r}, ∀O′ ∈ O_{n−s}, ϑ_{r}(O) ∩ ϑ_{s}(O′) = ∅.

If the above conditions are satisfied, and

∀O′ ∈ O_{n} ∃O ∈ O_{n−r} ∪ O_{n−s} such that O′ ∈ ϑ(O) n > r,

then the set

{ϑ_{s}(O), ϑ_{r}(O′) : O ∈ O_{n−s}, O′ ∈ O_{n−r}}, n ≥ r,

is a partition of O_{n}. The generating tree associated to ϑ_{s} ⊕ ϑ_{r} is a rooted tree whose edges can have length s or r. The level l(N) of a node N in the generating tree is defined as follows:

1. l(N) = 0, if N is the root of the tree;

2. otherwise, let F be the father of N, in the tree, and w be the length of the branch joininig F to N: then l(N) = l(F) + w.

In this generating tree the objects having the same value of the parameter lie at the same level, and the sons of each node at level n are the objects it produces through ϑ_{s} (lying on level n+s), and the ones it produces through ϑ_{r} (lying on level n+r). Therefore a succession rule describing that generating tree has the form:

\{ \begin{matrix}(b) \\ (h) & ⇝^{s} & (e_{1}(h)) … (e_{g}(h)) \\ & ⇝^{r} & (e_{g+1}(h)) … (e_{h}(h)). \end{matrix}  (11)

Such a succession rule defines a number sequence {f_{n}}_{n}, f_{n} being the total number of nodes at level n in the associated generating tree.

Let us consider the following succession rule:

Ω_{k} \{ \begin{matrix}(2) \\ (2^{h}) & ⇝^{2} & (2)^{2^{h−2}}(4)^{2^{h−3}}(8)^{2^{h−4}} … (2^{h−2})^{2}(2^{h−1})(2^{h+1}) \\ & ⇝^{k} & (2)^{2^{h−2}}(4)^{2^{h−3}}(8)^{2^{h−4}} … (2^{h−2})^{2}(2^{h−1})(2^{h}). \end{matrix}  (12)

Figure 7 shows the first levels of the generating tree associated to the succession rule Ω_{1}, which gives the Motzkin numbers.

We define an ECO operator ϑ which constructs generalized Motzkin paths according to their length, and follows the succession rule Ω_{k}. Each path having exactly h hills produces exactly 2^{h+1} paths through ϑ. As a neat consequence of this fact we have a combinatorial proof that the number of labels 2^{h+1}, h ≥ 0, at level n in the generating tree associated to Ω_{k} is equal to the number of generalized Motzkin paths of length n with exactly h hills. The operator

ϑ : O_{n} → 2^{O_{n+2}∪O_{n+k}},

is the direct sum of two ECO operators:

Figure 7: The first levels of the generating tree associated to Ω_{1}.

ϑ : ϑ_{D} ⊕ ϑ_{k}.

The first operator, namely ϑ_{D}, works on Motzkin paths exactly like the operator defined in the previous section for Dyck paths, however, now with edges of length 2. More precisely, if M is a generalized Motzkin path of length n having exactly h hills, then ϑ_{D}(M) is a set of 2^{h} paths of length n + 2. On the other side, ϑ_{k}(M) is a set of 2^{h} paths of length n + k, such that:

1. one path is obtained from M by adding a horizontal step at the end of M;

2. for j = 1, …, h we consider the (h − j)-th hill of M, namely c_{h−j+1}:

M = U_{0}c_{1}U_{1}c_{2} … U_{h−j}c_{h−j+1}U_{h−j+1} … c_{h}U_{h},

where the U_{i} are hill-free paths, and the c_{i} are hills. We add a rise step before c_{h−j+1} and a fall step at the end of the path, then replace c_{h−j+1} with a horizontal step. The (n + k)-length obtained path, which we call M′, has exactly h − j hills.

M′ = U_{0}c_{1}U_{1}c_{2} … U_{h−j}xa^{k}U_{h−j+1} … c_{h}U_{h}x̄,

where a^{k} encodes the horizontal step. For i = 0, 1, …, j − 1, we consider the j − 1 hills (i.e., xx̄ pairs that were hills on M) on the right of the added horizontal step. For each of these combinations, say

c_{l_{1}}, …, c_{l_{i}}, h − j < l_{1} < … < l_{i} ≤ h,

we have a path, obtained from M′ by adding i rise steps before the added horizontal step, and replacing each c_{l_{t}}, t = 1, …, i with a fall step:

U_{0}c_{1}U_{1}c_{2} … U_{h−j}x^{i+1}e^{k}U_{h−j+1} … x̄U_{l_{1}} … x̄U_{l_{1}} … c_{h}U_{h}x̄.

Performing these operations, each j gives

∑_{i=0}^{j−1} \binom{j − 1}{i} = 2^{j−1}

paths, each of them having h − j hills. Figure 8 shows the application of ϑ to a path having two hills, k = 3.

Figure 8: The application of ϑ to a path having 2 hills, k = 3.

Example 3 For k = 1, we have the succession rule:

\{ \begin{matrix}(2) \\ (2^{h}) & ⇝^{1} & (2)^{2^{h−2}}(4)^{2^{h−3}}(8)^{2^{h−4}} … (2^{h−2})^{2}(2^{h−1})(2^{h}) \\ & ⇝^{2} & (2)^{2^{h−2}}(4)^{2^{h−3}}(8)^{2^{h−4}} … (2^{h−2})^{2}(2^{h−1})(2^{h+1}) \end{matrix}  (13)

defining the Motzkin numbers. Let f_{n,h} be the number of nodes having label (2^{h}) at level n in the generating tree of the rule in (13). The array (f_{n,h})_{n,h≥0}, is a Riordan array:

\begin{matrix}n & 2^{1} & 2^{2} & 2^{3} & 2^{4} \\ 1 & 1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 \\ 4 & 2 & 2 & 0 & 0 \\ 5 & 5 & 3 & 1 & 0 \\ 6 & 12 & 6 & 3 & 0 \end{matrix}

The number of labels (2^{h+1}) at level n is the number of Motzkin paths having length n and exactly h hills. □

Example 4 For k = 2, the succession rule form (12) simplifies to:

\{ \begin{matrix}(2) \\ (2^{h}) ⇝ (2)^{2^{h−1}}(4)^{2^{h−2}}(8)^{2^{h−3}} … (2^{h−1})^{2}(2^{h})(2^{h+1}), \end{matrix}  (14)

defining the Schröder numbers. As in Example 3, let f_{n,h} be the number of nodes having label (2^{h}) at level n in the generating tree of the rule in (14). The array (f_{n,h})_{n,h≥0}, is a Riordan array:

\begin{matrix}n & 2^{1} & 2^{2} & 2^{3} & 2^{4} & 2^{5} \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 0 \\ 3 & 3 & 2 & 1 & 0 & 0 \\ 4 & 11 & 7 & 3 & 1 & 0 \\ 5 & 45 & 28 & 12 & 4 & 1 \end{matrix}

The number of labels (2^{h+1}) at level n is the number of Schröder paths having length 2n and exactly h hills. □

Example 5 For k = 4, we have the succession rule:

\{ \begin{matrix}(2) \\ (2^{h}) & ⇝^{2} & (2)^{2^{h−2}}(4)^{2^{h−3}}(8)^{2^{h−4}} … (2^{h−2})^{2}(2^{h−1})(2^{h+1}) \\ & ⇝^{1} & (2)^{2^{h−2}}(4)^{2^{h−3}}(8)^{2^{h−4}} … (2^{h−2})^{2}(2^{h−1})(2^{h}) \end{matrix}  (15)

Let us now fill up a table with the numbers f_{n,h}, where as usual f_{n,h} denotes the number of nodes having label (2^{h}) at level n in the generating tree of this rule. The array (f_{n,h})_{n,h≥0}, is again a Riordan array:

\begin{matrix}n & 2^{1} & 2^{2} & 2^{3} & 2^{4} & 2^{5} \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 1 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 \\ 5 & 1 & 0 & 1 & 0 & 0 \\ 6 & 1 & 2 & 0 & 0 & 0 \\ 7 & 3 & 2 & 0 & 1 & 0 \\ 8 & 5 & 2 & 2 & 0 & 0 \end{matrix}

References

[1] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani, ECO: a methodology for the Enumeration of Combinatorial Objects, Journal of Difference Equations and Applications, Vol.5 (1999) 435-490.

[2] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, M. Kleimann, The number of Baxter permutations, Journal of Combinatorial Theory Ser. A, 24 (1978) 382-394.

[3] E. Deutsch, An involution on Dyck paths and its consequences, Discrete Mathematics, 204 (1999) 163-166.

[4] E. Deutsch, Dyck path enumeration, Discrete Mathematics, 204 (1999) 167-202.

[5] E. Deutsch, L. Shapiro, A survey of the Fine numbers, (preprint).

[6] T. Fine, Extrapolation when very little is known about the source, Inform. and Control, 16 (1970) 331-359.

[7] D. G. Rogers, L. Shapiro, Deques, trees and lattice paths, Lecture Notes in Mathematics, Vol.884, Springer-Verlag, New York Heidelberg Berlin (1981) 293-303.

[8] L. Shapiro, A Catalan triangle, Discrete Mathemathics, 14 (1976) 83-90.

[9] L. Shapiro, S. Getu, W-J. Woan, L. C. Woodson, The Riordan group, Discrete Applied Mathemathics, 34 (1991) 229-239.

[10] N. J. A. Sloane, S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York (1995).