Dyck Paths, Motzkin Paths, and the Binomial Transform

Stefano Capparelli and Alberto Del Fra Dept SBAI Università di Roma La Sapienza Italy

                stefano.capparelli@uniroma1.it
                  alberto.delfra@uniroma1.it

Abstract We study the moments of orthogonal polynomial sequences (OPS) arising from tridiagonal matrices. We obtain combinatorial information about the sequence of moments of some OPS in terms of Motzkin and Dyck paths, and also in terms of the binomial transform. We then introduce an equivalence relation on the set of Dyck paths and some operations on them. We determine a formula for the cardinality of those equivalence classes, and use this information to obtain a combinatorial formula for the number of Dyck and Motzkin paths of a fixed length.

1 Introduction and preliminaries

In the papers [2] and [3] the first author studied certain combinatorial properties of orthogonal polynomial sequences arising from special matrices. Savo [10] used some results of [2]. Here we systematically study the sequence of moments arising from a generalization of the matrices studied there.

We use a combinatorial interpretation of the action of the binomial transform on the sequence of moments of orthogonal polynomials arising from a tridiagonal matrix to obtain relations that tie together different well-known sequences of integers.

We also obtain a recursive formula for the moments.

The object of our study is also the set of Dyck paths. We introduce an equivalence relation on the set of Dyck paths, we compute the cardinality of the equivalence classes and use this information to give a combinatorial formula for the number of Dyck and Motzkin paths of a fixed length.

We recall the definition of orthogonal polynomial sequence (OPS) [5]. Let (μ_{n})_{μ=0}^{∞} be a sequence of complex numbers and L the complex valued linear functional defined on the vector space of polynomials ℂ[x] by

L(x^{n}) = μ_{n}, n = 0, 1, 2, …  (1)

The functional L is called the moment functional, (μ_{n}) the moment sequence, and the number μ_{n} the moment of order n. A sequence (P_{n}(x))_{n=0}^{∞} is called an orthogonal polynomial sequence with respect to L if the following conditions hold for all nonnegative integers m and n:

1. P_{n}(x) is a polynomial of degree n,

2. L(P_{m}(x)P_{n}(x)) = 0 for m ≠ n,

3. L(P_{n}^{2}(x)) ≠ 0.

The following is a well known result [5]:

Theorem 1. The sequence of monic polynomials (P_{n}(x))_{n=0}^{∞} is an orthogonal polynomial sequence if and only if there exist two sequences (h_{n})_{n=1}^{∞} and (u_{n})_{n=1}^{∞} such that the following recurrence holds:

\begin{matrix}P_{n}(x) = (x − h_{n})P_{n−1}(x) − u_{n}P_{n−2}(x), n = 1, 2, 3, … \\ P_{−1}(x) = 0, P_{0}(x) = 1. \end{matrix}  (2)

We will be interested in the moment sequence. One way to compute the moment sequence of a monic OPS is the following, cf. [12, 11]. Consider the infinite matrix A whose n-th row is formed by taking the coefficients of the n-th (monic) polynomial of the OPS so that the entry a_{nk} is the coefficient of x^{k} of the polynomial. Since a_{nn} = 1, this is an infinite matrix with 1 on the main diagonal. We then consider the sequence of the leading principal minors, namely the submatrices obtained by taking the first n rows and the first n columns of this infinite matrix. These are all invertible matrices. Consider the sequence of the inverse matrices: these are the leading principal minors of the infinite matrix A^{−1}. The sequence of the first column in A^{−1} is the required moment sequence.

2 A recursive formula for moments

Definition 2. A Motzkin path of length n is a path on the integral lattice ℤ × ℤ starting from (0, 0) and ending in (k, 0) using n steps according to the vectors (1, 1), (1, 0), (1, −1) and never going below the x-axis, [1].

Definition 3. A Motzkin path with no (1, 0) steps is called a Dyck path, [6].

There is a close relationship between the moment of order n and the number of Motzkin paths suitably weighted (or “colored”). We will examine some special cases and draw some interesting conclusions.

Given three sequences

(h_{0}, h_{1}, h_{2}, …), (u_{0}, u_{1}, u_{2}, …), (d_{0}, d_{1}, d_{2}, …)

we may consider colored Motzkin paths where, for any index i, h_{i} is the number of colors of the horizontal step at level i, u_{i} is the number of colors of the up step starting from level i, d_{i} is the number of colors of the down step arriving at level i. For example,

[figure: h_{0}; u_{0}; h_{1}; u_{1}; h_{2}; d_{1}; h_{1}; d_{0}; h_{0}; u_{0}; h_{1}; d_{0}]

On the other hand one may consider the infinite tridiagonal matrix

(\begin{matrix}h_{0} & u_{0} & 0 & 0 & 0 & 0 & … \\ d_{0} & h_{1} & u_{1} & 0 & 0 & 0 & … \\ 0 & d_{1} & h_{2} & u_{2} & 0 & 0 & … \\ 0 & 0 & d_{2} & h_{3} & u_{3} & 0 & … \\ … & … & … & … & … & … & … \end{matrix})  (3)

and the sequence of the leading principal minors of order n = 1, 2, 3, . . .. For each such minor we may compute the monic characteristic polynomial. It is well known that the sequence of polynomials thus obtained is an OPS. Notice that the same sequence of polynomials is obtained if we consider the matrix

(\begin{matrix}h_{0} & u_{0}d_{0} & 0 & 0 & 0 & 0 & … \\ 1 & h_{1} & u_{1}d_{1} & 0 & 0 & 0 & … \\ 0 & 1 & h_{2} & u_{2}d_{2} & 0 & 0 & … \\ 0 & 0 & 1 & h_{3} & u_{3}d_{3} & 0 & … \\ … & … & … & … & … & … & … \end{matrix})  (4)

hence in this section we may assume, without loss of generality, that d_{i} = 1 for all i.

Let μ_{n} be the moments of this sequence of orthogonal polynomials. As a consequence of a theorem of Flajolet [7] (also see [12] and [11]), we have

Theorem 4. The element μ_{n} of the moment sequence (μ_{0}, μ_{1}, μ_{2}, …) determined by the matrix (3) counts the number of Motzkin paths of length n colored with h_{i}, u_{i}, d_{i}, i = 0, 1, 2, … We want to study the special case where h_{i} = h, u_{i} = u are constant sequences:

T = (\begin{matrix}h & u & 0 & 0 & 0 & 0 & … \\ 1 & h & u & 0 & 0 & 0 & … \\ 0 & 1 & h & u & 0 & 0 & … \\ 0 & 0 & 1 & h & u & 0 & … \\ … & … & … & … & … & … & … \end{matrix})  (5)

A formula for the moment sequence in this case is well known:

μ_{n} = ∑_{i≥0} C_{i}\binom{n}{2i}h^{n−2i}u^{i}  (6)

and C_{i} = \frac{1}{i+1} \binom{2i}{i} is the i-th term of the Catalan sequence. We wish to obtain a recurrence for this sequence.

We shall need the following general property of matrices:

Proposition 5. Let A = (a_{ij}), i, j = 0, …, n be a unipotent (n+1)×(n+1) lower triangular matrix, and let B be the matrix obtained by erasing the first row and the last column of A:

B = (\begin{matrix}a_{10} & 1 & 0 & ⋯ & 0 \\ a_{20} & a_{21} & 1 & ⋯ & 0 \\ ⋯ & ⋯ & ⋯ & ... & ⋯ \\ a_{n−1,0} & a_{n−1,1} & a_{n−1,2} & ⋯ & 1 \\ a_{n0} & a_{n1} & a_{n2} & ⋯ & a_{n,n−1} \end{matrix})

Let α_{ij} denote the cofactor in A of the element a_{ij}, and set P_{0} = 1, P_{i}, 1 ≤ i ≤ n − 1, the determinant of the leading principal minor of B of order i. Then α_{00} = 1 = P_{0}, α_{01} = −P_{1}, α_{02} = P_{2}, α_{03} = −P_{3}, …, α_{0n} = (−1)^{n}P_{n}. Moreover,

det B = P_{n} = ∑_{i=0}^{n−1} a_{ni}(−1)^{n+i−1}P_{i}  (7)

Lemma 6. Consider the matrix A = (a_{st}) formed by the coefficients of the characteristic polynomials

p_{n}(x) = a_{n0} + a_{n1}x + ⋯ + a_{n,n−1}x^{n−1} + x^{n}  (8)

of the leading principal minor of order n of the tridiagonal matrix (5). Its entries are, for s, t ∈ {0, 1, 2, …},

a_{st} = ∑_{j=0}^{s}(−1)^{s−t−j}\binom{s − j}{j + t}\binom{j + t}{t}h^{s−t−2j}u^{j}  (9)

Proof. To prove this formula we recall that the characteristic polynomials form an OPS and therefore satisfy the recurrence (2) with h_{n} = h and u_{n} = u, for all n. Hence we may proceed by induction as follows.

Define

p_{n}(x) = a_{n0} + a_{n1}x + ⋯ + a_{n,n−1}x^{n−1} + x^{n}  (10)

to be the monic characteristic polynomial of the n × n tridiagonal matrix (5). It is straightforward, using (2), to check that the coefficients of p_{n}(x) are related to the coefficients of p_{n−1}(x) and p_{n−2}(x) as follows:

a_{n0} = −ua_{n−2,0} − ha_{n−1,0} ; a_{n1} = −ua_{n−2,1} + a_{n−1,0} − ha_{n−1,1} ; a_{n2} = −ua_{n−2,2} + a_{n−1,1} − ha_{n−1,2} ; ⋮ ; a_{n,n−2} = −ua_{n−2,n−2} + a_{n−1,n−3} − ha_{n−1,n−2} ; a_{n,n−1} = a_{n−1,n−2} − h ; a_{nn} = 1  (11)

Now assume that (9) holds for s up to n − 1.

For t = 0 we have

\begin{matrix}a_{n,0} = −ua_{n−2,0} − ha_{n−1,0} \\ = −u ∑_{j≥0}(−1)^{n−2−j}\binom{n − 2 − j}{j}h^{n−2−2j}u^{j} − h ∑_{j≥0}(−1)^{n−1−j}\binom{n − 1 − j}{j}h^{n−1−2j}u^{j} \\ = ∑_{j≥1}(−1)^{n−j}\binom{n − 1 − j}{j − 1}h^{n−2j}u^{j} + ∑_{j≥0}(−1)^{n−j}\binom{n − 1 − j}{j}h^{n−2j}u^{j} \\ = (−1)^{n}\binom{n}{0}h^{n} + ∑_{j≥1}(−1)^{n−j}\binom{n − j}{j}h^{n−2j}u^{j} \\ = ∑_{j≥0}(−1)^{n−j}\binom{n − j}{j}h^{n−2j}u^{j} \end{matrix}  (12)

For 1 ≤ t ≤ n − 2 we have

a_{n,t} = −ua_{n−2,t} + a_{n−1,t−1} − ha_{n−1,t}

= −u ∑_{j≥0}(−1)^{n−2−t−j}\binom{n − 2 − j}{j + t}\binom{j + t}{t}h^{n−2−t−2j}u^{j}

+ ∑_{j≥0}(−1)^{n−t−j}\binom{n − 1 − j}{j + t − 1}\binom{j + t − 1}{t − 1}h^{n−t−2j}u^{j}

− h ∑_{j≥0}(−1)^{n−1−t−j}\binom{n − 1 − j}{j + t}\binom{j + t}{t}h^{n−1−t−2j}u^{j}

= ∑_{j≥1}(−1)^{n−t−j}\binom{n − 1 − j}{j + t − 1}\binom{j + t − 1}{t}h^{n−t−2j}u^{j}

+ ∑_{j≥0}(−1)^{n−t−j}\binom{n − 1 − j}{j + t − 1}\binom{j + t − 1}{t − 1}h^{n−t−2j}u^{j}

+ ∑_{j≥0}(−1)^{n−t−j}\binom{n − 1 − j}{j + t}\binom{j + t}{t}h^{n−t−2j}u^{j}

The terms for j ≥ 1 in the first two summations can be added using the Stiefel formula

= ∑_{j≥1}(−1)^{n−t−j}\binom{n − 1 − j}{j + t − 1}\binom{j + t}{t}h^{n−t−2j}u^{j}

+ ∑_{j≥1}(−1)^{n−t−j}\binom{n − 1 − j}{j + t}\binom{j + t}{t}h^{n−t−2j}u^{j}

+ (−1)^{n−t}\binom{n − 1}{t − 1}h^{n−t} + (−1)^{n−t}\binom{n − 1}{t}h^{n−t}

and applying Stiefel’s formula again we get

\begin{matrix}= (−1)^{n−t}\binom{n}{t}h^{n−t} + ∑_{j≥1}(−1)^{n−t−j}\binom{n − j}{j + t}\binom{j + t}{t}h^{n−t−2j}u^{j} \\ = ∑_{j≥0}(−1)^{n−t−j}\binom{n − j}{j + t}\binom{j + t}{t}h^{n−t−2j}u^{j} \end{matrix}

as required.

Finally, case t = n − 1:

\begin{aligned}a_{n,n−1} & = −h + a_{n−1,n−2} \\ & = −h + ∑_{j≥0}(−1)^{1−j}\binom{n − 1 − j}{n + j − 2}\binom{n + j − 2}{n − 2}h^{1−2j}u^{j} \end{aligned}  (13)

In the summation the only nonzero term is the one with j = 0 and we have

−h − \binom{n − 1}{n − 2}h = −nh  (14)

as required.

Proposition 7. The sequence of moments (μ_{n}) corresponding to the matrix (5) satisfies the following recursive formula: μ_{0} = 1 and, for n ≥ 1,

μ_{n} = ∑_{i=0}^{n−1} a_{ni}(−1)^{n+i}μ_{i}  (15)

where

a_{ni} = ∑_{j=0}^{n}(−1)^{n−i−j}\binom{n − j}{j + i}\binom{j + i}{i}h^{n−i−2j}u^{j}

Proof. Consider the matrix A formed by the coefficients of the characteristic polynomials of the leading principal minors of the tridiagonal matrix (5). Lemma 6 implies that its entries are, for s, t ∈ {0, 1, 2, …},

a_{st} = ∑_{j=0}^{s}(−1)^{s−t−j}\binom{s − j}{j + t}\binom{j + t}{t}h^{s−t−2j}u^{j}.

The moments are computed by taking the first column of the inverse matrix of A. When computing an inverse matrix one must compute the cofactors. We are interested, in particular, in the cofactors of the first row (those that give the first column of the inverse matrix). Since A is lower triangular with 1 on the main diagonal we may use Proposition 5. We then have

μ_{n} = α_{0n},

and by (7) we have the conclusion.

3 The binomial transform

We recall the definition of binomial transform [8]:

Definition 8. Given a sequence of integers (a_{n})_{n≥0} one defines its binomial transform to be the sequence (s_{n}) = T ((a_{n})) defined by

s_{n} = ∑_{h=0}^{n} \binom{n}{h}a_{h}

Example 9. If a_{n} = 1 for all n, then s_{n} = 2^{n}.

The operator T is invertible. The inverse binomial transform is given by the formula

a_{n} = ∑_{h=0}^{n}(−1)^{n−h}\binom{n}{h}s_{h}

The following nice result is well known and easy to prove:

Proposition 10. The binomial transform of the moment sequence of (3) is the moment sequence of

(\begin{matrix}h_{0} + 1 & u_{0} & 0 & 0 & … \\ d_{0} & h_{1} + 1 & u_{1} & 0 & … \\ 0 & d_{1} & h_{2} + 1 & u_{2} & … \\ 0 & 0 & d_{2} & h_{3} + 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )  (16)

Proof. To compute s_{n}, we choose k ≤ n horizontal steps to be colored with the new color. This can be done in \binom{n}{k} ways. Once we remove these k horizontal steps, we get Motzkin paths with the old colors. There are a_{n−k} such paths. Therefore

s_{n} = ∑_{k=0}^{n} \binom{n}{k}a_{n−k} = ∑_{k=0}^{n} \binom{n}{n − k}a_{k} = ∑_{k=0}^{n} \binom{n}{k}a_{k}

One may use this theorem to obtain a relation between different integer sequences.

Consider all the sequences of moments that can be obtained starting from two parameters (h, u) as follows:

μ : ℝ × ℝ → ℝ^{ℕ}

defined by associating with every pair of real numbers (h, u) the sequence of moments of the tridiagonal matrices (5), hence

(h, u) ↦ μ[h, u] = (μ_{n} = μ_{n}[h, u])  (17)

where μ_{n} = ∑_{i≥0} C_{i}\binom{n}{2i}h^{n−2i}u^{i} and C_{i} = \frac{1}{i+1} \binom{2i}{i} is the i-th term of the Catalan sequence (cf. (6)).

Define the multiplication of a scalar k ∈ ℝ and a sequence (μ_{n})_{n≥0} to mean the sequence (k^{\frac{n}{2}} μ_{n})_{n≥0}.

Proposition 11. For h, h′ ∈ ℕ, u, u′ ∈ ℝ_{+}, the following formula holds

T^{h′} (\frac{u′}{u} ) T^{−h}μ[h, u] = μ[h′, u′]  (18)

Proof. By applying the inverse binomial transform T^{−1} h times to the sequence μ[h, u] one gets the sequence μ[0, u] which counts Dyck paths. Then, by multiplying this sequence by \frac{u′}{u}, we suitably color the up steps, thus obtaining μ[0, u′]. Finally, by applying T^{h′} we obtain the sequence μ[h′, u′].

This formula allows one to relate the sequence of numbers of Motzkin paths of length n with weights h, u with the analogous sequence with weights h′, u′. For example, the sequence μ[2, 2] = (1, 2, 6, 20, 72, 272, …) counts Motzkin paths where the up and horizontal steps have two fixed colors. Computing T^{−2} we get the sequence μ[0, 2] = (1, 0, 2, 0, 8, 0, 40, 0, …) which counts Dyck paths with two-colored up step. Divide the sequence by 2 thus obtaining the sequence counting Dyck paths with a single color. Now multiply by 3 and finally apply T . The result is the sequence T (\frac{3}{2}) T^{−2}μ[2, 2] = μ[1, 3] = (1, 1, 4, 10, 37, 121, …) counting Motzkin paths whose up step has 3 colors and the horizontal steps a single color. Explicitly we have the following formula

μ_{n}[1, 3] = ∑_{k=0}^{n} \binom{n}{k} (\frac{3}{2})^{\frac{k}{2}} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j} ∑_{i=0}^{j}(−1)^{j−i}\binom{j}{i}μ_{i}[2, 2]  (19)

or

μ_{n}[1, 3] = ∑_{k=0}^{n} ∑_{j=0}^{k} ∑_{i=0}^{j} \binom{n}{k}\binom{k}{j}\binom{j}{i} (\frac{3}{2})^{\frac{k}{2}} (−1)^{k−i}μ_{i}[2, 2]  (20)

Remark 12. μ[1, 2] is the sequence \underline{A025235} in [9]. This is presented there, for example, with the formula

∑_{h=0}^{n} \binom{n}{h}2^{h/2}C_{h/2} \frac{1 + (−1)^{h}}{2} ,  (21)

where C_{n} is the n-th Catalan number. From our point of view, this formula is an example of our proposition relating μ[1, 2] and μ[0, 2]. This last one is the sequence \underline{A151374} in [9].

4 Frames of Dyck paths

Here we want to study the structure of the set of Dyck paths. This will also allow us to give a combinatorial formula that counts Dyck and Motzkin paths.

First, we wish to classify Dyck paths according to the number of feet at each level, defining a foot at level k to be a point where the path touches level k. The well known formula for the Catalan numbers:

C(n) = ∑_{k=0}^{n−1} C(n − 1 − k)C(k).  (22)

suggests that any length 2n Dyck path can be obtained by a combination of two operations. The first operation consists in adding to each path of length 2(n − 1 − k) an up step at the beginning and a down step at the end. We call this operation lifting. The second operation consists in gluing at the end of it any path of length 2k, k = 0, …, n − 1.

Next, we observe that every Dyck path is obtained by a sequence of up and down steps, indicated by U and D, respectively, in such a way that the total number of U’s is equal to the number of D’s and that at each step the number of U’s be not less than the number of D’s. Let’s associate with each U the number 1 and to each D the number −1. Starting from 0, let’s sum at each step the numbers 1 and −1 up to that point. For a length 2n path, the associated sequence thus obtained starts and ends with 0 and the maximum number appearing is at most n. For each integer i ≥ 0, let p(i) denote the number of times that i appears in the sequence; we shall say that the path is p(i)-ped at the level i. As an example, the length 14 path UUDUUDDUUDUDDD has the associated sequence 012123212323210 which is simply the sequence of the y coordinate of the points touched by the path. The path is therefore biped at level 0, quadruped at level 1, 6-ped at level 2, 3-ped at level 3, 0-ped at higher levels. We may sometimes identify a path with its associated sequence.

For our purposes, we need to know the number of Dyck paths that have a fixed “frame” (i_{0}, i_{1}, …), according to the definition we are about to give.

Given a Dyck path D, with i_{k} feet at level k, k = 0, 1, …, we call the sequence (i_{0}, i_{1}, …), which is zero from a certain index on, the frame of D. In other words, the sequence tells us how many feet there are at each level. This sequence is zero from a certain index on, since, if the length of D is 2n, one has i_{n+j} = 0, for j ≥ 1, namely, the maximum reachable level for a Dyck path of length 2n is n.

Given an eventually zero sequence I = (i_{0}, i_{1}, …), we shall call the integer −1 + ∑_{k=0}^{∞} i_{k} the length of I .

We shall say that an eventually zero sequence is admissible if it is the frame of some Dyck path. For an admissible frame I, its length is the same as the length of a path with that frame and is necessarily even.

For example, frames of Dyck paths of length 0,2,4 are, respectively:

• (1, 0, 0, …),

• (2, 1, 0, …),

• (2, 2, 1, 0, …), (3, 2, 0, …).

Notice that two distinct paths with the same length may have the same frame. For example, the two paths

have the same frame (3, 3, 1, 0, 0, …).

Obviously, “having the same frame” is an equivalence relation on the set of Dyck paths. Notice that lifting two equivalent paths we still get two equivalent paths. This is true also if we glue together two paths: if p_{i} is equivalent to q_{i}, i = 1, 2, then gluing p_{1} and p_{2} gives a path that is equivalent to gluing q_{1} and q_{2}. This observation allows us to speak of lifting a frame and gluing two frames.

It is easy to construct recursively the frames associated with Dyck paths of various lengths, using the same recursive law as for the paths.

Lifting the frame (i_{0}, i_{1}, i_{2}, …) one gets the frame (2, i_{0}, i_{1}, i_{2}, …). While gluing two frames (j_{0}, j_{1}, j_{2}, …) and (i_{0}, i_{1}, i_{2}, …), we get a frame (i_{0} + j_{0} − 1, i_{1} + j_{1}, i_{2} + j_{2}, …).

For the lifting and gluing operations we shall use the following symbols:

s(i_{0}, i_{1}, i_{2}, …) = (2, i_{0}, i_{1}, i_{2}, …),
(i_{0}, i_{1}, i_{2}, …) ∧ (j_{0}, j_{1}, j_{2}, …) = (i_{0} + j_{0} − 1, i_{1} + j_{1}, i_{2} + j_{2}, …)

It is not difficult to check, for example, that the frames with length 4 can be obtained in this fashion from those with shorter lengths.

The gluing operation on paths is associative but not commutative: in general, u ∧ v ≠ v ∧ u. The same operation on frames however is commutative, namely, u ∧ v and v ∧ u have the same frame.

Actually, any frame can be obtained by the combination of two elementary operations: lifting of frame (i_{0}, i_{1}, i_{2}, …), which turns (i_{0}, i_{1}, i_{2}, …) into s(i_{0}, i_{1}, i_{2}, …) = (2, i_{0}, i_{1}, i_{2}, …) and the gluing (i_{0}, i_{1}, i_{2}, …) to the frame of length 2, which we call extension, that turns (i_{0}, i_{1}, i_{2}, …) into a(i_{0}, i_{1}, i_{2}, …) = (i_{0}, i_{1}, i_{2}, …)∧(2, 1, 0, …) = (i_{0}+1, i_{1}+1, i_{2}, …). Indeed, we have:

Theorem 13. Every frame can be obtained by a combination of a lifting and a suitable number of extensions.

Proof. Consider any path U ⋯ D that is not a lifting, i.e., with a frame starting with i_{0} ≥ 3. It follows that its sequence is of the form 01 ⋯ 101 ⋯ 10, with at least one subsequence 101 inside. The first triple 101 inside comes from an ordered pair DU. If we eliminate such a pair inside and add instead the pair UD at the end of the frame, we get a new path with the same frame as the previous one. Iterating such a procedure we get a Dyck path with the same frame as the starting path obtained by gluing a lifting of a suitable path and a finite number, possibly zero, of length 2 paths.

Theorem 14. The number of frames of length 2n, with n > 0, is 2^{n−1}.

Proof. The frames of length 2n are obtained from those of length 2(n − 1) by constructing for each of them, say I, the lifting s(I) or the extension a(I). The frame s(I) is different from a(I) if n > 1. It follows that the number of frames with length 2n is twice the number of the frames of length 2(n − 1).

Natural generalizations of the extension a and lifting s operations can be defined on any sequence of integers eventually zero. The operation a is a bijection on the set of such sequences. Its inverse operation b is defined by:

b(i_{0}, i_{1}, i_{2}, …) = (i_{0} − 1, i_{1} − 1, i_{2}, …).

The operation s is injective and can be inverted on its image, via an operation r defined by:

r(2, i_{1}, i_{2}, …) = (i_{1}, i_{2}, …).

It is easy to see if a given sequence, which is eventually zero, is admissible. Indeed, we can, starting from it, trace back the elementary steps that generated it from the basic frame (1, 0, 0, …). The rules can be summed up as follows: every time there is a 2 we erase it by using r, otherwise we subtract 1 from the first two elements, by applying b.

Example 15. Consider the sequence (3, 6, 6, 3, 1, 0, …). We wish to see if it is admissible for a path of length 18 = 3+6+6+3+1−1. Tracing backwards we have : (2, 5, 6, 3, 1, 0, …), (5, 6, 3, 1, 0, …), (4, 5, 3, 1, 0, …), (3, 4, 3, 1, 0, …), (2, 3, 3, 1, 0, …), (3, 3, 1, 0, …), (2, 2, 1, 0, …), (2, 1, 0, …), finally (1, 0, …). So the given sequence is admissible. Example 16. If we take (4, 5, 2, 3, 1, 0, …), and we trace backwards, we get:

(3, 4, 2, 3, 1, 0, …), (2, 3, 2, 3, 1, 0, …), (3, 2, 3, 1, 0, …), (2, 1, 3, 1, 0, …), (1, 3, 1, 0, …),

and finally (0, 2, 1, 0, …), which is clearly not admissible since there are no Dyck paths of length 2 without feet at the zero level.

In the preceding arguments, we have implicitly used the following two lemmas whose proof is straightforward: Lemma 17. Given an eventually zero integer sequence I, with i_{0} = 2, r(I) is admissible if and only if I is. Lemma 18. Given an eventually zero integer sequence I, with i_{0} ≠ 2, b(I) is admissible if and only if I is.

Given an eventually zero integer sequence (i_{0}, i_{1}, i_{2}, …), let i_{f} denote the last nonzero element and call f the degree of the frame. Theorem 19. An eventually zero sequence of nonnegative integers

I = (i_{0}, i_{1}, …, i_{f}, 0, …),

with length 2n, is admissible if and only if the following conditions are satisfied:

• i_{0} = 1, if f = 0 and i_{0} ≥ 2 if f > 0;

• i_{1} − i_{0} ≥ 0 provided f > 1;

• i_{2} − i_{1} + i_{0} ≥ 2;

• i_{3} − i_{2} + i_{1} − i_{0} ≥ 0;

• i_{4} − i_{3} + i_{2} − i_{1} + i_{0} ≥ 2;

• ⋯

• i_{f} − i_{f−1} + i_{f−2} + ⋯ = −1 when f is odd;

• i_{f} − i_{f−1} + i_{f−2} + ⋯ = 1 when f is even. Proof. The proof uses induction and it is a straightforward, though somewhat lengthy, computation, cf. [4].

The following proposition is an immediate consequence of the previous theorem. Proposition 20. If a frame I = (i_{0}, i_{1}, i_{2}, …, i_{f}, …) with length 2n is admissible, then:

1. i_{f−1} > i_{f};

2. i_{0} = i_{1} + 1 ⟺ i_{1} = i_{f};

3. 2 ≤ i_{j} ≤ i_{j−1} + i_{j+1} − 2 (0 < j < f − 1)

5 Cardinality of a frame

Recall the two operations defined on the set of Dyck paths:

• the lifting s(u) of a path u;

• the gluing u ∧ v of two paths u and v.

With these two operations one may construct any Dyck path starting from shorter Dyck paths.

Therefore, every Dyck path may be expressed as

s^{j_{1}}(x_{1}) ∧ s^{j_{2}}(x_{2}) ∧ ⋯ ∧ s^{j_{t}}(x_{t})

where each x_{i} is again expressible in the same way, with the condition that after a finite number of steps one arrives at expressions of the form

s^{k_{1}}(0) ∧ s^{k_{2}}(0) ∧ ⋯ ∧ s^{k_{r}}(0),

where 0 is the unique Dyck path of length 0. For example, let’s consider the path

UUDUUDDDUDUUUDUDDDUUDD

with length 22:

The corresponding sequence is

01212321010123232101210

and it may be expressed as

s(x_{1}) ∧ s(x_{2}) ∧ s(x_{3}) ∧ s(x_{4}),

where s(x_{1}) = 012123210, s(x_{2}) = 010, s(x_{3}) = 012323210, s(x_{4}) = 01210, with x_{1} = 0101210, x_{2} = 0, x_{3} = 0121210, x_{4} = 010. One has therefore:

x_{1} = s(y_{1}) ∧ s(y_{2}), x_{3} = s(y_{3}), x_{4} = s(0), with y_{1} = 0, y_{2} = 010, y_{3} = 01010 and so y_{2} = s(0), y_{3} = s(z_{1}) ∧ s(z_{2}), with z_{1} = 0, z_{2} = 0.

Finally, the assigned path can be expressed as

s(s(0) ∧ s^{2}(0)) ∧ s(0) ∧ s^{2}(s(0) ∧ s(0)) ∧ s^{2}(0).

Since a frame is an eventually zero integer sequence, we may think of it as a polynomial. The constant polynomial 1 corresponds to the null frame. Thus s(1) is the frame of the unique path with length 2, while s^{2}(1) and s(1) ∧ s(1) are the frames of the length 4 paths, and so on. It is easy to check that, denoting by p(x) a frame, one has:

Proposition 21. s(p(x)) = 2 + xp(x), p(x) ∧ q(x) = p(x) + q(x) − 1.

The procedure to determine the admissibility of a sequence, see Examples 15, 16, can be used to determine a “canonical” representative of a frame. Example 22. Consider the frame (3, 4, 3, 1, 0, …) and apply to it the functions r and b. We obtain the sequence of frames

(2, 3, 3, 1, 0, …), (3, 3, 1, 0, …), (2, 2, 1, 0, …), (2, 1, 0, …), (1, 0, …),

thus getting to the null frame. There is, of course, only one path corresponding to the null frame: the null path.

We may now trace this procedure backwards with the operations s and a on the paths, eventually getting the desired canonical representative of the frame (3, 4, 3, 1, 0, …).

We start form the null path

this lifted gives:

with frame s(1) = (2, 1, 0, …),

lifted gives:

with frame s^{2}(1) = (2, 2, 1, 0, …),

extended gives:

with frame s^{2}(1) ∧ s(1) = (3, 3, 1, 0, …),

lifted gives:

with frame s(s^{2}(1) ∧ s(1)) = (2, 3, 3, 1, 0, …),

extended gives:

with frame s(s^{2}(1) ∧ s(1)) ∧ s(1) = (3, 4, 3, 1, 0, …).

Applying this procedure to any frame (i_{0}, i_{1}, …, i_{f}, 0, …), we reach a particular path belonging to this frame. This path is called the canonical representative of the frame (i_{0}, i_{1}, …, i_{f}, 0, …). In the preceding example the canonical representative is therefore s(s^{2}(0) ∧ s(0)) ∧ s(0).

The procedure is such that any time in a canonical representative there is a product of the form s^{j_{1}}(x_{1}) ∧ s^{j_{2}}(x_{2}) ∧ ⋯ ∧ s^{j_{t}}(x_{t}), then s^{j_{2}}(x_{2}) = ⋯ = s^{j_{t}}(x_{t}) = s(0).

In other words, a canonical path is of the form

s^{j_{1}}(s^{j_{2}}(⋯ (s^{j_{t−1}}(s^{j_{t}}(0) ∧ \underbrace{s(0) ∧ ⋯ ∧ s(0)}_{k_{t}}) ∧ \underbrace{s(0) ∧ ⋯ ∧ s(0)}_{k_{t−1}}) ⋯) ∧ \underbrace{s(0) ∧ ⋯ ∧ s(0)}_{k_{1}} .

Another way to describe the canonical path is to observe that in the corresponding sequence of U and D, after any sequence of one or more D there is at most one U.

Example 23. Assume the frame (3, 6, 6, 3, 1, 0, …) is given. By the preceding remarks to reach level 4 one must necessarily begin with a sequence of 4 U. Since there is a single foot at level 4 we must go down with at least 2 D. If we go down with 3 D, we could not go back to level 3, where there should be 3 feet. Hence we go down exactly two steps D and go back up with one U. So far the sequence is UUUUDDU. Since we do not need to go back to level 3 any longer, we go down with at least 2 more D’s. Again in this case, considering that at level 2 we have 6 feet, we must go down exactly with 2 D, then go up with one U, then go down with one D and climb back up with one U two more times. We thus obtain UUUUDDUDDUDUDU so far. Having exhausted the level 2 feet, we must go down with 2 D to level 0. Having obtained so far only 5 feet at level 1, we must still go up with U and the concluding with a D. The sequence is therefore UUUUDDUDDUDUDUDDUD.

The following property is often useful in computations.

Proposition 24. s(p(x) ∧ q(x)) ∧ s(1) = s(p(x)) ∧ s(q(x)).

Proof. Use Proposition 21: s(p(x)∧q(x))∧s(1) = s(p(x)+q(x)−1)∧(2+x) = (2+x(p(x)+ q(x) − 1)) ∧ (2 + x) = 2 + x(p(x) + q(x) − 1) + (2 + x) − 1 = 2 + xp(x) + 2 + xq(x) − 1 = s(p(x)) ∧ s(q(x)).

From this, it immediately follows:

Corollary 25. Given two Dyck paths x_{1}, x_{2}, the two paths s(x_{1}) ∧ s(x_{2}), s(x_{1} ∧ x_{2}) ∧ s(0) have the same frame.

Theorem 26. It is possible to obtain the canonical representative of a frame (i_{0}, i_{1}, …, i_{f}, 0, …) in a finite number of steps starting from any representative path x using the commutativity property of the gluing operation and Corollary 25.

Proof. If x is a representative of the frame, suppose that x contains a product s(0) ∧ s^{i}(y), then this can be transformed into s^{i}(y) ∧ s(0). If it contains a product s^{i}(y) ∧ s^{j}(z), with s^{i}(y) ≠ s(0), s^{j}(z) ≠ s(0), this can be transformed into s(s^{i−1}(y) ∧ s^{j−1}(z)) ∧ s(0). After a finite number of steps of these two types, one gets to the canonical path when none of these two steps is any longer possible.

Using Theorem 26, we are now able to count the number of paths in a given frame.

Example 27. Consider the frame (3, 4, 3, 1, 0, …) as before. We already saw that its canonical representative is u = s(s^{2}(0) ∧ s(0)) ∧ s(0). From this canonical representative, using commutativity of the wedge operation, we have a total of 4 paths, including u, precisely:

s(s^{2}(0)∧s(0))∧s(0), s(s(0)∧s^{2}(0))∧s(0), s(0)∧s(s^{2}(0)∧s(0)), s(0)∧s(s(0)∧s^{2}(0)):

Using Corollary 25 we have also v = s^{3}(0)∧s^{2}(0), which gives rise, by the commutativity of ∧, to a total of 2 paths, including v:

s^{3}(0) ∧ s^{2}(0), s^{2}(0) ∧ s^{3}(0).

We have therefore a total of 6 paths belonging to the frame (3, 4, 3, 1, 0, …).

We wish to compute an explicit formula for the number p_{I}^{2n} of paths having frame I = (i_{0}, i_{1}, …) with length 2n.

Definition 28. We define a right frame to be a frame of the form

(2, i_{1}, i_{2}, i_{3}, …)

and a left frame any other frame.

Definition 29. Given a frame (i_{0}, i_{1}, i_{2}, …), with i_{0} ≥ 2, we define its right progenitor to be the frame (2, i_{1} − i_{0} + 2, i_{2}, …). If the frame has i_{0} = i_{1} = … = i_{t−1} = 2 and i_{t} ≠ 2 we define its left progenitor to be (i_{t}, i_{t+1}, …). If i_{0} ≠ 2 its left progenitor is itself.

Remark 30. Every frame has a right and left progenitor except for the null frame which has only itself as a left progenitor and no right progenitor.

We can prove two propositions describing how the cardinality of a frame I is related to the one of its progenitors.

Proposition 31. The cardinality of a frame I is the same as that of its left progenitor.

Proof. It is easy to see that there is a bijection between the set of paths realizing the frame I and those realizing the frame s(I). Indeed, if p is a path of the frame I then s(p) is a path of the frame s(I), moreover s is an invertible operation. By repeatedly applying this argument we reach its left progenitor.

Obviously,

Lemma 32. The cardinality of the frame (u + 1, u, 0, …), ∀u ∈ ℕ, is 1.

Proposition 33. Given a frame of the form X = (2 + n, a, b …) with n ≥ 0, let Y = (2, a − n, b, …) be its right progenitor and k the cardinality of Y. Then the cardinality of X is k\binom{a−1}{a−n−1}.

Proof. If b = 0, the frame X is of the form (u + 1, u, 0, …) by Theorem 20. The right progenitor is (2, 1, 0, …) with cardinality k = 1 and the formula holds by Lemma 32. If b > 0 then a ≥ 2 + n, by Theorem 19. There is a bijection between the set of paths realizing the frame X and the weak compositions of n into a − n parts. Hence the formula. In fact, there are a − n positions in Y, (a − n − 2 feet at level 1 of the path plus the two endpoints at level 0) in which one can distribute the n paths s(0), using Proposition 24 or the commutativity property. This means that each of the n “hats” must be located in a − n positions.

In other words, any path in Y gives rise to a path in the frame X by inserting n pairs 01. These pairs may be distributed either at the beginning, in the order 01, or at the end as 10, or in the interior for every possible pair 12 as 1012. We are left to prove that if we take two different paths p and p′ in the frame Y they give rise to different paths in X. Notice that there are no 0’s in the middle of the associated sequences with p and p′. In the first position where they differ, one has the pair a, a + 1 and the other has a, a − 1 where a ≥ 2. If a > 2, a pair 01 or 10 cannot be inserted after a so the paths remain different. If a = 2 then we have the sequence ⋯ abc21 ⋯ and ⋯ abc23 · · ·. The insertion of pairs 1, 0 or 0, 1 cannot turn these two sequences into equal ones.

With these propositions it is easy to prove (cf. [4]):

Theorem 34. Given the frame I = (i_{0}, i_{1}, …, i_{f}, 0 …), setting:

j_{1} = i_{0} −2, j_{2} = i_{1} −i_{0}, j_{3} = i_{2} −i_{1} +i_{0} −2, j_{4} = i_{3} −i_{2} +i_{1} −i_{0}, and so on, the cardinality of I is

\binom{i_{1} − 1}{i_{1} − j_{1} − 1}\binom{i_{2} − 1}{i_{2} − j_{2} − 1} ⋯ \binom{i_{f} − 1}{i_{f} − j_{f} − 1}.

Example 35. The cardinality of the frame I = (5, 8, 7, 3) is

\binom{7}{4}\binom{6}{3}\binom{2}{0} = 700.

6 Colored Dyck paths

For any fixed frame (i_{0}, …, i_{f}, …) with length 2n, let v_{k} denote the number of U steps joining the levels k, k + 1 (k = 0, …, f − 1). This number is clearly equal to the number of the D steps joining the same two levels.

Theorem 36. Using the notation above, we have

v_{k} = i_{k} − i_{k−1} + ⋯ + (−1)^{k}i_{0} + (−1)^{k+1}, k = 0, …, f − 1.

Proof. Since at level 0 from the first node we have a U step, and we also have a D step in the final node, while in all the others we certainly have a U and a D, we have a total of 2(i_{0} − 1) steps joining level 0 and level 1. Since there are as many U as D we must have: v_{0} = i_{0} − 1. Assume we proved the formula up to v_{k−1}, we prove it for v_{k}. From the i_{k} nodes at level k we have 2i_{k} steps, half of which are U and half are D. Of these, 2v_{k−1} come from the lower level. It follows that v_{k} = i_{k} − v_{k−1} = i_{k} − (i_{k−1} − ⋯ + (−1)^{k−1}i_{0} + (−1)^{k}), hence the result.

Notice that the number v_{k} depends only on the given frame and not on the particular path in that frame.

Let I_{2n} denote the set of frames with length 2n. Suppose that we can color with u_{k} colors the U steps joining level k and level k + 1 and with d_{k} colors the D steps joining the same levels (k = 0, …, n − 1). The number of colored paths of a given frame I = (i_{0}, i_{1}, …) with length 2n, is clearly p_{I}^{2n}u_{0}^{v_{0}} ⋯ u_{n−1}^{v_{n−1}}d_{0}^{v_{0}} ⋯ d_{n−1}^{v_{n−1}}, recalling that p_{I}^{2n} denotes the number of elements in the frame I = (i_{0}, i_{1}, …) with length 2n. We immediately have

Theorem 37. The number of Dyck paths with length 2n, that can be colored with u_{k} and d_{k} colors from level k to level k + 1 (k = 0, …, n − 1) is

∑_{I∈I_{2n}} p_{I}^{2n}u_{0}^{v_{0}} ⋯ u_{n−1}^{v_{n−1}}d_{0}^{v_{0}} ⋯ d_{n−1}^{v_{n−1}}.

Notice that, the number v_{k} depends also on the frame I. However, to explicitly indicate such a relation in the notation would make for a quite cumbersome symbol such as v_{k}(p_{I}^{2n}).

7 Colored Motzkin paths

Proposition 38. If m^{(n)} is the number of Motzkin paths with length n, and we set ν = ⌊\frac{n}{2}⌋, then

m^{(n)} = ∑_{j=0}^{ν} ∑_{I∈I_{2j}} p_{I}^{2j}\binom{n}{n − 2j}.  (23)

Proof. A Motzkin path with length n may be obtained from a Dyck path p with length 2j, 0 ≤ 2j ≤ n, by adding n − 2j horizontal steps at the feet at various levels of p. If p has frame I = (i_{0}, …), we may distribute the n − 2j horizontal steps at each of the 2j + 1 nodes of p. So this can be done in as many ways as the possibility to express n − 2j as a sum of 2j +1 integers between 0 and n−2j, that is, in \binom{n−2j+(2j+1)−1}{n−2j} = \binom{n}{n−2j} ways. The statement follows.

The n − 2j horizontal steps can be distributed as follows: k_{0} steps at each of the i_{0} nodes of level 0, k_{1} steps at the i_{1} nodes of level 1, and so on. The number of such possible arrangements are counted by weak compositions of suitable integers. If at each level r one uses h_{r} colors on the horizontal steps and sets H = (h_{0}, …, h_{ν}), the formula becomes

Proposition 39.

m_{H}^{(n)} = ∑_{j=0}^{ν} ∑_{I∈I_{2j}} p_{I}^{2j} ∑_{k_{0}+···+k_{ν}=n−2j} \binom{k_{0} + i_{0} − 1}{k_{0}} ⋯ \binom{k_{ν} + i_{ν} − 1}{k_{ν}}h_{0}^{k_{0}} ⋯h_{ν}^{k_{ν}}.

It may happen that in the summation corresponding to a frame, the frame is too “low” to allow adding horizontal steps, for example at level ν. In this case the corresponding binomial coefficient \binom{k_{ν}+i_{ν}−1}{k_{ν}} has i_{ν} = 0 and is therefore zero.

If we add to this the possibility of coloring the U and D steps with u_{k} and d_{k} colors from level k to level k + 1 (k = 0, …, ν − 1), and we set U = (u_{0}, …, u_{ν−1}), D = (d_{0}, …, d_{ν−1}), we get

Theorem 40. Let m_{H,U,D}^{(n)} denote the number of Motzkin paths colored with colors determined by H, U, D. Then we have

m_{H,U,D}^{(n)} = ∑_{j=0}^{ν} ∑_{I∈I_{2j}} p_{I}^{2j}u_{0}^{v_{0}} ⋯ u_{j−1}^{v_{j−1}}d_{0}^{v_{0}} ⋯ d_{j−1}^{v_{j−1}} ∑_{\begin{matrix}k_{0}+···+k_{ν} \\ =n−2j \end{matrix}} \binom{k_{0} + i_{0} − 1}{k_{0}} ⋯ \binom{k_{ν} + i_{ν} − 1}{k_{ν}}h_{0}^{k_{0}} ⋯ h_{ν}^{k_{ν}} .  (24)

Notice that such formula makes sense if we set h_{k} = 0 for all those levels k where there are no horizontal steps provided we attribute value 1 to the expression h_{j}^{k_{j}}, if h_{j} = 0 and k_{j} = 0.

Remark 41. Comparing formula (23) with (24) written in the case of all h_{k} = u_{k} = d_{k} = 1 yields the following identity for binomial coefficients, where we made obvious changes of symbols:

\binom{m + i_{0} + ⋯ + i_{ν} − 1}{m} = ∑_{k_{0}+···+k_{ν}=m} \binom{k_{0} + i_{0} − 1}{k_{0}} ⋯ \binom{k_{ν} + i_{ν} − 1}{k_{ν}}.

References

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

[2] S. Capparelli and P. Maroscia, On two sequences of orthogonal polynomials related to Jordan blocks, Mediterr. J. Math. 10 (2013), 1609–1630.

[3] S. Capparelli and P. Maroscia, Some results on a class of polynomials related to convolutions of the Catalan sequence, Mediterr. J. Math. 11 (2014), 255–271.

[4] S. Capparelli and A. Del Fra, Some results on Dyck paths and Motzkin paths, preprint,

   2015. Available at http://arxiv.org/abs/1505.01961.

[5] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978.

[6] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.

[7] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

[8] D. E. Knuth, The Art of Computer Programming, Addison-Wesley, 1973.

[9] N. J. A. Sloane, The On–Line Encyclopedia of Integer Sequences, http://oeis.org.

[10] A. Savo, Heat flow, heat content and the isoparametric property, preprint, 2014. Avail-

   able at http://arxiv.org/abs/1406.2835.

[11] G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Lecture Notes LACIM, UQAM, Montréal, 1984. Available at

   http://www.xavierviennot.org/xavier/polynomes_orthogonaux.html.

[12] G. Viennot, A combinatorial theory for general orthogonal polynomials with extensions and applications, in Polynômes Orthogonaux et Leurs Applications, Lecture Notes in Math., Vol. 1171, Springer, 1985, pp. 139–157.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A99. Keywords: Dyck path, Motzkin path, binomial transform.

(Concerned with sequences \underline{A025235}, \underline{A025237}, \underline{A063376}, and \underline{A151374}.)

Received May 19 2015; revised versions received July 19 2015; July 27 2015. Published in Journal of Integer Sequences, July 29 2015.

Return to Journal of Integer Sequences home page.