\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 & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 \\ 4 & 0 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 \\ 5 & 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 \end{array} \right] , \] \[ (m_{n,k})=\left[ \begin{array}{ccccccc} n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 14 & 6 & 1 & 0 & 0 \\ 4 & 42 & 48 & 27 & 8 & 1 & 0 \\ 5 & 132 & 165 & 110 & 44 & 10 & 1 \end{array} \right] , \] \[ (b_{n,k})=\left[ \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 5 & 4 & 1 & 0 & 0 & 0 \\ 0 & 14 & 14 & 6 & 1 & 0 & 0 \\ 0 & 42 & 48 & 27 & 8 & 1 & 0 \\ 0 & 132 & 165 & 110 & 44 & 10 & 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 & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 2 & 3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 4 & 12 & 13 & 6 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 8 & 36 & 66 & 63 & 33 & 9 & 1 & 0 & 0 \\ 4 & 0 & 16 & 96 & 248 & 360 & 321 & 180 & 62 & 12 & 1 & 0 \\ 5 & 32 & 240 & 800 & 1560 & 1970 & 1683\ & 985 & 390 & 100 & 15 & 1 \end{array} \right] , \] \[ (m_{n,k})=\left[ \begin{array}{ccccccc} n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 11 & 6 & 1 & 0 & 0 & 0 \\ 3 & 45 & 31 & 9 & 1 & 0 & 0 \\ 4 & 197 & 156 & 60 & 12 & 1 & 0 \\ 5 & \ 903 & \ 785 & 372 & 98 & 15 & 1 \end{array} \right] , \] \[ (b_{n,k})=\left[ \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 6 & 1 & 0 & 0 & 0 \\ 0 & 45 & 31 & 9 & 1 & 0 & 0 \\ 0 & 197 & 156 & 60 & 12 & 1 & 0 \\ 0 & \ 903 & \ 785 & 360 & 98 & 15 & 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 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 3 & 4 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 9 & 24 & 22 & 8 & 1 & 0 & 0 \\ 3 & 0 & 27 & 108 & 171 & 136 & 57 & 12 & 1 & 0 \\ 4 & 81 & 432 & 972 & 1200 & 886 & 400 & 108 & 16 & 1 \end{array} \right] , \] \[ (m_{n,k})=\left[ \begin{array}{cccccc} n\backslash k & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 4 & 1 & 0 & 0 & 0 \\ 2 & 19 & 8 & 1 & 0 & 0 \\ 3 & 100 & 54 & 12 & 1 & 0 \\ 4 & 562 & 352 & 105 & 16 & 1 \end{array} \right] , \] \[ (b_{n,k})=\left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 4 & 1 & 0 & 0 & 0 \\ 0 & 19 & 8 & 1 & 0 & 0 \\ 0 & 100 & 54 & 9 & 1 & 0 \\ 0 & 562 & 356 & 105 & 16 & 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} & & & & & & & & & & & & \\ & \circ & & & & & & & & & \circ & & \circ \\ \times & & \circ & & & & & & & \circ & & \circ & \\ & & & \circ & & & \circ & & \circ & & & & \\ & & & & \bullet & \circ & & \circ & & & & & \end{array} \in A(12,1) \] \[ P' = = \begin{array}{ccccccccccccc} & & & & & & & & & & & \circ & \\ & & & & & & & & & & \circ & & \circ \\ & & & & & & & & & \circ & & & \\ & & & & & & \circ & & \bullet & & & & \\ & & & & & \circ & & \circ & & & & & \\ & & \circ & & \circ & & & & & & & & \\ \times & \circ & & \circ & & & & & & & & & \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*} &&\left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 4 & 1 & 0 & 0 & 0 \\ 14 & 14 & 6 & 1 & 0 & 0 \\ 42 & 48 & 27 & 8 & 1 & 0 \\ 132 & 165 & 110 & 44 & 10 & 1 \end{array} \right] \left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{array} \right] \\ &=&\left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 & 0 \\ 20 & 15 & 6 & 1 & 0 & 0 \\ 70 & 56 & 28 & 8 & 1 & 0 \\ 252 & 210 & 120 & 45 & 10 & 1 \end{array} \right] . \end{eqnarray*} For Example \ref{TWO} \begin{eqnarray*} &&\left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 11 & 6 & 1 & 0 & 0 & 0 \\ 45 & 31 & 9 & 1 & 0 & 0 \\ 197 & 156 & 60 & 12 & 1 & 0 \\ \ 903 & \ 785 & 360 & 98 & 15 & 1 \end{array} \right] \left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 & 0 \\ 4 & 0 & 2 & 0 & 1 & 0 \\ 0 & 4 & 0 & 2 & 0 & 1 \end{array} \right] \\ &=&\left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 13 & 6 & 1 & 0 & 0 & 0 \\ 63 & 33 & 9 & 1 & 0 & 0 \\ 321 & 180 & 62 & 12 & 1 & 0 \\ 1683\ & 985 & 390 & 100 & 15 & 1 \end{array} \right] . \end{eqnarray*} $\ $ For Example \ref{THREE} \begin{eqnarray*} &&\left[ \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 19 & 8 & 1 & 0 & 0 \\ 100 & 54 & 12 & 1 & 0 \\ 562 & 352 & 105 & 16 & 1 \end{array} \right] \left[ \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 3 & 0 & 1 & 0 & 0 \\ 0 & 3 & 0 & 1 & 0 \\ 9 & 0 & 3 & 0 & 1 \end{array} \right] \\ &=&\left[ \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 22 & 8 & 1 & 0 & 0 \\ 136 & 57 & 12 & 1 & 0 \\ 886 & 400 & 108 & 16 & 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 &=& \sum_{k=-n}^na_{n,k} \\ &=& \sum_{k=-n}^{-1} a_{n,k}+a_{n,0}+ \sum_{k=1}^n a_{n,k} \\ &=& \sum_{k=1}^n c^k a_{n,k}+a_{n,0}+ \sum_{k=1}^n a_{n,k} \\ &=& 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 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 & 0 \\ 20 & 15 & 6 & 1 & 0 & 0 \\ 70 & 56 & 28 & 8 & 1 & 0 \\ 252 & 210 & 120 & 45 & 10 & 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 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 13 & 6 & 1 & 0 & 0 & 0 \\ 63 & 33 & 9 & 1 & 0 & 0 \\ 321 & 180 & 62 & 12 & 1 & 0 \\ 1683\ & 985 & 390 & 100 & 15 & 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 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 22 & 8 & 1 & 0 & 0 \\ 136 & 57 & 12 & 1 & 0 \\ 886 & 400 & 108 & 16 & 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 & 1 & 0 & 0 & 0 & 0 \\ \times & \times & 1 & 0 & 0 & 0 \\ \times & \times & \times & 1 & 0 & 0 \\ \times & \times & \times & \times & 1 & 0 \\ \times & \times & \times & \times & \times & 1 \\ \times & \times & \times & \times & \times & \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 & 1 & 0 & 0 & 0 & 0 \\ d & b & 1 & 0 & 0 & 0 \\ 0 & c & b & 1 & 0 & 0 \\ 0 & 0 & c & b & 1 & 0 \\ 0 & 0 & 0 & c & b & 1 \\ 0 & 0 & 0 & 0 & c & 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 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{array} \right] ,\;\;\;\;S_{(m_{n,k})}=\left[ \begin{array}{cccccc} 2 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 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 & 1 & 0 & 0 & 0 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 0 & 2 & 3 & 1 & 0 & 0 \\ 0 & 0 & 2 & 3 & 1 & 0 \\ 0 & 0 & 0 & 2 & 3 & 1 \\ 0 & 0 & 0 & 0 & 2 & 3 \end{array} \right] ,\;\;S_{(m_{n,k})}=\left[ \begin{array}{cccccc} 3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 0 & 2 & 3 & 1 & 0 & 0 \\ 0 & 0 & 2 & 3 & 1 & 0 \\ 0 & 0 & 0 & 2 & 3 & 1 \\ 0 & 0 & 0 & 0 & 2 & 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 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 4 & 1 & 0 & 0 & 0 \\ 14 & 14 & 6 & 1 & 0 & 0 \\ 42 & 48 & 27 & 8 & 1 & 0 \\ 132 & 165 & 110 & 44 & 10 & 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 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 11 & 6 & 1 & 0 & 0 & 0 \\ 45 & 31 & 9 & 1 & 0 & 0 \\ 197 & 156 & 60 & 12 & 1 & 0 \\ \ 903 & \ 785 & 360 & 98 & 15 & 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 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 19 & 8 & 1 & 0 & 0 \\ 100 & 54 & 12 & 1 & 0 \\ 562 & 352 & 105 & 16 & 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 & 1 & 0 & 0 & 0 & 0 \\ c & b & 1 & 0 & 0 & 0 \\ 0 & c & b & 1 & 0 & 0 \\ 0 & 0 & c & b & 1 & 0 \\ 0 & 0 & 0 & c & b & 1 \\ 0 & 0 & 0 & 0 & c & 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 & 1 & 0 & 0 & 0 & 0 \\ d & b & 1 & 0 & 0 & 0 \\ 0 & c & b & 1 & 0 & 0 \\ 0 & 0 & c & b & 1 & 0 \\ 0 & 0 & 0 & c & b & 1 \\ 0 & 0 & 0 & 0 & c & 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) &=& \frac 1{1-ax-dxf}\frac{1\ +(k-a-c-1)f+(c-d)f^2}{(1-f)(1-cf)} \\ &=&\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)} \\ &=& \frac 1{1-ax-dxf}\frac{\frac fx-af-df^2}{(1-f)(1-cf)} \\ &=&\frac f{x(1-f)(1-cf)}\\ &=&\frac f{x(1-f-cf+cf^2)} \\ &=&\frac f{x-xf-cxf+cxf^2}\\ &=&\frac f{f-xbf-xf-cxf} \\ &=&\frac f{f-xf(b+c+1)}\\ &=&\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 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{array} \right] \;,\;A=\left[ \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 5 & 9 & 5 & 1 & 0 & 0 \\ 14 & 28 & 20 & 7 & 1 & 0 \\ 42 & 90 & 75 & 35 & 9 & 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 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 5 & 9 & 5 & 1 & 0 & 0 \\ 14 & 28 & 20 & 7 & 1 & 0 \\ 42 & 90 & 75 & 35 & 9 & 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 & 1 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 \\ 0 & 2 & 3 & 1 & 0 \\ 0 & 0 & 2 & 3 & 1 \\ 0 & 0 & 0 & 2 & 3 \end{array} \right] ,\;A=\left[ \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 6 & 5 & 1 & 0 & 0 \\ 22 & 23 & 8 & 1 & 0 \\ 90 & 107 & 49 & 11 & 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 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 6 & 5 & 1 & 0 & 0 \\ 22 & 23 & 8 & 1 & 0 \\ 90 & 107 & 49 & 11 & 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}