\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{amsthm} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{xca}[theorem]{Exercise} \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} \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 Recursive Relation for Weighted Motzkin Sequences} \vskip 1cm \large Wen-jin Woan\\ Department of Mathematics\\ Howard University\\ Washington, D.C. 20059\\ USA \\ \href{mailto:wwoan@howard.edu}{\tt wwoan@howard.edu} \\ \end{center} \vskip .2 in \begin{abstract} We consider those lattice paths that use the steps {\it Up\/}, {\it Level\/}, and {\it Down\/} with assigned weights $w$, $u$, and $v$. In probability theory, the total weight is 1. In combinatorics, we regard weight as the number of colors and normalize by setting $w=1$. The lattice paths generate Motzkin sequences. Here we give a combinatorial proof of a three-term recursion for a weighted Motzkin sequence and we find the radius of convergence. \end{abstract} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{proposition}{Proposition}[section] %\newtheorem{corollary}{Corollary}[section] %\newtheorem{lemma}{Lemma}[section] %\maketitle \section{Introduction} We consider those lattice paths in the Cartesian plane starting from $(0,0)$ that use the steps $U$, $L$, and $D$, where $U=(1,1)$, an up-step; $L=(1,0)$, a level-step; and $D=(1,-1)$, a down-step. Let $c$ and $d$ be positive integers, and color the $L$ steps with $d$ colors and the $D$ steps with $c$ colors. Let $ A(n,k)$ be the set of all colored 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}=\left| A(n,k)\right|$, $m_{n,k}=\left| M(n,k)\right|$, and $m_n=\left| M(n,0)\right|$. The number $m_n$ is called the $ (1,d,c)$-Motzkin number. Let $B(n,k)$ denote the set of lattice paths in $ A(n,k)$ that never return to the $x$-axis and let $b_{n,k}=\left| B(n,k)\right|$. Note that $a_{n,k}=a_{n-1,k-1}+da_{n-1,k}+ca_{n-1,k+1}$. Here we give a combinatorial proof of the following three-term recursion for the $(1,d,c)$-Motzkin sequence: \[ (n+2)m_n=d(2n+1)m_{n-1}+(4c-d^2)(n-1)m_{n-2}. \] If $\frac{\sqrt{c}}2\leq d$, then $\displaystyle \lim_{n\to\infty }\frac{m_n}{m_{n-1}}=k=d+2\sqrt{c}$. \begin{example}\label{example1} The first few terms of the $(1,3,2)$-Motzkin numbers are $ m_0=1,3,11,45,197,903,\ldots$, $k=3+2\sqrt{2}$. This sequence is the little Schroeder number sequence and is Sloane's sequence \seqnum{A001003}. Some entries of the matrices $(a_{n,k}), \;(m_{n,k})$ and $(b_{n,k})$ are as follows; \[ (a_{n,k})=\left[ \begin{tabular}{cccccccccc} $n/k$ & $-4$ & $-3$ & $-2$ & $-1$ & $0$ & $1$ & $2$ & $3$ & $4$ \\ $0$ & $0$ & $0$ & $0$ & $0$ & $1$ & $0$ & $0$ & $0$ & $0$ \\ $1$ & $0$ & $0$ & $0$ & $2$ & $3$ & $1$ & $0$ & $0$ & $0$ \\ $2$ & $0$ & $0$ & $4$ & $12$ & $13$ & $6$ & $1$ & $0$ & $0$ \\ $3$ & $0$ & $8$ & $36$ & $66$ & $63$ & $33$ & $9$ & $1$ & $0$ \\ $4$ & $16$ & $96$ & $248$ & $360$ & $321$ & $180$ & $62$ & $12$ & $1$% \end{tabular} \right] , \] \[ (m_{n,k})=\ \left[ \begin{array}{cccccc} n/k & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 \\ 2 & 11 & 6 & 1 & 0 & 0 \\ 3 & 45 & 31 & 9 & 1 & 0 \\ 4 & 197 & 156 & 60 & 12 & 1 \end{array} \right] , \] \[ (b_{n,k})=\left[ \begin{array}{ccccccc} n/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 3 & 1 & 0 & 0 & 0 \\ 3 & 0 & 11 & 6 & 1 & 0 & 0 \\ 4 & 0 & 45 & 31 & 9 & 1 & 0 \\ 5 & 0 & 197 & 156 & 60 & 12 & 1 \end{array} \right] . \] \end{example} \begin{example}\label{example2} The first few terms of the $(1,2,1)$-Motzkin numbers are $ m_0=1,2,5,14,42,\ldots , k=2+2\sqrt{1}=4$. This sequence is the Catalan sequence, Sloane's sequence \seqnum{A000108}.\end{example} \begin{example}\label{example3} The first few terms of the $(1,1,1)$-Motzkin numbers are $ m_0=1,1,2,4,9,21,\ldots , k=1+2\sqrt{1}=3$. The sequence is the Motzkin sequence, discussed by Woan \cite{Wo}, and is Sloane's sequence \seqnum{A001006}.\end{example} \section{Main Results} We apply the cut and paste technique to prove the following lemma. Please refer to Dershowitz and Zaks \cite{DZ} and Pergola and Pinzani \cite{PP} for information about the technique. \begin{lemma}\label{lemma1}There is a combinatorial proof for the equation $ m_n=b_{n+1,1}=db_{n,1}+cb_{n,2}=dm_{n-1}+cb_{n,2}$.\end{lemma} \begin{proof} Let $P\in B(n+1,1).$ Remove the first step $(U)$ and note that the remaining is in $M(n,0)$. \end{proof} For example, the path $P=UULDLUUUDDLD\in B(12,1)$ becomes $Q=ULDLUUUDDLD\in M(11)$ where $\times $ marks the origin. \[ P= \begin{array}{ccccccccccccc} & & & & & & & & \circ & & & & \\ & & & & & & & \circ & & \circ & & & \\ & & \circ & \circ & & & \circ & & & & \circ & \circ & \\ & \circ & & & \circ & \circ & & & & & & & \circ \\ \times & & & & & & & & & & & & \end{array} , \] \[ Q= \begin{array}{cccccccccccc} & & & & & & & \circ & & & & \\ & & & & & & \circ & & \circ & & & \\ & \circ & \circ & & & \circ & & & & \circ & \circ & \\ \times & & & \circ & \circ & & & & & & & \circ \end{array} . \] \begin{theorem}\label{theorem2} There is a combinatorial proof for the equation $ (n+1)b_{n+1,1}=a_{n+1,1}$.\end{theorem} \begin{proof} Wendel \cite{We} proved a similar result. Let $$S(n+1)=\{P^{*}:P\in B(n+1,1)$$ where $P^{*}$ is $P$ with one vertex marked$\}$. Then $\left| S(n+1)\right| =(n+1)b_{n+1,1}$. Let $P^{*}\in S(n+1)$. The marked vertex partitions the path into $P=FB,$ where $F$ is the front section and $B$ is the back section. Then $Q=BF\in A(n+1,1)$. Note that, graphically, the point of attachment is the rightmost lowest point of $Q$. Conversely, starting with any path we may find the rightmost lowest point of $Q$ and reverse the procedure to create a marked path $P^{*}$ in $B(n+1,1)$.\end{proof} For example, \[ P^{*}= \begin{array}{ccccccccccccc} & & & & & & & & \circ & & & & \\ & & & & & & & \circ & & \circ & & & \\ & & \circ & \bullet & & & \circ & & & & \circ & \circ & \\ & \circ & & & \circ & \circ & & & & & & & \circ \\ \times & & & & & & & & & & & & \end{array} \in S(12), \] \[ \rightarrow Q= \begin{array}{ccccccccccccc} & & & & & & & & & & & & \\ & & & & & \circ & & & & & & & \\ & & & & \circ & & \circ & & & & & \circ & \circ \\ \times & & & \circ & & & & \circ & \circ & & \circ & & \\ & \circ & \circ & & & & & & & \bullet & & & \end{array} \in A(12,1). \] \begin{proposition}\label{proposition3} The total number of $L$ steps in $M(n)$ is the same as that in $B(n+1,1)$ and is $da_{n,1}$.\end{proposition} \begin{proof} From the proof of Lemma \ref{lemma1}, there is a bijection between $M(n)$ and $ B(n+1,1)$. Let $P=FLB\in B(n+1,1)$ with an $L$ step. Then $Q=BF\in A(n,1)$. Note that the attachment point is the rightmost lowest point in $Q$ since $ P\in B(n+1,1)$. This identification suggests the inverse mapping. Note that there are $d$ colors for an $L$ step.\end{proof} For example, \[ P= \begin{array}{ccccccccccccc} & & & & & & & & \circ & & & & \\ & & & & & & & \circ & & \circ & & & \\ & & \bullet & \bullet & & & \circ & & & & \circ & \circ & \\ & \circ & & & \circ & \circ & & & & & & & \circ \\ \times & & & & & & & & & & & & \end{array} \in B(12,1), \] \[ \rightarrow Q= \begin{array}{cccccccccccc} & & & & & & & & & & & \\ & & & & & \circ & & & & & & \\ & & & & \circ & & \circ & & & & & \circ \\ \times & & & \circ & & & & \circ & \circ & & \circ & \\ & \circ & \circ & & & & & & & \bullet & & \end{array} \in A(11,1). \] \begin{proposition}\label{proposition4} There is a combinatorial proof for the equation $$\displaystyle a_{n,0}=m_n+\frac 12(nm_n-da_{n,1})=b_{n+1,1}+\frac 12(nb_{n+1,1}-dnb_{n,1}).$$ \end{proposition} \begin{proof} Let $T(n)=\{P^e:P\in M(n)$ where $P^e$ is $P$ with a $U$ step marked$\}$. By Theorem \ref{theorem2} and Proposition \ref{proposition3} the number of $L$ steps among all paths in $ M(n)$ is $da_{n,1}=dnb_{n,1}$. The total number of steps among all paths in $ M(n)$ is $nm_n=nb_{n+1,1}$, hence the total number of $U$ steps among all paths in $M(n)$ is $\frac 12(nb_{n+1,1}-dnb_{n,1})=\left| T(n)\right|$. Let $P^e=FUB\in T(n)$ with a $U$ step marked. Then $Q=BUF\in A(n,0)-M(n,0)$ and the initial point of $U$ in $Q$ is the rightmost lowest point in $Q$. The inverse mapping starts with the rightmost lowest point. Note that $\left| M(n,0)\right| =m_n=b_{n+1,1}$\end{proof} For example, \[ P^e= \begin{array}{cccccccccccc} & & & & \circ & & \circ & \circ & & & & \\ & & & \bullet & & \circ & & & \circ & & & \\ & \circ & \bullet & & & & & & & \circ & \circ & \\ \times & & & & & & & & & & & \circ \end{array} \in T(11), \] \[ Q= \begin{array}{cccccccccccc} & \circ & & \circ & \circ & & & & & & & \\ \times & & \circ & & & \circ & & & & & \circ & \circ \\ & & & & & & \circ & \circ & & \bullet & & \\ & & & & & & & & \bullet & & & \end{array} \in A(11,0). \] \begin{proposition}\label{proposition5} There is a combinatorial proof for the equation \begin{eqnarray*} a_{n,0}&=&a_{n-1,-1}+da_{n-1,0}+ca_{n-1,1}=2ca_{n-1,1}+da_{n-1,0}\\ &=&2c(n-1)b_{n-1,1}+d(b_{n,1}+\frac 12((n-1)b_{n,1}-d(n-1)b_{n-1,1}))\,. \end{eqnarray*} \end{proposition} \begin{proof} The first equality represents the partition of $A(n,0)$ by the last step ($U$, $L$ or $D$). The second equality represents the fact that $ a_{n-1,-1}=ca_{n-1,1}$, since elements in $A(n-1,-1)$ have one more $D$ step than those in $A(n-1,1)$. And the last equality holds by Theorem \ref{theorem2} and Proposition \ref{proposition4}.\end{proof} Sulanke \cite{S} proved the following result for the Motzkin sequence. \begin{theorem}\label{theorem6} $(n+2)m_n=(2dn+d)m_{n-1}+(4c-d^2)(n-1)m_{n-2}.$ \end{theorem} \begin{proof} By Propositions \ref{proposition4} and \ref{proposition5} \begin{eqnarray*} b_{n+1,1}+\frac 12(nb_{n+1,1}-dnb_{n,1})&=&2c(n-1)b_{n-1,1}+db_{n,1}+(\frac 12((n-1)b_{n,1}-d(n-1)b_{n-1,1}))\,. \end{eqnarray*} By Lemma \ref{lemma1} \begin{eqnarray*} m_n+\frac 12(nm_n-dnm_{n-1}).&=&2c(n-1)m_{n-2}+dm_{n-1}+d(\frac 12((n-1)m_{n-1}-d(n-1)m_{n-2}))\,. \end{eqnarray*} Equivalently \[ (n+2)m_n=(2dn+d)m_{n-1}+(4c-d^2)(n-1)m_{n-2}\,. \] \end{proof} \begin{theorem}\label{theorem7} $\displaystyle \lim_{n\to \infty} \frac{m_n}{m_{n-1}}=k=d+2\sqrt{c}$. \end{theorem} \begin{proof} By Theorem \ref{theorem6}, let \[ s_n:=\frac{m_n}{m_{n-1}}=\frac{d(2n+1)}{n+2}+(\frac{(4c-d^2)(n-1)}{ n+2})\frac{m_{n-2}}{m_{n-1}}\,, \] and let \begin{eqnarray*} a_n&:=&\frac{d(2n+1)}{n+2}=2d-\frac{3d}{n+2}\\ b_n&:=&\frac{ (4c-d^2)(n-1)}{n+2}=\ (4c-d^2)(1-\frac 3{n+2}). \end{eqnarray*} Then $s_n=a_{n+}\frac{b_n}{s_{n-1}}$. If the sequence $s_n=a_{n+}\frac{b_n}{s_{n-1}}$ has limit $k$, then $ k^2=2dk+(4c-d^2)$ and $k=\frac{2d+\sqrt{4d^2+4(4c-d^2)}}2=d+2\sqrt{c}$. \medskip\noindent {\bf Case 1}. $4c-d^2\geq 0$. If $s_{n-1}\leq k,$ then \begin{eqnarray*} s_n &=&a_{n+}\frac{b_n}{s_{n-1}}\geq 2d-\frac{3d}{n+2}+\frac{(4c-d^2)\frac{ n-1}{n+2}}k=k-\frac{3dk+3(4c-d^2)}{k(n+2)} \\ \ \ \ &=&k-\frac{3k^2-3dk}{k(n+2)}=k-\frac{3(k-d)}{n+2} \end{eqnarray*} and \begin{eqnarray*} s_{n+1}&=&a_{n+1}+\frac{b_{n+1}}{s_n}\leq 2d-\frac{3d}{n+3}+\frac{ (4c-d^2)(\frac n{n+3})}{k-\frac{3(k-d)}{n+2}}\\ &=&2d-\frac{3d}{n+3}+\frac{\left( 4c-d^2\right) }k(1-\frac{3\ dn+9d-3k}{% (n+3)(kn-k+3d)})\\ &=&2d+\frac{\left( 4c-d^2\right) }k-\frac{3d}{n+3}- \frac{\left( 4c-d^2\right) }k\frac{3\ dn+9d-3k}{(n+3)(kn-k+3d)}\\ &=&k-\frac{3(2dn(k-d)-(k-d)(k-3d))}{(n+3)(kn-k+3d)}\\ &=&k-\frac{% 6(k-d)(d(n+1)-\sqrt{c})}{(n+3)(kn-k+3d)}. \end{eqnarray*} Note that $s_1=\frac d1$ and $s_2=\frac{d^2+c}d=d+\frac cd$. If $\frac{\sqrt{c}} 2\leq d$, then $s_1,s_2\leq k.$ By induction on both odd and even $n$ we have \[k-\frac{3(k-d)}{n+3}\leq s_{n+1}\leq k-\frac{6(k-d)(d(n+1)-\sqrt{c})}{ (n+3)(kn-k+3d)}\leq k\,.\] and $\displaystyle \lim_{n\to \infty }\frac{m_n}{m_{n-1}}=k$. \medskip\noindent {\bf Case 2}. $4c-d^2<0$. Inductively, assuming that $s_{n-1}\leq k$ and $\{s_i\}$ is nondecreasing up to $n-1$. Then \begin{eqnarray*} s_n &=&a_{n+}\frac{b_n}{s_{n-1}}\leq 2d-\frac{3d}{n+2}+\frac{(4c-d^2)\frac{ n-1}{n+2}}k=k-\frac{3dk+3(4c-d^2)}{k(n+2)} \\ &=&k-\frac{3k^2-3dk}{k(n+2)}=k-\frac{3(k-d)}{n+2}0\,. \end{eqnarray*} By induction $\{s_i\}$ is a bounded nondecreasing sequence and \[\lim_{n\to \infty }\frac{m_n}{m_{n-1}}=k\,.\] \end{proof} \begin{thebibliography}{9} \bibitem{DZ} N. Dershowitz and S. Zaks, The cycle lemma and some applications, {\it European J. Combin.\/} {\bf 11} (1990), 34--40. \bibitem{PP} E. Pergola and R. Pinzani, A combinatorial interpretation of the area of Schroeder paths, {\it Electron. J. Combin.\/} {\bf 6} (1999), Research paper 40, 13 pp. \bibitem{S} R. Sulanke, Moments of generalized Motzkin paths, {\it J. Integer Seq.\/} {\bf 3} (2000), Article 00.1.1. \bibitem{We} J. Wendel, Left-continuous random walk and the Lagrange expansion, {\it Amer. Math. Monthly} {\bf 82} (1975), 494--499. \bibitem{Wo} W. Woan, A Combinatorial proof of a recursive relation of the Motzkin sequence by Lattice Paths {\it Fibonacci Quart.\/} {\bf 40} (2002), 3--8. \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}, \seqnum{A001003}, and \seqnum{A001006}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 9 2005; revised version received February 24 2005. Published in {\it Journal of Integer Sequences}, February 28 2005. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document} \end{document}