**Matrix Identities on**

Weighted Partial Motzkin Paths

William Y.C. Chen$^1$, Nelson Y. Li$^2$, Louis W. Shapiro$^3$ and Sherry H. F. Yan$^4$\
\[2mm\] $^{1,2,4}$Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, P.R. China\
\[2mm\] $^3$Department of Mathematics, Howard University, Washington, DC 20059, USA\
\[2mm\] $^1$chen@nankai.edu.cn, $^2$nelsonli@eyou.com, $^3$lshapiro@howard.edu, $^4$huifangyan@eyou.com\

[**Abstract.**]{} We give a combinatorial interpretation of a matrix identity on Catalan numbers and the sequence $(1, 4,
4^2, 4^3, \ldots)$ which has been derived by Shapiro, Woan and Getu by using Riordan arrays. By giving a bijection between weighted partial Motzkin paths with an elevation line and weighted free Motzkin paths, we find a matrix identity on the number of weighted Motzkin paths and the sequence $(1, k, k^2, k^3, \ldots)$ for any $k \geq 2$. By extending this argument to partial Motzkin paths with multiple elevation lines, we give a combinatorial proof of an identity recently obtained by Cameron and Nkwanta. A matrix identity on colored Dyck paths is also given, leading to a matrix identity for the sequence $(1, t^2+t, (t^2+t)^2, \ldots)$.

[Key words]{}: Catalan number, Schröder number, Dyck path, Motzkin path, partial Motzkin path, free Motzkin path, weighted Motzkin path, Riordan array

[AMS Mathematical Subject Classifications]{}: 05A15, 05A19.

[Corresponding Author:]{} William Y. C. Chen, chen@nankai.edu.cn

Introduction
============

This paper is motivated the following matrix identity obtained by Shapiro, Woan and Getu [@shapirotc] in their study of the moments of a Catalan triangle [@chapman; @shapiro; @sulanke]: $$\label{eq2.2}
\begin{bmatrix} 1 \\2 & 1\\5 & 4 & 1\\14 & 14 & 6 & 1\\42 & 48 & 27 & 8 & 1\\& & \cdots &&&\ddots  \end{bmatrix}
 \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ \vdots
\end{bmatrix} = \begin{bmatrix} 1 \\ 4 \\ 4^2 \\ 4^3 \\ 4^4 \\ \vdots
\end{bmatrix},$$ where the first column of the first matrix is the Catalan number $C_n={1\over n+1} {2n \choose n}$ and $a_{i,j}$ (the entry in the $i$-th row and $j$-th column) is determined by the following recurrence relation for $j\geq 2 $: $$\label{r2.2}
a_{i,j}=a_{i-1, j-1}+2a_{i-1,j}+a_{i-1,j+1}   .$$ Another proof of the above identity is given by Woan, Shapiro and Rogers [@woan] while computing the areas of parallelo-polyominos via generating functions.

The first result of this paper is a combinatorial interpretation of the identity (\[eq2.2\]) in terms of Dyck paths.

One main objective of this paper is to give a matrix identity that extends the sequence $(1, 4, 4^2, 4^3, \ldots)$ to $(1, k, k^2,
k^3, \ldots)$ in (\[eq2.2\]). The following matrix identity was proved by Cameron and Nkwanta [@cn] that arose in a study of elements of order $2$ in [*Riordan groups*]{} [@aigner; @shapiroba; @shapirotr; @sprugnoli]: $$\label{eq1.1}
\begin{bmatrix} 1 \\3 & 1\\11 & 6 & 1\\45 & 31 & 9 & 1\\197 & 156 & 60 & 12 & 1 & &\\& & \cdots &&&\ddots  \end{bmatrix}
\begin{bmatrix} 1 \\ 3 \\ 7 \\ 15 \\ 31 \\ \vdots
\end{bmatrix} = \begin{bmatrix} 1 \\ 6 \\ 6^2 \\ 6^3 \\ 6^4 \\
\vdots
\end{bmatrix},$$ where the entry $a_{i,j}$ ($i$th row and $j$th column) in the above matrix satisfies the recurrence relation $$\label{r1.1}
a_{i,j}=a_{i-1,j-1}+3a_{i-1,j}+2a_{i-1,j+1}$$ for $j\geq 2$ and the $a_{i,1}$ is the $i$-th [*little Schröder number*]{} $s_i$ (sequence A001003 in [@sloane]), which counts Schröder paths of length $2(i+1)$. A [*Schröder path*]{} is a lattice path starting at (0, 0) and ending at $(2n, 0)$ and using steps $H=(2, 0)$, $U=(1, 1)$ and $D=(1,
-1)$ such that no steps are below the $x$-axis and there are no peaks at level one. Imposing this last peak condition gives us little Schröder numbers while without it we would have the [*large Schröder numbers*]{}.

For $k=3$, we obtain the following matrix identity on Motzkin numbers:

$$\label{3p}
\begin{bmatrix} 1 \\1 & 1\\2 & 2 & 1\\4 & 5 & 3 & 1\\9 & 12 & 9 & 4 & 1\\& & \cdots &&&\ddots   \end{bmatrix}
\begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ \vdots
\end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 3^2 \\ 3^3 \\ 3^4 \\ \vdots
\end{bmatrix},$$

where the first column is the sequence of Motzkin numbers, and matrix $A=(a_{ij})$ is generated by the following recurrence relation: $$a_{i,j}= a_{i-1, j-1} + a_{i-1, j} + a_{i-1, j+1}.$$ For $k=5$, we find the following matrix identity $$\label{5p}
\begin{bmatrix} 1 \\3 & 1\\10 & 6 & 1\\36 & 29 & 9 & 1\\137 & 132 & 57 & 12 & 1\\& & \cdots &&&\ddots  \end{bmatrix}
\begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ \vdots
\end{bmatrix} = \begin{bmatrix} 1 \\ 5 \\ 5^2 \\ 5^3 \\ 5^4 \\ \vdots
\end{bmatrix},$$ where the first column sequence A002212 in [@sloane], which has two interpretations, the number of $3$-Motzkin paths or the number of ways to assemble benzene rings into a tree [@hr]. Recall that a $3$-Motzkin path is a lattice path from $(0,0)$ to $(n-1,0)$ that does not go below the $x$-axis and consists of up steps $U=(1,1)$, down steps $D=(1,-1)$, and three types of horizontal steps $H=(1,0)$. The above matrix $A=(a_{i,j})$ is generated by the first column and the following recurrence relation $$a_{i,j}= a_{i-1,j-1} + 3a_{i-1,j} +
a_{i-1,j+1}.$$ We may prove the above identities (\[3p\]) and (\[5p\]) by using method of Riordan arrays. So the natural question is to find a matrix identity for the sequence $(1, k, k^2, k^3, \ldots)$. We need the combinatorial interpretation of the entries in the matrix in terms of weighted partial Motzkin paths, as given by Cameron and Nkwanta [@cn]. To be precise, a partial Motzkin path, also called a Motzkin path from $(0,0)$ to $(n,k)$ in [@cn], is just a Motzkin path but without the requirement of ending on the x-axis. A weighted partial Motkzin a partial Motzkin path with the weight assignment that the horizontal steps are endowed with a weight $k$ and the down steps are endowed with a weight $t$, where $k$ and $t$ are regarded as positive integers. In this sense, our weighted Motzkin paths can be regarded as further generalization of $k$-Motzkin paths in the sense of $2$-Motzkin paths and $3$-Motkzin paths [@BdLPP; @deutschs; @sloane].

We introduce the notion of weighted free Motzkin paths which is a lattice path consisting of Motzkin steps without the restrictions that it has to end with a point on the $x$-axis and it does not go below the $x$-axis. We then give a bijection between weighted free Motzkin paths and weighted partial Motzkin paths with an elevation line, which leads to a matrix identity involving the number of weighted partial Motzkin paths and the sequence $(1, k,
k^2, \ldots)$. The idea of the elevation operation is also used by Cameron and Nkwanta in their combinatorial proof of the identity (\[eq2.2\]) in a more restricted form. By extending our argument to weighted partial Motzkin paths with multiple elevation lines, we obtain a combinatorial proof of an identity recently derived by Cameron and Nkwanta, in answer to their question.

We also give a generalization of the matrix identity (\[eq2.2\]) and give a combinatorial proof by using colored Dyck paths.

Riordan Arrays
==============

In this section, we give a brief introduction to the notion of Riordan arrays [@shapiroba; @shapirotr; @sprugnoli]. Let us use (\[eq2.2\]) and (\[eq1.1\]) as examples. Start with two generating functions $g(x)=1+g_1x+g_2x^2+\cdots$ and $f(x)=f_1x+f_2x^2+\cdots$ with $f_1\neq 0$. Let $H=(h_{i,j})_{n,j\geq 0}$ be the infinite lower triangular matrix with nonzero entries on the main diagonal, where $h_{i,j}=[x^i](g(x)(f(x)^j)$ for $i\geq j$, namely, $h_{i,j}$ equals the coefficient of $x^i$ in the expansion of the series $f(x)(g(x)^j)$. If an infinite lower triangular matrix $H$ can be constructed in this way from two generating functions $g(x)$ and $f(x)$, then it is called a [*Riordan array*]{} and is denoted by $H=(g(x),f(x))=(g,f)$.

Suppose we multiply the matrix $H=(g,f)$ by a column vector $(a_0,a_1,\cdots)^T$ and get a column vector $(b_0,b_1,\cdots)^T$. Let $A(x)$ and $B(x)$ be the generating functions for the sequences $(a_0,a_1,\cdots)$ and $(b_0,b_1,\cdots)$ respectively. Then the method of Riordan arrays asserts that $$B(x)=g(x)A(f(x)).$$

For the matrix identity (\[eq2.2\]), let $g(x)$ be the generating function for Catalan numbers $(1, 2, 5, 14, \ldots)$: $$g(x) = {1 -2x-
\sqrt{1-4x} \over 2x^2}.$$ Let $f(x)=xg(x)$. From the recurrence relation (\[r2.2\]) one may derive that the generating function for the sequence in the $j$-th $(j\geq 1)$ column in the matrix in (\[eq2.2\]) equals $g(xg)^{j-1}$. Let $H$ be the Riordan array $(g, xg)$. Since the generating function of $(1,2,3,4\cdots)^T$ equals $A(x)=\frac{1}{(1-x)^2}$, it follows that $B(x)=g(x)A(xg(x))=\frac{1}{1-4x}$ equals the generating function for the right hand side of (\[eq2.2\]). Thus we obtain the identity (\[eq2.2\]).

Let us consider the matrix identity (\[eq1.1\]). Let $g(x)$ be the generating function for the little Schröder numbers as given by $$\label{sg}
g(x)={1-3x-\sqrt{1-6x+x^2}\over 4x^2},$$ and let $f(x) =xg(x)$. Note that the generating function for the sequence $(1, 3, 7, 15, \ldots)$ equals $A(x)=\frac{1}{(1-x)(1-2x)}$. From the recurrence relation (\[r1.1\]) one may verify that the matrix in (\[eq1.1\]) is indeed the Riordan array $(g, xg)$. Therefore, the generating function for the right hand side of (\[eq1.1\]) equals $
g(x)A(xg(x))=\frac{1}{1-6x}$, which implies (\[eq1.1\]).

Using the same method, we can verify the matrix identity (\[3p\]) and (\[5p\]). Since we are going to establish a general bijection for weighted Motzkin numbers, here we omit the proofs.

Dyck path interpretation of (\[eq2.2\])
=======================================

In this section, we present a combinatorial interpretation of the matrix identity (\[eq2.2\]) by using Dyck paths. A [*Dyck path*]{} of length $2n$ is a path going from the origin $(0,0)$ to $(2n,0)$ using steps $U=(1,1)$ and down steps $D=(1,-1)$ such that no steps is below the $x$-axis [@De; @stanley]. The number of Dyck paths of length $2n$ equals the Catalan number $C_n$.

For a Dyck path $P$, the points on the $x$-axis except for the initial point are called return points. In this sense, the ending point is always a return point. Formally speaking, a [*composition*]{} of a Dyck path $P$ is sequence of Dyck path $(P_1,
P_2, \ldots, P_j)$ such that $P=P_1 P_2 \cdots P_j$, where $P_1,
P_2, \ldots, P_j$ are Dyck paths. For a composition $(P_1, P_2,
\ldots, P_j)$ of a Dyck path $P$, its length is meant to be the length of $P$ and $j$ is called the number of segments. We may choose certain return points to cut off the Dyck paths into a composition. We use the convention that the ending point is always a cut point. Clearly, a Dyck path with one segment is an ordinary Dyck path.

\[dotheom\] For $j\geq 2$, we have the following recurrence relation $$\label{eq.1}
 d_{i,j}=d_{i-1,j-1} +
2d_{i-1,j} + d_{i-1,j+1}.$$

Let $(P_1, P_2, \ldots, P_{j})$ be composition of a Dyck path $P$ of length $2i$. Consider the following cases for $P_1$. Case 1: $P_1=UD$. Then we get a composition length $2(i-1)$ with $j-1$ segments: $(P_2, \ldots, P_j)$. Case 2: $P_1=QUD$ and $Q$ is not empty. Then we get a composition $(Q, P_2, \ldots, P_j)$ of length $2(i-1)$ and $j$ segments. Case 3: $P_1=U Q D$, $Q$ is not empty. We get a composition $(Q,  P_2, \ldots, P_j)$ of length $2(i-1)$ with $j$ segments. Case 4: $P_1=Q_1UQ_2D$, where $Q_1$ and $Q_2$ are not empty. Then we get a composition $(Q_1, Q_2,
P_2, \ldots, P_j)$ of length $2(i-1)$ with $j+1$ segments. Adding up the terms in the above cases, we obtain the desired recursion (\[eq.1\]).

From Lemma \[dotheom\] one sees that the entry $a_{i,j}$ in the triangular matrix of the identity (\[eq2.2\]) can be explained as the number compositions of Dyck paths of length $2i$ that contain $j$ segments. We remark that this combinatorial interpretation can also be derived from the generating function of the entries in the $j$-th column in of the matrix in (\[eq2.2\]). The following formula for $a_{i,j}$ has been derived by Cameron and Nkwanta [@cn]: $$a_{i,j}= {j \over i} \, {2i \choose i-j} .$$

Let us rewrite the matrix identity (\[eq2.2\]) as follows $$\label{eq.2}
\sum_{j= 1}^i ja_{i,j}=4^{i-1}.$$ A combinatorial formulation of the above identity is given by Callan [@callan].

We are now ready to give a combinatorial proof of the above identity. Clearly, $4^n$ is the number of sequences of length $n$ on four letters, say, $\{1, 2, 3, 4\}$. The term $ja_{i,j}$ suggests that we should specify a segment in a composition as a distinguished segment. We may use a star $*$ to mark the distinguished segment. We call a composition with a distinguished segment a [*rooted*]{} composition of a Dyck path. Then $ja_{i,j}$ equals the number of rooted compositions of Dyck paths of length $2i$ that contain $j$ segments.

There is a bijection $\phi$ between the set of rooted compositions of Dyck paths of length $2i$ and the set of sequences of length $i-1$ on four letters.

Let $(P_1, P_2, \ldots, P_j)$ be a rooted composition of a Dyck path $P$ of length $2i$. We proceed to construct a sequence of length $i-1$ on the elements $\{ 1, 2,3, 4\}$. We now recursively define a map $\phi$ from rooted compositions of a Dyck path $P$ of length $2i$ to sequences of length $i-1$ on $\{
1, 2, 3, 4\}$. For $i=1$, $P$ is unique, and the sequence is set to be the empty sequence. We now assume that $i>1$. Let $(P_1,
\ldots, P_t^*, \ldots, P_j)$ be a rooted composition of $P$ with $P_t^*$ being the distinguished segment.

We have the following cases.

1.  $P_1=UD$ and $t=1$. Then we set $\phi(P)=1\, \phi(P_2^*, P_3, \ldots, P_j)$.

2.  $P_1=UD$ and $t\not=1$. Then we set $\phi(P)=2\, \phi(P_2, \ldots, P_t^*\ldots, P_j)$.

3.  $P_1=QUD$ and $Q$ is a nonempty Dyck path. Set $\phi(P)=3\,
     \phi(Q^*, P_2,  \ldots, P_j)$ if $t=1$ and set $\phi(P_1, \ldots, P_j) =3 \, \phi (Q, P_2, \ldots, P_t^*, \ldots, P_j)$ if $t>1$.

4.  $P_1=Q_1UQ_2D$, where $Q_1$ and $Q_2$ are nonempty Dyck paths. Then we set $$\phi(P_1, \ldots, P_j)=1\, \phi
     (Q_1, Q_2, P_2, \ldots, P_t^*, \ldots, P_j)
     \text{ if }
     t>1 ,$$ $$\phi(P)=1\, \phi
     (Q_1, Q_2^*, P_2, \ldots, P_j) \text{ if } t=1.$$

5.  If $P_1=UQD$ and $Q$ is a nonempty Dyck path. Then we set $$\phi(P)=4\, \phi(Q, P_2, \ldots, P_t^*, \ldots,
    P_j).$$

In order to show that $\phi$ is a bijection, we construct the reverse map of $\phi$. Let $w=w_1w_2\cdots w_{i-1}$ be a sequence of length $i-1$ on $\{1, 2, 3, 4\}$. If $i=1$, then it corresponds to $UD$. We now assume that $i>1$. Suppose that $w_2w_3\cdots w_{i-1}$ corresponds to a rooted composition $(R_1, R_2, \cdots, R_m)$ of a Dyck path $P$ of length $2(i-1)$ with $R_k$ being the distinguished segment. We proceed to find a rooted composition $(P_1, P_2, \ldots, P_j)$ with $P_t$ being the distinguished segment such that $\phi(P_1,
P_2, \ldots, P_j) = w_1 \phi(R_1, R_2, \ldots, R_m)$.

If $w_1=2$, we have $P_1=UD$ and $(P_2, P_3, \ldots, P_j) =
                                       (R_1, R_2, \ldots, R_m)$. It follows that $t=k+1$ and $j=m+1$. Thus we can recover $(P_1, P_2, \ldots, P_j)$. For the case $w_1=3$, we have $P_1=R_1UD$ and $t=k$. Also, we can recover $(P_2, \cdots, P_j)$ from $(R_2,  \ldots, R_m)$. For the case $w_1=4$, we have $t=k$, $P_1=UR_1D$, and $(P_2,
\ldots, P_j)=(R_2, \ldots, R_m)$.

It remains to deal with the situation $w_1=1$, which involves Cases 1 and 4 of the bijection. If $k=1$, then we have $t=1$, $P_1=UD$ and $(P_2,  \ldots, P_j)=(R_1,\ldots, R_m)$. If $k=2$, then we have $t=1$, $P_1=R_1UR_2D$ and $(P_2,  \ldots, P_j)= (R_3,
 \ldots, R_m)$. If $k>2$, then we have $t=k-1$, $P_1=R_1UR_2D$, and $(P_2,  \ldots, P_j)=(R_3,  \ldots, R_m)$. Thus, we have shown that $\phi$ is a bijection.

An example of the bijection $\phi$ is given in Figure \[dyck\], where normal vertices are drawn with black points, return points that cut off the Dyck paths into segments are drawn with white points, and the distinguished segment is marked with a $*$ on its last return step.

(120,25)

(0,15)[(1,1)[4]{}]{} (4,19)[(1,-1)[3.7]{}]{} (8.3,15.3)[(1,1)[8]{}]{} (16,23)[(1,-1)[8]{}]{} (24,15)[(1,1)[4]{}]{} (28,19)[(1,-1)[3.7]{}]{}(29.5,16.9)[$\ast$]{}(32.3,15.3)[(1,1)[4]{}]{} (36,19)[(1,-1)[3.7]{}]{} (0,15) (4,19) (8,15) (12,19) (16,23) (20,19) (24,15)(28,19) (32,15) (36,19) (40,15)

(43,19)[$\longleftrightarrow$]{} (54,18)[$2$]{}

(58,15)[(1,1)[8]{}]{} (66,23)[(1,-1)[8]{}]{} (74,15)[(1,1)[4]{}]{} (78,19)[(1,-1)[3.7]{}]{}(79.5,16.9)[$\ast$]{}(82.3,15.3)[(1,1)[4]{}]{} (86,19)[(1,-1)[3.7]{}]{} (58,15) (62,19) (66,23) (70,19) (74,15)(78,19) (82,15) (86,19) (90,15)

(93,19)[$\longleftrightarrow$]{}

(0,3)[$23$]{} (5.3,0.3)[(1,1)[8]{}]{} (13,8)[(1,-1)[7.7]{}]{} (18.5,1.9)[$\ast$]{}(21.3,0.3)[(1,1)[4]{}]{} (25,4)[(1,-1)[3.7]{}]{} (5,0) (9,4) (13,8) (17,4) (21,0) (25,4) (29,0)

(32,4)[$\longleftrightarrow$]{}

(43,3)[$234$]{} (48,0)[(1,1)[4]{}]{} (52,4)[(1,-1)[3.7]{}]{} (53.5,1.9)[$\ast$]{}(56.3,0.3)[(1,1)[4]{}]{} (60,4)[(1,-1)[3.7]{}]{} (48,0) (52,4) (56,0) (60,4) (64,0)

(67,4)[$\longleftrightarrow$]{}

(78,3)[$2341$]{} (85,0)[(1,1)[4]{}]{} (89,4)[(1,-1)[3.7]{}]{} (90.5,1.9)[$\ast$]{} (85,0) (89,4) (93,0)

(96,4)[$\longleftrightarrow$]{} (107,3)[$2341$]{}

Weighted Partial Motzkin Paths 
===============================

A [*Motzkin path*]{} of length $n$ is a path going from $(0,0)$ to $(n,0)$ consisting of up steps $U=(1,1)$, down steps $D=(1,-1)$ and horizontal steps $H=(1,0)$, which never goes below the $x$-axis. A [*$(k,t)$-Motzkin path*]{} is a Motzkin path such that each horizontal step is weighted by $k$, each down step is weighted by $t$ and each up step is weighted by $1$. The case $k=2, t=1$ gives the $2$-Motzkin paths which have been introduced by Barcucci, del Lungo, Pergola and Pinzani [@BdLPP] and have been studied by Deutsch and Shapiro [@deutschs]. The [*weight* ]{} of a path is the product of the weights of all its steps. Denote by $|P|$ the weight of a path $P$. The [*weight* ]{} of a set of paths is the sum of the total weights of all the paths. For any step, we say that it is at level $k$ if the $y$-coordinate of its end point is at level $k$.

In this section, we aim to establish the following matrix identity on weighted Motzkin numbers.

Let $M=(m_{i,j})_{i,j\geq 1}$ be the lower triangular matrix such that the first column is the sequence of the number of $(k-t-1, t)$-Motzkin paths of length $n$ and $m_{i,j}$ satisfies the following recurrence relation for $j\geq 2$: $$\label{rc.5}
m_{i,j}=m_{i-1,j-1}+(k-t-1)m_{i-1,j}+tm_{i-1,j+1}.$$ Then we have $$\label{eq.5}
(m_{i,j})  \times
\begin{bmatrix} 1 \\ 1+t \\ 1+t+t^2  \\ \vdots\\
\end{bmatrix} = \begin{bmatrix} 1 \\ k \\ k^2  \\ \vdots
\end{bmatrix},$$

It is well known that the number of $2$-Motzkin paths of length $n$ is given by the Catalan number $C_{n+1}$. It follows that the matrix identity (\[eq2.2\]) is a special case of (\[eq.5\]) for $k=4,t=1$. Denote by $f(x)=\sum_{n\geq 0}f_{n}x^n$ the generating function for the number of $(3,2)$-Motzkin paths. Then it is easy to find the functional equation for $f(x)$: $$f(x)=1+3xf(x)+2x^2f^2(x).$$ It follows that $$f(x)={{1-3x-\sqrt{1-6x+x^2}}\over {4x^2}}.$$ From the above generating function, one see that the number of $(3,2)$-Motzkin paths of length $n$ equals the $n$-th little Schröder number. Therefore, the matrix identity (\[eq1.1\]) is a special case of (\[eq.5\]) for $k=6,t=2$.

Let us rewrite matrix identity (\[eq.5\]) in the following form $$\label{mi}
\sum_{j= 1}^i \, m_{i,j}(1+t+\cdots +t^{j-1}) =k^{i-1}.$$

The following combinatorial interpretation of the entries in the matrix in (\[eq.5\]) is due to Cameron and Nkwanta [@cn]. A partial $(k,t)$-Motkzin path is defined as an initial segment of a $(k,t)$-Motkzin path. We say that a partial $(k, t)$-Motzkin path ends at level $j$ if its last step is at level $j$.

Let $m_{i,j}$ be the entries in the matrix in (\[eq.5\]). Then $m_{i,j}$ equals the the number of partial $(k-t-1, t)$-Motzkin paths of length $i-1$ that end at level $j-1$.

[*Proof.*]{} Regarding the first column of the matrix $M$, one sees that a partial $(k-t-1, t)$-Motzkin path that ends at level zero is just a $(k-t-1, t)$-Motzkin path. Let $a_{i,j}$ denote the number of partial $(k-t-1, t)$-Motzkin paths of length $i-1$ ending at level $j-1$. Let $P$ be a partial $(k-t-1,
t)$-Motzkin path of length $i-1$ that ends at level $j-1$ $(j>1)$. By considering the last step of $P$ and its weight, one sees that $a_{i,j}$ satisfies the recurrence relation (\[rc.5\]).

Let $P$ be a partial $(k-t-1, t)$-Motzkin path ending at level $j-1$. We need the notion of an [*elevated* ]{} partial Motzkin path, which has been introduced by Cameron and Nkwanta [@cn] in their combinatorial proof of the following identity which is a reformulation of (\[eq.2\]): $$4^n=
\sum_{k=0}^n \, {(k+1)^2 \over n+1} \, {2n+2\choose n-k}.$$ Let $p$ be an integer with $0\leq p\leq j$. The [*elevation*]{} of $P$ with respect to the horizontal line $y=p$ is defined as follows. For $p=0$, the elevation of $P$ with respect to $y=0$ is just $P$ itself. We now assume $ 0<p\leq j$. Note that there are always up steps of $P$ at levels $j-1$, $j-2$, …, $0$ bearing in mind that an up step is said to be at level $k$ if its initial point is at level $k$. Therefore, for each level from $0$ to $p-1$, one can find a rightmost up step. Note that there are no other steps at the same level to the right of the rightmost up step which is called a [*R-visible*]{} up step with respect to the line $y=p$ in the sense that it can seen far away from the right. The elevation of $P$ with respect to the line $y=p$ is derived from $P$ by changing the R-visible up steps up to level $p-1$ to down steps by elevating their initial points. The line $y=p$ is called an [*elevation line*]{}.

Figure \[mot\] is an illustration of the elevation of a partial Motzkin path with respect to the line $y=2$.

(150,30) (-0.15,0)[(1,1)[4]{}]{} (0.15,0)[(1,1)[4]{}]{}(4,4)[(1,0)[4]{}]{} (8,4)[(1,1)[4]{}]{} (12,8)[(1,-1)[4]{}]{} (16,4)[(1,0)[4]{}]{} (20,4)[(1,1)[8]{}]{} (28,12)[(1,-1)[8]{}]{} (35.85,4)[(1,1)[4]{}]{} (36.15,4)[(1,1)[4]{}]{}(40,8)[(1,1)[8]{}]{}(48,16)[(1,-1)[4]{}]{} (52,12)[(1,0)[4]{}]{} (0,8)(3,0)[20]{}[(1,0)[1]{}]{}

(0,0) (4,4) (8,4) (12,8) (16,4) (20,4) (24,8) (28,12) (32,8) (36,4) (40,8) (44,12) (48,16) (52,12) (56,12)

(63,5)[$\longleftrightarrow$]{}

(79.85,8)[(1,-1)[4]{}]{} (80.15,8)[(1,-1)[4]{}]{}(84,4)[(1,0)[4]{}]{} (88,4)[(1,1)[4]{}]{} (92,8)[(1,-1)[4]{}]{} (96,4)[(1,0)[4]{}]{} (100,4)[(1,1)[8]{}]{} (108,12)[(1,-1)[8]{}]{} (115.85,4)[(1,-1)[4]{}]{} (116.15,4)[(1,-1)[4]{}]{}(120,0)[(1,1)[8]{}]{} (128,8)[(1,-1)[4]{}]{} (132,4)[(1,0)[4]{}]{}

(80,8) (84,4) (88,4) (92,8) (96,4) (100,4) (104,8) (108,12) (112,8) (116,4) (120,0) (124,4) (128,8) (132,4) (136,4)

We now introduce the notion of [*free Motzkin* ]{} paths which are lattice paths starting from $(0,0)$ and using up steps $U=(1,1)$, down steps $D=(1,-1)$ and horizontal steps $H=(1,0)$. Note that there is no restriction so that the paths may go below the $x$-axis. A free $(k,t)$-Motzkin path is a free Motzkin path in which the steps are weighted in the same way as for $(k,t)$-Motzkin paths, namely, an up step has weight one, a horizontal step has weight $k$ and a down step has weight $t$.

For a free Motzkin path $P$ we may analogously define the [*L-visible*]{} down steps as the down steps that are visible from the far left. It is clear that a complete Motzkin path (a partial Motzkin path with ending point on the $x$-axis) has no R-visible up steps. Similarly, a partial Motzkin path has no L-visible down steps.

We have the following summation formula for weighted free Motzkin paths.

The sum of weights of free $(k-t-1, t)$-Motkzin paths of length $i$ equals $k^i$.

The proof of the above lemma is obvious because of the relation $$(1+k-t-1+t)^i=k^i.$$ We are now led to establish a bijection for the identity (\[mi\]).

\[the.1\] There is a bijection between the set of partial $(k-t-1,t)$-Motzkin paths of length $i$ with an elevation line and the set of free $(k-t-1,t)$-Motzkin path of length $i$.

The bijection is just the elevation operation. The reverse map is also easy. For a free Motzkin path, one can identify the L-visible down steps, if any, then change these L-visible down steps to up steps by elevating their end points.

For a partial $(k-t-1, t)$-Motzkin path $P$ with an elevation line $y=p$, suppose that $Q$ is the elevation of $P$ with respect to $y=p$. It is clear that the weight of $Q$ equals $t^p |P|$. If $P$ ends at level $j$, then the possible elevation lines are $y=0$, $y=1, \ldots, y=j-1$. Summing over $j$ to get what we have currently. Thus we arrive at a combinatorial interpretation of the identity (\[mi\]).

As a consequence of Theorem \[the.1\], we obtain the matrix identity (\[eq.5\]). Note that the matrix identity (\[eq2.2\]) is a special case of (\[eq.5\]) for $k=4$ and $t=1$, and the matrix identity (\[eq1.1\]) is also a special case of (\[eq.5\]) for $k=6$ and $t=2$.

An Identity of Cameron and Nkwanta
==================================

In their study of involutions in Riordan groups, Cameron and Nkwanta [@callan] obtained the following identity for $m\geq
0$, and asked for a purely combinatorial proof: $$\binom{n}{m}4^{n-m}=\sum_{k=0}^{n}\frac{k+1}{n+1}\binom{k+m+1}{k-m}\binom{2n+2}{n-k}.$$

It is clear that identity (\[eq.2\]) is a special case for $m=0$. To be consistent with our notation, we may rewrite the above identity in the following form: $$\label{cam}
\binom{i-1}{m}4^{i-1-m}=\sum_{j=1}^{i}\frac{j}{i}\binom{j+m}{2m+1}\binom{2i}{i-j}.$$

We now give a bijective proof (\[cam\]).

We recall that the number of partial $2$-Motzkin paths of length $i-1$ ending at level $j-1$ is given by $a_{i,j}=\frac{j}{i}\binom{2i}{i-j}$. We now consider the set of partial $2$-Motzkin paths with $m$ marked R-visible up steps and $m+1$ elevation lines such that there is exactly one marked R-visible up step between two adjacent elevation lines. We now have a combinatorial interpretation of the summand in (\[cam\]).

The summand in (\[cam\]) counts partial $2$-Motzkin paths of length $i-1$ ending at level $j-1$ with $m$ marked R-visible up steps and $m+1$ elevation lines such that there is exactly one marked step between two adjacent elevation lines.

Let $P$ be a partial $2$-Motzkin path of length $i-1$ ending at level $j-1$. Suppose that there are $m$ marked R-visible up steps with initial points at levels $j_1, j_2, \ldots, j_m$. Let $t_1=j_1$ and $t_{i}=j_{i}-j_{i-1}-1$ with $j_{m+1}=j-1$ for $i\geq 2$. Then one see that the number of ways to choose the $m+1$ elevation lines such that there is exactly $m+1$ marked R-visible up step is equals to $$(t_1+1) (t_2+1) \cdots (t_m+1).$$ Note that the $t_i$’s range over $t_1+t_2+\cdots +t_{m+1}=j-m-1$. Thus, the number of partial $2$-Motzkin paths of length $i-1$ ending at level $j-1$ with the required marked steps and elevation lines equal $$\label{c.1}
\sum_{t_1+t_2+\ldots t_{m+1}=j-1-m}(t_1+1)(t_2+1)\cdots
(t_{m+1}+1).$$ Let $g(x)=\sum_{n\geq 0}(n+1)x^n$. It is clear that $g(x)={1\over
(1-x)^2}$. Hence the summation (\[c.1\]) equals the coefficient of $x^{j-1-m}$ in the expansion of ${1\over (1-x)^{2m+2}}$, that is, the binomial coefficient ${j+m\choose 2m+1}$.

In fact, we may give a combinatorial interpretation of the binomial coefficient ${j+m \choose 2m+1}$ in the above proof. Let $P$ be a partial $2$-Motzkin path of length $i-1$ ending at level $j-1$ with $m$ marked R-visible up steps and $m+1$ elevation lines such that there is exactly one marked up step between two adjacent elevation lines. Suppose that the $k$-th elevation line and the $k$-th marked up step of $P$ are at level $x_k$ and $y_k$, respectively. Such a configuration can be represented as follows: $$t_1\, | \, t_2 \, * \,  t_3\,  |\,  t_4\, * \,  t_5\, | \, \cdots \,  |
\,  t_{2m}  \,  * \, t_{2m+1} \,  |\,  t_{2m+2} ,$$ where $t_i$ denotes the numbers of unmarked R-visible up steps. It is clear that we have $t_1+t_2+\ldots+t_{2m+2}=j-1-m$, and the number of solutions of this equation equals the numbers of ways to distribute $j-1-m$ balls into $2m+2$ boxes when a box can have more than one ball. So this number equals the binomial coefficient ${ j+m \choose 2m+1}$.

We are now ready to give a combinatorial proof of the identity of Cameron and Nkwanta. We recall that a $2$-Motzkin path have two kind of horizontal steps, straight steps and wavy steps. We now need to introduce the third kind of horizontal steps – dotted steps. Therefore, the left hand side of (\[cam\]) is the number of free $3$-Motzkin paths with exactly $m$ dotted horizontal steps. We now give the following bijection that leads to a combinatorial interpretation of (\[cam\]).

\[cameron\] There is a bijection between partial $2$-Motzkin paths of length $i$ with $m$ marked R-visible up steps and $m+1$ elevation lines such that there is exactly one marked step between two adjacent elevation lines and free $3$-motzkin paths of length $i$ with exactly $m$ dotted horizontal steps.

Suppose that $P=P_1U^*P_2U^*\ldots P_{m}U^*P_{m+1}$ is a partial $2$-Motzkin path with $m$ marked R-visible up steps and $m+1$ elevation lines, we get a free $3$-motzkin path by changing all the marked up steps to dotted horizontal steps and applying the elevation operation for each $P_k$.

Conversely, given a free $3$-Motzkin path $P=P_1  \dashrightarrow P_2\dashrightarrow \cdots  P_{m}
\dashrightarrow P_{m+1}$ with $m$ dotted horizontal steps, where $\dashrightarrow$ denotes a dotted horizontal step, then we can get a partial $2$-motzkin path by changing each dotted horizontal step to a marked up step and the L-visible down steps of each $P_k$ to up steps by elevating their end points.

(138,30) (-0.15,0)[(1,1)[4]{}]{} (0.15,0)[(1,1)[4]{}]{}(4,4)(4.5,5)(5,4) (5,4)(5.5,3)(6,4) (6,4)(6.5,5)(7,4) (7,4)(7.5,3)(8,4) (8,4)[(1,1)[4]{}]{} (12,8)[(1,0)[4]{}]{} (16,8)[(1,-1)[4]{}]{} (20,4)[(1,1)[8]{}]{} (28,12)[(1,-1)[8]{}]{} (36,4)[(1,1)[4]{}]{} (39.85,8)[(1,1)[8]{}]{} (40.15,8)[(1,1)[8]{}]{}(42.5,9)[$*$]{} (40,8)[(1,1)[12]{}]{} (52,20)[(1,0)[4]{}]{} (0,4)(3,0)[20]{}[(1,0)[1]{}]{} (0,16)(3,0)[20]{}[(1,0)[1]{}]{} (0,0) (4,4) (8,4) (12,8) (16,8) (20,4) (24,8) (28,12) (32,8) (36,4) (40,8) (44,12) (48,16) (52,20) (56,20) (63,5)[$\longleftrightarrow$]{} (79.85,8)[(1,-1)[4]{}]{} (80.15,8)[(1,-1)[4]{}]{}(84,4)(84.5,5)(85,4) (85,4)(85.5,3)(86,4) (86,4)(86.5,5)(87,4) (87,4)(87.5,3)(88,4) (88,4)[(1,1)[4]{}]{} (92,8)[(1,0)[4]{}]{} (96,8)[(1,-1)[4]{}]{} (100,4)[(1,1)[8]{}]{} (108,12)[(1,-1)[8]{}]{} (116,4)[(1,1)[4]{}]{} (120,8)(1,0)[5]{}[(1,0)[0.4]{}]{} (123.85,8)[(1,-1)[4]{}]{} (124.15,8)[(1,-1)[4]{}]{}(128,4)[(1,1)[4]{}]{} (132,8)[(1,0)[4]{}]{} (80,8) (84,4) (88,4) (92,8) (96,8) (100,4) (104,8) (108,12) (112,8) (116,4) (120,8) (124,8) (128,4) (132,8) (136,8)

We conclude this section by giving a more general identity. Let $a_{i,j,k}$ be the number of partial $k$-Motzkin paths of length $i-1$ ending at level $j-1$. Then we have $$\label{cameron1}
\binom{i-1}{m}k^{i-1-m}=\sum_{j=1}^{i}a_{i,j,k-2}\binom{j+m}{2m+1}.$$

A Dyck path generalization of (\[eq1.1\])
=========================================

In this section, we give a Dyck path generalization of the matrix identity (\[eq1.1\]) on the little Schröder numbers. A $k$-Dyck path is a Dyck path in which an up step is colored by one of the $k$ colors $\{ 1, 2, \ldots, k\}$ if it not immediately followed by a down step . In this section, we aim to give the following generalization of (\[eq1.1\]).

Let $M=(m_{i,j})$ be a lower triangular matrix with the first column being the weight of $(t^2-t)$-Dyck paths of length $2i$. The other columns of $M$ are given by the following relation: $$\label{eq.6}
m_{i,j}=m_{i-1,j-1}+(t^2-t+1)m_{i-1,j}+(t^2-t)m_{i-1,j+1}.$$ Then we have the following matrix identity $$\label{eq.t}
(m_{i,j}) \times
\begin{bmatrix} 1 \\ t^2-(t-1)^2 \\     \ t^3-(t-1)^3 \\ \vdots
\end{bmatrix} = \begin{bmatrix} 1 \\ t^2+t \\   (t^2+t)^{2} \\
\vdots
\end{bmatrix}.$$

The matrix identity (\[eq1.1\]) is a consequence of (\[eq.t\]) by setting $t=2$. By using generating functions, one can verify that the number of $2$-Dyck paths of length $2n$ equals the number of little Schröder paths of length $n$.

We now proceed to give a combinatorial proof of (\[eqt.t\]). To this end, we need to give a combinatorial interpretation of the entries in the matrix $M$ in (\[eq.t\]). We may define a composition of $k$-Dyck path $P$ as a sequence of $k$-Dyck paths $(P_1, P_2, \ldots, P_j)$ such that $P=P_1P_2\cdots P_j$, where $j$ is called the number of segments.

Let $a_{i,j}$ be the sum of weights of compositions of $(t^2-t)$-Dyck paths of length $2i$ with $j$ segments. Then $a_{i,j}$ satisfies the recurrence relation (\[eq.6\]).

The proof of the above lemma is similar to that of Lemma \[dotheom\]. Let us rewrite (\[eq.t\]) as follows $$\label{eqt.t}
\sum_{j\geq 1}m_{i,j}(t^j-(t-1)^j)=(t^2+t)^{i-1}.$$

In order to deal with $m_{i,j}(t^j-(t-1)^j)$ combinatorially, we introduce a coloring scheme on a composition of a $(t^2-t)$-Dyck path with $j$ segments. Suppose that we have $t$ colors $c_1, c_2,
\ldots, c_t$. If we use these $t$ colors to color the $j$ segments such that the first color $c_1$ must be used, then there are $t^j-(t-1)^j$ ways to accomplish such colorings. We simply call such colorings [*$t$-feasible colorings*]{}.

We can now present a bijection leading to a combinatorial proof of (\[eqt.t\]).

There is a bijection between the set of compositions of $(t^2-t)$-Dyck paths of length $2i$ with a $t$-feasible coloring on the segments and the set of sequences of length $i-1$ on $t^2+t$ letters.

The desired bijection $\sigma$ is constructed as follows. Let $(P_1, P_2, \ldots, P_j)$ be a composition of a $(t^2-t)$-Dyck path $P$ of length $2i$ with a $t$-feasible coloring on the segments. We will use the following alphabet that contains $t^2+t$ letters: $$\label{alphabet}
 \{ \alpha_r,  \;|\;
1\leq r\leq t\} \cup \{ \beta_s, \;|\; 1\leq s\leq t-1\} \cup \{
\gamma_{k} \; | \; 1 \leq k \leq t^2-t\} \cup \{ \delta\}.$$

For $i=1$, both the composition and the $t$-feasible coloring are unique. We set the corresponding sequence to be empty. For $i\geq 2$, we consider the following cases:

1.  If $P_1=UD$, $P_1$ is colored by $c_r$ ($1\leq r\leq t$) and $(P_2, \ldots, P_j)$ still has a $t$-feasible coloring. Then we set $\sigma(P_1, \ldots P_j)=\alpha_r \sigma(P_2, \ldots, P_j)$.

2.  If $P_1=UD$, $P_1$ is colored by $c_1$ and $(P_2, \ldots, P_j)$ does not inherit a $t$-feasible coloring. Assume that $P_2$ is colored by $c_{s+1}$ ($1\leq s\leq t-1$). Then we change the color of $P_2$ to $c_1$ and set $\sigma(P_1, \ldots, P_j)=\beta_s \sigma(P_2, \ldots, P_j)$.

3.  If $P_1=UDQ$, where $Q$ is not empty. Then we set $\sigma(P_1, \ldots, P_j)=\delta\sigma(Q, P_2, \ldots, P_j)$.

4.  If $P_1=UQD$, where $Q$ is not empty and the first up step of $P$ has color $k$ ($1 \leq k \leq
    t^2-t$) because the first step of $Q$ is an up step. Then we set $\sigma(P_1, \ldots, P_j)=\gamma_{k}
     \sigma(Q, P_2, \ldots, P_j)$.

5.  If $P_1=U Q_1 D Q_2$, neither $Q_1$ nor $Q_2$ is empty and the first up step of $P$ has color $c_k$. Since $k$ ranges from $1$ to $t(t-1)$, we may encode a color $c_k$ by a pair of colors $(c_p, c_q)$ where $p$ ranges from $1$ to $t$ and $q$ ranges from $1$ to $t-1$. Moreover, we may use $(c_r, \beta_s)$ to denote a color $c_k$. Then we assign color $c_r$ to $Q_1$, pass the color of $P_1$ to $Q_2$, and set $\sigma(P)=\beta_s\sigma(Q_1, Q_2, P_2, \ldots, P_j)$.

For each case, the resulting path is always a sequence of length $i-1$.

In order to show that $\sigma$ is a bijection, we proceed to construct the inverse map of $\sigma$. Let $S$ be a sequence of length $i-1$ on the alphabet (\[alphabet\]). If $i=1$, then we get the unique Dyck path $UD$ and the unique composition with a $t$-feasible coloring. Note that the up step in the Dyck path $UD$ is not colored. We now assume that $i>1$. It is easy to check that Cases 1, 3, and 4 are reversible. It remains to show that Cases 2 and 5 are reversible. In fact, we only need to ensure that Case 2 and Case 5 can be distinguished from each other. For Case 2, either $j=2$ or $(P_3, \ldots, P_j)$ does not have a $t$-feasible coloring. On the other hand, for Case 5, $(Q_2,
P_2,\ldots, P_j)$ is always nonempty and it has a $t$-feasible coloring. This completes the proof.

We also have a combinatorial interpretation of the matrix identity (\[eq1.1\]) based on little Schröder paths. The idea is similar to the proof given above, so the proof is omitted.

[**Acknowledgments.**]{} This work was supported by the 973 Project on Mathematical Mechanization, the National Science Foundation, the Ministry of Education, and the Ministry of Science and Technology of China. The third author is partially supported by NSF grant HRD 0401697.

[100]{}

E. Barcucci, A. del Lungo, E. Pergola and R. Pinzani, A construction for enumerating $k$-coloured Motzkin paths, Lecture Notes in Computer Science, Vol. 959, Springer, Berlin, 1995, pp. 254-263.

M. Aigner, Catalan-like numbers and determinants, [*J. Combin. Theory, Ser. A*]{}, 87 (1999) 33-51.

D. Callan, A combinatorial interpretation of a Catalan numbers identity, [*Math. Mag.*]{}, 72 (1999) 295-298.

N. Cameron and A. Nkwanta, On some (pseado) involutions in the Riordan group, [*J. Integer Sequences*]{}, 8 (2005), Article 05.3.7.

R. Chapman, Moments of Dyck paths, [*Discrete Math.*]{}, 204 (1999) 113-117.

E. Deutsch, Dyck path enumeration, [*Discrete Math.*]{}, 204 (1999) 167-202.

E. Deutsch and L. Shapiro, A bijection between ordered trees and $2$-Motzkin paths and its many consequences, [*Discrete Math.*]{}, 256 (2002) 655-670.

F. Harary and R. C. Read, The enumeration of tree-like polyhexes, [ *Proc. Edinburgh Math. Soc.*]{}, (2) 17 (1970) 1-13.

L. Shapiro, Bijections and the Riordan group, [*Theoretical Computer Science*]{}, 307 (2003) 403-413.

L. Shapiro, S. Getu, Wen-Jin Woan, and L.C. Woodson, The Riordan group, [*Discrete Appl. Math.*]{}, 34 (1991) 229-239.

L. Shapiro, Wen-Jin Woan, and S. Getu, Runs, slides and moments, [ *SIAM J. Alg. Disc. Math.*]{}, 4 (1983), 459-466.

L. Shapiro, A Catalan triangle, [*Discrete Math.*]{}, 14 (1976), 83-90.

N.J.A. Sloane, S. Plouffe, The Encyclopedia of Integer Sequence, Academic Press, San Diego, 1995, online at [www.research.att.com/126 njas/sequences/]{}.

R. Sprugnoli, Riordan arrays and combinatorial sums, [*Discrete Math.*]{}, 132 (1994) 267-290.

R.P. Stanley, [*Enumerative Combinatorics, Vol. 2*]{}, Cambridge University Press, Cambridge, 1999.

R.A. Sulanke, Moments of generalized Motzkin pahts, [*J. Integer Sequences*]{}, 3 (2000) 00.1.1.

Wen-Jin Woan, L. Shapiro, and D.G. Rogers, The Catalan numbers, the Lebesgue integral, and $4^{n-2}$, [*The Amer. Math. Monthly*]{}, 104 (1997) 927-931.
