<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{amsthm}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
A Relation Between Restricted and \\
\vskip .1in
Unrestricted Weighted Motzkin Paths
}
\vskip 1cm
\large
Wen-jin Woan \\
Howard University \\
Washington, DC  20059  \\
USA \\
\href{mailto:wwoan@fac.howard.edu}{\tt wwoan@fac.howard.edu} \\
\end{center}

\vskip .2 in
\begin{abstract}
We consider those lattice paths that use the steps ``up'', ``level'', and
``down'' with assigned weights $w,b,c$. In probability theory, the total weight
is $1$. In combinatorics, we replace weight by the number of colors. Here
we give a combinatorial proof of a relation between restricted and
unrestricted weighted Motzkin paths.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}

%\usepackage[usenames]{color}
%\usepackage{graphicx}
%\usepackage{amscd}
%\usepackage[colorlinks=true,
%linkcolor=webgreen, filecolor=webbrown,
%citecolor=webgreen]{hyperref}
%\usepackage{color}
%\usepackage{fullpage}
%\usepackage{float}
%\usepackage{psfig}
%\usepackage{graphics,amsmath,amssymb}
%\usepackage{latexsym}
%\usepackage{epsf}


\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} 
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{remar}[theorem]{Remark}
\newenvironment{remark}{\begin{remar}\normalfont\quad}{\end{remar}}

\section{Introduction}

We consider those lattice paths in the Cartesian plane starting from
$(0,0)$ that use the steps $\{U,L,D\}$, where $U=(1,1)$, an up-step,
$L=(1,0)$, a level-step and $D=(1,-1),$ a down-step, with assigned
weights $w,b$, and $c $. In probability theory, the total weight is 1.
In combinatorics, we regard weight as the number of colors and
normalize by setting $w=1$. Let $P$ be a path.   We define the weight
$w(P)$ to be the product of the weight of the steps.  Let $A(n,k)$ be
the set of all weighted lattice paths ending at the point $(n,k),$ and
let $M(n,k)$ be the set of lattice paths in $A(n,k)$ that never go
below the $x$-axis. Let $a_{n,k}$ be the sum of all $w(P)$ with $P$ in
$A(n,k)$ and let $m_{n,k}$ be the sum of all $w(P)$ with $P$
in $M(n,k)$.
Note that 
$$a_{n,k}=a_{n-1,k-1}+ba_{n-1,k}+ca_{n-1,k+1},$$
and the same
relationship holds for $b_{n,k}$ and $m_{n,k}$.   In combinatorics,
we regard the weights as the number of colors. Then $A(n,k)$ is the set
of all colored lattice paths ending at the point $(n,k)$ and $M(n,k)$
is the set of all colored lattice paths in $A(n,k)$ that never go below
the $x$-axis.  Then $a_{n,k}=\left| A(n,k)\right|$, $m_{n,k}=\left|
M(n,k)\right|$, and $ m_n=\left| M(n,0)\right| $. The sequence
$\{ m_n \}$ is called the $bc$-Motzkin sequence for the $bc$-Motzkin
lattice path. Let $B(n,k)$ denote the set of lattice paths in $A(n,k)$
that never return to the $x$-axis after the initial $U$ step and let
$b_{n,k}=\left| B(n,k)\right|.$  Note that the paths in $M(n,k)$ and
$B(n,k)$ are restricted paths. For definitions and results please refer
to Stanley \cite{RS}.

\section{Some Examples}

\begin{example}
\label{ONE} For $b=2,\;c=1,$ all matrices are infinite by infinite. Partial
entries are as follows:
\end{example}

\[
(a_{n,k})=\ \left[ \
\begin{array}{cccccccccccc}
n\backslash k &amp; -5 &amp; -4 &amp; -3 &amp; -2 &amp; -1 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 4 &amp; 6 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 0 &amp; 0 &amp; 1 &amp; 6 &amp; 15 &amp; 20 &amp; 15 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 0 &amp; 1 &amp; 8 &amp; 28 &amp; 56 &amp; 70 &amp; 56 &amp; 28 &amp; 8 &amp; 1 &amp; 0 \\
5 &amp; 1 &amp; 10 &amp; 45 &amp; 120 &amp; 210 &amp; 252 &amp; 210 &amp; 120 &amp; 45 &amp; 10 &amp; 1
\end{array}
\right] ,
\]

\[
(m_{n,k})=\left[
\begin{array}{ccccccc}
n\backslash k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 5 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 14 &amp; 14 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 42 &amp; 48 &amp; 27 &amp; 8 &amp; 1 &amp; 0 \\
5 &amp; 132 &amp; 165 &amp; 110 &amp; 44 &amp; 10 &amp; 1
\end{array}
\right] ,
\]

\[
(b_{n,k})=\left[
\begin{array}{ccccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 5 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 14 &amp; 14 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 42 &amp; 48 &amp; 27 &amp; 8 &amp; 1 &amp; 0 \\
0 &amp; 132 &amp; 165 &amp; 110 &amp; 44 &amp; 10 &amp; 1
\end{array}
\right] .
\]

The $21$-Motzkin sequence $1,2,5,14,42,132,..$. of the first column of $%
(m_{n,k})$ is the Catalan sequence (Sloane's \seqnum{A000108}). 
Please refer to Stanley \cite{RS}.

\begin{example}
\label{TWO} For $b=3$, $c=2,$ partial entries are as follows$:$
\end{example}

\[
(a_{n,k})=\ \ \left[
\begin{array}{cccccccccccc}
n\backslash k &amp; -5 &amp; -4 &amp; -3 &amp; -2 &amp; -1 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 0 &amp; 0 &amp; 0 &amp; 4 &amp; 12 &amp; 13 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 0 &amp; 0 &amp; 8 &amp; 36 &amp; 66 &amp; 63 &amp; 33 &amp; 9 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 0 &amp; 16 &amp; 96 &amp; 248 &amp; 360 &amp; 321 &amp; 180 &amp; 62 &amp; 12 &amp; 1 &amp; 0 \\
5 &amp; 32 &amp; 240 &amp; 800 &amp; 1560 &amp; 1970 &amp; 1683\  &amp; 985 &amp; 390 &amp; 100 &amp; 15 &amp; 1
\end{array}
\right] ,
\]

\[
(m_{n,k})=\left[
\begin{array}{ccccccc}
n\backslash k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 11 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 45 &amp; 31 &amp; 9 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 197 &amp; 156 &amp; 60 &amp; 12 &amp; 1 &amp; 0 \\
5 &amp; \ 903 &amp; \ 785 &amp; 372 &amp; 98 &amp; 15 &amp; 1
\end{array}
\right] ,
\]

\[
(b_{n,k})=\left[
\begin{array}{ccccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 11 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 45 &amp; 31 &amp; 9 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 197 &amp; 156 &amp; 60 &amp; 12 &amp; 1 &amp; 0 \\
0 &amp; \ 903 &amp; \ 785 &amp; 360 &amp; 98 &amp; 15 &amp; 1
\end{array}
\right] .
\]

The $32$-Motzkin sequence $1,3,11,45,197,..$.of the first column of 
$(m_{n,k})$ is the little Schroeder sequence (Sloane's \seqnum{A001003}).

\begin{example}
\label{THREE} Let $b=4,c=3$.  Partial entries are as follows:
\end{example}

$\ $%
\[
(a_{n,k})=\ \ \left[
\begin{array}{cccccccccc}
n\backslash k &amp; -4 &amp; -3 &amp; -2 &amp; -1 &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; 0 &amp; 0 &amp; 3 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 0 &amp; 0 &amp; 9 &amp; 24 &amp; 22 &amp; 8 &amp; 1 &amp; 0 &amp; 0 \\
3 &amp; 0 &amp; 27 &amp; 108 &amp; 171 &amp; 136 &amp; 57 &amp; 12 &amp; 1 &amp; 0 \\
4 &amp; 81 &amp; 432 &amp; 972 &amp; 1200 &amp; 886 &amp; 400 &amp; 108 &amp; 16 &amp; 1
\end{array}
\right] ,
\]

\[
(m_{n,k})=\left[
\begin{array}{cccccc}
n\backslash k &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 19 &amp; 8 &amp; 1 &amp; 0 &amp; 0 \\
3 &amp; 100 &amp; 54 &amp; 12 &amp; 1 &amp; 0 \\
4 &amp; 562 &amp; 352 &amp; 105 &amp; 16 &amp; 1
\end{array}
\right] ,
\]

\[
(b_{n,k})=\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 19 &amp; 8 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 100 &amp; 54 &amp; 9 &amp; 1 &amp; 0 \\
0 &amp; 562 &amp; 356 &amp; 105 &amp; 16 &amp; 1
\end{array}
\right] .
\]

\section{Main results}

We now give a bijective proof for

\begin{theorem}
\label{FOUR}  $a_{n,k}=\sum_{i=0}c^im_n,_{2i+k}$ for $ n,k \geq 0.$
\end{theorem}

\begin{proof}
Let $P$ be a lattice path in $A(n,k)$.  Find the leftmost lowest point
of the path, and let this point be $p = (m,-i)$.  Now we obtain path
$P'$ in $M(n,2i+k)$ from $P$ as follows:  first, replace $U$ with $D$,
and $D$ with $U$ for the section of $P$ before the point $p$.  Next,
reverse the order of those steps and attach those steps to the end of
the rest of the path.  This gives us a path $P'$ with $i$ fewer down
steps and $w(P)= c^i w(P')$. Note that the attached point is the
rightmost point of height $i+k$; this identification suggests the
inverse mapping.  \end{proof}

\begin{example}
\label{FIVE} Let\ $P=(UDDD)LUDUUUDU\ \in A(15,1),\;P' =LUDUUUDU\
(UUUD)\in M(15,5).$
\end{example}

\[
P=\
\begin{array}{ccccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\
&amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ \\
\times &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  \\
&amp;  &amp;  &amp; \circ &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  \\
&amp;  &amp;  &amp;  &amp; \bullet &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;
\end{array}
\in A(12,1)
\]

\[
P' = =
\begin{array}{ccccccccccccc}
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  \\
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ \\
&amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp;  &amp;  \\
&amp;  &amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \bullet &amp;  &amp;  &amp;  &amp;  \\
&amp;  &amp;  &amp;  &amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  \\
&amp;  &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\
\times &amp; \circ &amp;  &amp; \circ &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;
\end{array}
\in M(12,2*2+1)
\]

\begin{remark}
\label{SIX} Theorem \ref{FOUR} shows us the relationship between $(m_{n,k})$
and $(a_{n,k}).$
\end{remark}

For Example \ref{ONE}

\begin{eqnarray*}
&amp;&amp;\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
5 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
14 &amp; 14 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
42 &amp; 48 &amp; 27 &amp; 8 &amp; 1 &amp; 0 \\
132 &amp; 165 &amp; 110 &amp; 44 &amp; 10 &amp; 1
\end{array}
\right] \left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\
1 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 1
\end{array}
\right] \\
&amp;=&amp;\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
6 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
20 &amp; 15 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
70 &amp; 56 &amp; 28 &amp; 8 &amp; 1 &amp; 0 \\
252 &amp; 210 &amp; 120 &amp; 45 &amp; 10 &amp; 1
\end{array}
\right] .
\end{eqnarray*}

For Example \ref{TWO}

\begin{eqnarray*}
&amp;&amp;\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
11 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
45 &amp; 31 &amp; 9 &amp; 1 &amp; 0 &amp; 0 \\
197 &amp; 156 &amp; 60 &amp; 12 &amp; 1 &amp; 0 \\
\ 903 &amp; \ 785 &amp; 360 &amp; 98 &amp; 15 &amp; 1
\end{array}
\right] \left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 2 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 0 &amp; 2 &amp; 0 &amp; 1 &amp; 0 \\
0 &amp; 4 &amp; 0 &amp; 2 &amp; 0 &amp; 1
\end{array}
\right] \\
&amp;=&amp;\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
13 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
63 &amp; 33 &amp; 9 &amp; 1 &amp; 0 &amp; 0 \\
321 &amp; 180 &amp; 62 &amp; 12 &amp; 1 &amp; 0 \\
1683\  &amp; 985 &amp; 390 &amp; 100 &amp; 15 &amp; 1
\end{array}
\right] .
\end{eqnarray*}

$\ $

For Example \ref{THREE}

\begin{eqnarray*}
&amp;&amp;\left[
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
19 &amp; 8 &amp; 1 &amp; 0 &amp; 0 \\
100 &amp; 54 &amp; 12 &amp; 1 &amp; 0 \\
562 &amp; 352 &amp; 105 &amp; 16 &amp; 1
\end{array}
\right] \left[
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 3 &amp; 0 &amp; 1 &amp; 0 \\
9 &amp; 0 &amp; 3 &amp; 0 &amp; 1
\end{array}
\right] \\
&amp;=&amp;\left[
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
22 &amp; 8 &amp; 1 &amp; 0 &amp; 0 \\
136 &amp; 57 &amp; 12 &amp; 1 &amp; 0 \\
886 &amp; 400 &amp; 108 &amp; 16 &amp; 1
\end{array}
\right] .
\end{eqnarray*}
$\ $

We now give a bijective proof for

\begin{theorem}
\label{SEVEN} $a_{n,-k}=c^ka_{n,k}.$
\end{theorem}

\begin{proof}
Let $P$ be in $A(n,-k)$. Then $P$ has $k$ more $D$ steps than $U$
steps. We obtain $P' \in A(n,k)$ from $P$ by interchanging $D$
steps and $U$ steps. Then $P$ has $k$ more $D$ steps than $P'.$
Hence $a_{n,-k}=c^ka_{n,k}.$ 
\end{proof}

For examples, see Examples 1, 2 and 3.

We now give a bijective proof for

\begin{theorem}
\label{EIGHT} 
$(1+b+c)^n=\sum_{k=-n}^na_{n,k}=a_{n,0}+ \sum_{k=1}^n(c^k+1)a_{n,k}.$
\end{theorem}

\begin{proof}
For each step we have $(1+b+c)$ choices. Let us index the columns of 
$(a_{n,k})$ by the power $k$ of $y$.  The generating function going from one
row to next is multiplied by $w(y)=y+b+cy^{-1}$.  Hence the generating
function of the $n^{th}$ row of $(a_{n,k})$ is $w(y)^n$.   By setting $y=1$
we have
\begin{eqnarray*}
(1+b+c)^n &amp;=&amp; \sum_{k=-n}^na_{n,k} \\
&amp;=&amp; \sum_{k=-n}^{-1} a_{n,k}+a_{n,0}+ \sum_{k=1}^n a_{n,k} \\
&amp;=&amp; \sum_{k=1}^n c^k a_{n,k}+a_{n,0}+ \sum_{k=1}^n a_{n,k} \\
&amp;=&amp; a_{n,0}+\sum_{k=1}^n(c^k+1)a_{n,k}.  
\end{eqnarray*}
\end{proof}

\begin{remark}
\label{NINE} Apply Theorem \ref{EIGHT} to
\end{remark}

Example \ref{ONE}:

\[
\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
6 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
20 &amp; 15 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
70 &amp; 56 &amp; 28 &amp; 8 &amp; 1 &amp; 0 \\
252 &amp; 210 &amp; 120 &amp; 45 &amp; 10 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
2 \\
2 \\
2 \\
2 \\
2
\end{array}
\right] =\left[
\begin{array}{c}
1 \\
4 \\
16 \\
64 \\
256 \\
1024
\end{array}
\right] .
\]
$.$

Example \ref{TWO}

\[
\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
13 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
63 &amp; 33 &amp; 9 &amp; 1 &amp; 0 &amp; 0 \\
321 &amp; 180 &amp; 62 &amp; 12 &amp; 1 &amp; 0 \\
1683\  &amp; 985 &amp; 390 &amp; 100 &amp; 15 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
3 \\
5 \\
9 \\
17 \\
33
\end{array}
\right] =\left[
\begin{array}{c}
1 \\
6 \\
36 \\
216 \\
1296 \\
7776
\end{array}
\right] .
\]
$\ $

$\ $

Example \ref{THREE}

\[
\left[
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
22 &amp; 8 &amp; 1 &amp; 0 &amp; 0 \\
136 &amp; 57 &amp; 12 &amp; 1 &amp; 0 \\
886 &amp; 400 &amp; 108 &amp; 16 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
4 \\
10 \\
28 \\
82
\end{array}
\right] =\left[
\begin{array}{c}
1 \\
8 \\
64 \\
512 \\
4096
\end{array}
\right] .
\]

Please refer to Getu \cite{GSWW} for Riordan matrices.

\begin{definition}
A lower triangular matrix $A=(g,f)$ is said to be a $Riordan$ matrix if the
generating function $A_k$ of the $k^{th}$ column is $gf^k$, where $%
g=g(x)=1+g_1x+g_2x^2+ \cdots$ and $f=f(x)=x+f_2x^2+f_3x^3+ \cdots$.
Let $R$ be the
set of all Riordan matrices.
\end{definition}

\begin{lemma}
Let $D=(d_{n,k})=(g,f)$ $\in R\;$and $A=[a_i]$ a column vector with
generating function $A(x)=\sum a_ix^i$. Then the generating function for $%
B=DA$ is $gA(f)$.
\end{lemma}

\begin{proof}
$b_n=\sum a_i([x^n]gf^i)=[x^n]\sum a_igf^i=[x^n]gA(f).$
\end{proof}

\begin{remark}
Let $M=(g,f)$ and $N=(h,l)$ be in $R$.  Then $MN=(g,f)(k,l)=(gk(f),l(f))\;$
and $R$ is a group with $(g,f)^{-1}=(\frac 1{g(f^{-1})},f^{-1})$.
\end{remark}

\begin{definition}
For each $A\in R$,\ we define the $Stieltjes$\ Matrix. $S_A=A^{-1}\overline{A%
}$ \ or $AS_A=\overline{A}$,\ where $\overline{A}\;$is the matrix obtaining
from $A$ by removing the first row.\ The entries of the $Stieltjes\;$%
matrix are of the following form:
\end{definition}

\[
S_A=\left[
\begin{array}{cccccc}
\times &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
\times &amp; \times &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
\times &amp; \times &amp; \times &amp; 1 &amp; 0 &amp; 0 \\
\times &amp; \times &amp; \times &amp; \times &amp; 1 &amp; 0 \\
\times &amp; \times &amp; \times &amp; \times &amp; \times &amp; 1 \\
\times &amp; \times &amp; \times &amp; \times &amp; \times &amp; \times
\end{array}
\right] .
\]

For the following Remark please refer to Peart \cite{PW} and Spitzer \cite
{FS}.

\begin{remark}
Let $A=(g,f)\in R\;$be a matrix with tridiagonal Stieltjes matrix of the form
\end{remark}

\ $\left[
\begin{array}{cccccc}
a &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
d &amp; b &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; c &amp; b &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; c &amp; b &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; c &amp; b &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; c &amp; b
\end{array}
\right] .$

Then$\;f=f(x)=x(1+bf+cf^2),\;g=\frac 1{1-ax-dxf}$.

For Example \ref{ONE}, $f=x(1+2f+f^2)=\frac{1-2x-\sqrt{1-4x}}{2x}\ ,$

$(a_{n,k})=(g,f)\;$with $g=\frac 1{1-2x-2xf},$

$(m_{n,k})=(\frac fx,f),$

\[
S_{(a_{n,k})}=\left[
\begin{array}{cccccc}
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2
\end{array}
\right] ,\;\;\;\;S_{(m_{n,k})}=\left[
\begin{array}{cccccc}
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2
\end{array}
\right]
\]
$.$

For Example \ref{TWO}, $f=x(1+3f+2f^2)=\frac{1-3x-\sqrt{1-6x+x^2}}{4x},$

$(a_{n,k})=(g,f)\;$with $g=\frac 1{1-3x-4xf},$

$(m_{n,k})=(\frac fx,f),$

\[
S_{(a_{n,k})}=\left[
\begin{array}{cccccc}
3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
4 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 2 &amp; 3 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 2 &amp; 3 &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 2 &amp; 3 &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 3
\end{array}
\right] ,\;\;S_{(m_{n,k})}=\left[
\begin{array}{cccccc}
3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 2 &amp; 3 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 2 &amp; 3 &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 2 &amp; 3 &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 3
\end{array}
\right] .
\]

\begin{theorem}
\label{FIFTEEN} For $bc$-Motzkin sequences we have
$(m_{n,k})(\frac 1{1-cx^2},x)=(a_{n,k}).$
\end{theorem}

\begin{proof}
It follows by Theorem \ref{FOUR}.
\end{proof}

\begin{theorem}
\label{SIXTEEN} For $bc$-Motzkin sequences we have
$(a_{n,k})(\frac 1{1-cx}+\frac x{1-x})=\frac 1{1-kx},\;k=1+b+c.$
\end{theorem}

\begin{proof}
By Theorem \ref{EIGHT}.
\end{proof}

\begin{theorem}
\label{SEVENTEEN} For $bc$-Motzkin sequences we have
$(m_{n,k})(\frac 1{(1-cx)(1-x)}\ )=\frac 1{1-kx}.$
\end{theorem}

\begin{proof}
By Theorems \ref{FIFTEEN}, \ref{SIXTEEN}.
\end{proof}

\begin{remark}
Apply Theorem \ref{SEVENTEEN} to
\end{remark}

Example \ref{ONE}.

\[
\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
5 &amp; 4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
14 &amp; 14 &amp; 6 &amp; 1 &amp; 0 &amp; 0 \\
42 &amp; 48 &amp; 27 &amp; 8 &amp; 1 &amp; 0 \\
132 &amp; 165 &amp; 110 &amp; 44 &amp; 10 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
2 \\
3 \\
4 \\
5 \\
6
\end{array}
\right] =\left[
\begin{array}{c}
1 \\
4 \\
16 \\
64 \\
256 \\
1024
\end{array}
\right] .
\]
$.$

Example \ref{TWO}. Please refer to Cameron \cite{CN} for this example.

\[
\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
11 &amp; 6 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
45 &amp; 31 &amp; 9 &amp; 1 &amp; 0 &amp; 0 \\
197 &amp; 156 &amp; 60 &amp; 12 &amp; 1 &amp; 0 \\
\ 903 &amp; \ 785 &amp; 360 &amp; 98 &amp; 15 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
3 \\
7 \\
15 \\
31 \\
63
\end{array}
\right] =\left[
\begin{array}{c}
1 \\
6 \\
36 \\
216 \\
1296 \\
7776
\end{array}
\right] .
\]

Example \ref{THREE}.

\[
\left[
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
19 &amp; 8 &amp; 1 &amp; 0 &amp; 0 \\
100 &amp; 54 &amp; 12 &amp; 1 &amp; 0 \\
562 &amp; 352 &amp; 105 &amp; 16 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
4 \\
13 \\
40 \\
121
\end{array}
\right] \ =\left[
\begin{array}{c}
1 \\
8 \\
64 \\
512 \\
4096
\end{array}
\right]
\]
$.$

\begin{remark}
Theorem \ref{SEVENTEEN} applies only to Stieltjes matrices of the form
\end{remark}

\[
\left[
\begin{array}{cccccc}
b &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
c &amp; b &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; c &amp; b &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; c &amp; b &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; c &amp; b &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; c &amp; b
\end{array}
\right]
\]
$.$

The following is a generalization.

\begin{theorem}
\label{TWENTY} Let $A=(g,f)\in R\;$be a Riordan matrix with tridiagonal
Stieltjes matrix of the form
\end{theorem}

\[
\left[
\begin{array}{cccccc}
a &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
d &amp; b &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; c &amp; b &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; c &amp; b &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; c &amp; b &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; c &amp; b
\end{array}
\right]
\]
$\;$and\ $A(x)=\frac{\ (1-cx)+(k-a-1)x+(c-d)x^2}{(1-x)(1-cx)},$

then $(g,f)A(x)=\frac 1{1-kx},$ where $k=1+b+c$.

\begin{proof}
Let
$
A(x)=1+(k-a)x+[(k-a-1)c+(c-d)+(k-a)]x^2+[((k-a-1)c+c-d)c+(k-a-1)c+(c-d)+(k-a)]x^3+ \cdots .
$

Then
$\ A(x)-xA(x)=\frac{\ (1-cx)+(k-a-1)x+(c-d)x^2}{1-cx}\ .\ $

Now
\begin{eqnarray*}
(g,f)A(x) &amp;=&amp; \frac 1{1-ax-dxf}\frac{1\ +(k-a-c-1)f+(c-d)f^2}{(1-f)(1-cf)} \\
&amp;=&amp;\frac 1{1-ax-dxf}\frac{1\ +(b-a)f+(c-d)f^2}{(1-f)(1-cf)}=\frac 1{1-ax-dxf}
\frac{1+bf+cf^2-af-df^2}{(1-f)(1-cf)} \\
&amp;=&amp; \frac 1{1-ax-dxf}\frac{\frac fx-af-df^2}{(1-f)(1-cf)} \\
&amp;=&amp;\frac f{x(1-f)(1-cf)}\\
&amp;=&amp;\frac f{x(1-f-cf+cf^2)} \\
&amp;=&amp;\frac f{x-xf-cxf+cxf^2}\\
&amp;=&amp;\frac f{f-xbf-xf-cxf} \\
&amp;=&amp;\frac f{f-xf(b+c+1)}\\
&amp;=&amp;\frac 1{1-kx}.
\end{eqnarray*}
\end{proof}

\begin{remark}
Apply Theorem \ref{TWENTY} and Peart \cite{PW}.
\end{remark}

Example \ref{ONE}.

\[
S_A=\left[
\begin{array}{cccccc}
1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2
\end{array}
\right] \;,\;A=\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
5 &amp; 9 &amp; 5 &amp; 1 &amp; 0 &amp; 0 \\
14 &amp; 28 &amp; 20 &amp; 7 &amp; 1 &amp; 0 \\
42 &amp; 90 &amp; 75 &amp; 35 &amp; 9 &amp; 1
\end{array}
\right] =(g,f),
\]

where $f=x(1+2f+\ f^2)=\frac{1-2x-\sqrt{1-4x}}{2x}\ ,$ $g=\frac 1{1-x-xf}=%
\frac{1-\sqrt{1-4x}}2\ ,$

$A(x)=\frac{1+x}{(1-x)(1-x)}=1+3x+5x^2+7x^3+9x^4+11x^5+13x^6+O\left(
x^7\right) ,$

\[
\left[
\begin{array}{cccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 3 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
5 &amp; 9 &amp; 5 &amp; 1 &amp; 0 &amp; 0 \\
14 &amp; 28 &amp; 20 &amp; 7 &amp; 1 &amp; 0 \\
42 &amp; 90 &amp; 75 &amp; 35 &amp; 9 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
3 \\
5 \\
7 \\
9 \\
11
\end{array}
\right] =\left[
\begin{array}{c}
1 \\
4 \\
16 \\
64 \\
256 \\
1024
\end{array}
\right] .
\]

$\ $

Example \ref{TWO}.

\[
S_A=\left[
\begin{array}{ccccc}
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 3 &amp; 1 &amp; 0 &amp; 0 \\
0 &amp; 2 &amp; 3 &amp; 1 &amp; 0 \\
0 &amp; 0 &amp; 2 &amp; 3 &amp; 1 \\
0 &amp; 0 &amp; 0 &amp; 2 &amp; 3
\end{array}
\right] ,\;A=\left[
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
6 &amp; 5 &amp; 1 &amp; 0 &amp; 0 \\
22 &amp; 23 &amp; 8 &amp; 1 &amp; 0 \\
90 &amp; 107 &amp; 49 &amp; 11 &amp; 1
\end{array}
\right] =(g,f),
\]

where $f=x(1+3f+2f^2)=\frac{1-3x-\sqrt{1-6x+x^2}}{4x}\ ,$ $g=\frac
1{1-2x-2xf},$

$A(x)=\frac{1+x}{(1-x)(1-2x)}\
=1+4x+10x^2+22x^3+46x^4+94x^5+190x^6+382x^7+O\left( x^8\right) ,$

\[
\ \left[
\begin{array}{ccccc}
1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
2 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
6 &amp; 5 &amp; 1 &amp; 0 &amp; 0 \\
22 &amp; 23 &amp; 8 &amp; 1 &amp; 0 \\
90 &amp; 107 &amp; 49 &amp; 11 &amp; 1
\end{array}
\right] \left[
\begin{array}{c}
1 \\
4 \\
10 \\
22 \\
46
\end{array}
\right] \ =\left[
\begin{array}{c}
1 \\
6 \\
36 \\
216 \\
1296
\end{array}
\right] .
\]
$.$\bigskip\

\section{Acknowledgments}
The author wishes to thank the referee for the valuable comments that
improved the presentation of the paper.


\begin{thebibliography}{9}
\bibitem{CN}  N. Cameron and A. Nkwanta,
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html}{On some (Pseudo) involutions in the Riordan group}, \textit{J. Integer Seq.}, {\bf 8} (2005), article 05.3.7.

\bibitem{GSWW}  S. Getu, L. Shapiro, W. J. Woan and L. Woodson, The Riordan
groups, \textit{Discrete Appl. Math.}, {\bf 34} (1991), 229--239.

\bibitem{PW}  P. Peart and W. J. Woan,
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL3/PEART/peart1.html}{Generating functions via Hankel and
Stieltjes matrices}, \textit{J. Integer Seq.}, {\bf 3} (2000), article 00.2.1.

\bibitem{FS}  F. Spitzer, \textit{Principles of Random Walk}, Van Nostrand,
Princeton, 1964.

\bibitem{RS}  R. Stanley, \textit{Enumerative Combinatorics}, Vol. 2,
Cambridge University Press, 1999.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A19.

\noindent \emph{Keywords: } Motzkin paths, combinatorial identity.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108} and
\seqnum{A001003}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 4 2005;
revised version received January 28 2006.  
Published in {\it Journal of Integer Sequences}, January 29 2006.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>