\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,amsthm} \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 Note on the Enumeration of Diffusion \\ \vskip .05in Walks in the First Octant by Their Number \\ \vskip .1in of Contacts with the Diagonal} \vskip 1cm \large Heinrich Niederhausen\\ Department of Mathematical Sciences\\ Florida Atlantic University\\ Boca Raton, FL 33431\\ USA \\ \href{mailto:Niederhausen@math.fau.edu}{\tt Niederhausen@math.fau.edu}\\ \end{center} \vskip .2 in \begin{abstract} Diffusion walks take steps in the four directions N, E, S, and W. We derive a closed form for the number of diffusion walks from the origin to some point $\left( n,n\right) $ on the diagonal in $k$ steps inside the first octant, touching the diagonal exactly $c$ times. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] % \documentclass[12pt]{article} %\usepackage{amsmath} %\usepackage{amssymb} %\usepackage{amsfonts} %\usepackage{graphicx} \setcounter{MaxMatrixCols}{30} %\newtheorem{theorem}{Theorem} %\newtheorem{acknowledgement}[theorem]{Acknowledgement} %\newtheorem{algorithm}[theorem]{Algorithm} %\newtheorem{axiom}[theorem]{Axiom} %\newtheorem{case}[theorem]{Case} %\newtheorem{claim}[theorem]{Claim} %\newtheorem{conclusion}[theorem]{Conclusion} %\newtheorem{condition}[theorem]{Condition} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{criterion}[theorem]{Criterion} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{example}[theorem]{Example} %\newtheorem{exercise}[theorem]{Exercise} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{notation}[theorem]{Notation} %\newtheorem{problem}[theorem]{Problem} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{remark}[theorem]{Remark} %\newtheorem{solution}[theorem]{Solution} %\newtheorem{summary}[theorem]{Summary} %\begin{document} \section{Notation and Results} A diffusion walk is a random walk in the square lattice $\mathbb{Z}^{2}$, equally likely taking one of the four unit steps $North=\left( 0,1\right) $, $South=\left( 0,-1\right) $, $East=\left( 1,0\right) $, and $West=\left( -1,0\right) $. The walk stays in the first octant, also called principal wedge, if it only visits lattice points $\left( n,m\right) $ satisfying $0\leq m\leq n$. We will call such restricted diffusion walks \emph{octant walks} in this paper. We denote by $D_{2k}\left( 0_{\rightarrow}n;c\right) $ the number of octant walks from $\left( 0,0\right) $ to $\left( n,n\right) $ taking $2k$ steps and contacting the diagonal $y=x$ exactly $c$ times. Note that the start and end point of such walks are counted as contacts with the diagonal. The walks may self-intersect, and they may touch (contact) but not cross either boundary of the octant. Synonyms for contacts are \emph{visits}, and \emph{points of adsorption}. Figure \ref{fig:DiffusionExample} shows a path from $\left( 0,0\right) $ to $\left( 3,3\right) $ making four visits.% %TCIMACRO{\TeXButton{B}{\begin{table}[h] \centering}}% %BeginExpansion \begin{table}[h] \centering %EndExpansion $% \begin{tabular} [c]{llllllll} & 0 & 1 & 2 & 3 & 4 & 5 & 6\\\cline{7-8}% 5 & & & & & & \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}} & \multicolumn{1}{|l|}{}\\\cline{6-8}% 4 & & & & & \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$\hspace {9pt}_{\downarrow}^{\bullet}$} & \multicolumn{1}{|l}{$^{\leftarrow\bullet}$} & \multicolumn{1}{|l|}{$^{\leftarrow\bullet}$}\\\cline{5-8}% 3 & & & & \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$_{\hspace{9pt}\circ} $} & \multicolumn{1}{|l}{$\hspace{9pt}_{\downarrow}^{\bullet}$} & \multicolumn{1}{|l}{} & \multicolumn{1}{|l|}{$\hspace{9pt}_{\bullet}% ^{\uparrow}$}\\\cline{4-8}% 2 & & & \multicolumn{1}{|l}{$_{\bullet\longrightarrow}$\rule[-7pt]% {0pt}{21pt}} & \multicolumn{1}{|l}{$_{\bullet\longrightarrow}^{\hspace {9pt}\uparrow}$} & \multicolumn{1}{|l}{$_{\bullet\longrightarrow}% ^{\hspace{9pt}\downarrow}$} & \multicolumn{1}{|l}{$_{\bullet\longrightarrow} $} & \multicolumn{1}{|l|}{$\hspace{9pt}_{\bullet}^{\uparrow}$}\\\cline{3-8}% 1 & & \multicolumn{1}{|l}{} & \multicolumn{1}{|l}{$_{\bullet}^{\uparrow}$} & \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$\hspace{9pt}_{\bullet}^{\uparrow}$} & \multicolumn{1}{|l}{$\hspace{9pt}_{\downarrow}^{\bullet}$} & \multicolumn{1}{|l}{} & \multicolumn{1}{|l|}{}\\\cline{2-8}% 0 & \multicolumn{1}{|l}{$_{\circ\longrightarrow}$} & \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$_{\bullet\longrightarrow}$} & \multicolumn{1}{|l}{$_{\bullet}^{\uparrow}$} & \multicolumn{1}{|l}{$\hspace {9pt}_{\bullet}^{\uparrow}$} & \multicolumn{1}{|l}{$_{\leftarrow\bullet}$} & \multicolumn{1}{|l}{$\hspace{9pt}$} & \multicolumn{1}{|l|}{\hspace*{20pt}% }\\\cline{2-8}% \end{tabular} $% \caption{A diffusion walk in the first octant from $(0,0)$ to $(3,3)$ with 20 steps and 4 contacts \label{fig:DiffusionExample}}% %TCIMACRO{\TeXButton{E}{\end{table}}}% %BeginExpansion \end{table}% %EndExpansion We prove in this paper that $D_{2k}\left( 0_{\rightarrow}n;c\right) =$ \begin{align} & \frac{2n+1}{2k+1}\binom{2k+2}{k-n}\binom{2k-c+1}{k-c+1}-\frac{2n+1}% {2k+1}\binom{2k+1}{k-n-1}\binom{2k-c+2}{k-c+1}\label{ClosedForm}\\ & -\frac{2n+1}{k+1}\binom{2k+2}{k-n}\binom{2k-c}{k-c}+\frac{4\left( n+1\right) }{2k+1}\binom{2k+1}{k-n-1}\binom{2k-c+1}{k-c}\nonumber\\ & +\frac{\left( 2+c+2n\right) }{\left( 2k+1\right) \left( 2k-c+2\right) }\binom{2k+1}{k}\binom{2k-c+2}{k-n-c}.\nonumber \end{align} Of course, there are various ways to shorten this expression; for example, $D_{2k}\left( 0_{\rightarrow}n;c\right) =$% \begin{align*} & \frac{\binom{2k+2}{k+n+2}\binom{2k}{k}}{\binom{2k+1}{c+1}2\left( k+1\right) ^{2}}\times\\ & \left( \left( n+1\right) \left( c-1\right) \binom{k}{c-1}+\frac{\left( 2k+1-c\right) \left( 2n+c+2\right) }{c+1}\left( \binom{k-n}{c}-\binom {k}{c}+n\binom{k}{c-1}\right) \right) . \end{align*} We leave it to the reader to show that the total number of walks in the first octant\emph{\ ending somewhere on the diagonal} after $2k$ steps and $c$ visits equals% \[ \sum_{n\geq0}D_{2k}\left( 0_{\rightarrow}n;c\right) =\frac{c\left( c-1\right) }{2k+1-c}\binom{2k+1-c}{k}\frac{1}{k+1}\binom{2k}{k}\text{ for }k\geq c-1. \]% %TCIMACRO{\TeXButton{B}{\begin{table}[h] \centering}}% %BeginExpansion \begin{table}[h] \centering %EndExpansion% \begin{tabular} [c]{l||llllll} & & & & \multicolumn{2}{l}{$k=$} & \\ $c\downarrow$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$\\\hline\hline $2$ & $2$ & $4$ & $20$ & $140$ & $1176$ & $11\,088$\\ $3$ & $0$ & $6$ & $30$ & $210$ & $1764$ & $16\,632$\\ $4$ & $0$ & $0$ & $20$ & $168$ & $1512$ & $14\,784$\\ $5$ & $0$ & $0$ & $0$ & $70$ & $840$ & $9240$\\ $6$ & $0$ & $0$ & $0$ & $0$ & $252$ & $3960$\\ $7$ & $0$ & $0$ & $0$ & $0$ & $0$ & $924$% \end{tabular} \caption{The number of octant walks contacting the diagonal $c$ times, and ending there after $2k$ steps \label{fig:TbleEndDiagonal}}% %TCIMACRO{\TeXButton{E}{\end{table}}}% %BeginExpansion \end{table}% %EndExpansion This follows from (\ref{ClosedForm}), but there may be better arguments, noticing the (generalized) Catalan numbers in the formula. Another challenge is an \emph{elementary} proof showing that the number of octant walks with $l $ steps and $c$ visits (ending anywhere) equals $f\left( l,c\right) =\frac{c}{\left\lfloor \left( l+1\right) /2\right\rfloor }\binom {l-c}{\left\lfloor l/2\right\rfloor +1-c}\binom{l}{\left\lfloor \left( l-1\right) /2\right\rfloor }$ for $1\leq c\leq\left\lfloor l/2\right\rfloor +1$.% %TCIMACRO{\TeXButton{B}{\begin{table}[h] \centering}}% %BeginExpansion \begin{table}[h] \centering %EndExpansion% \begin{tabular} [c]{l||llllllll} & & & & \multicolumn{2}{l}{$l=$} & & & \\ $c\downarrow$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\\hline\hline $1$ & $1$ & $1$ & $3$ & $6$ & $20$ & $50$ & $175$ & $490$\\ $2$ & $0$ & $2$ & $3$ & $8$ & $20$ & $60$ & $175$ & $560$\\ $3$ & $0$ & $0$ & $0$ & $6$ & $10$ & $45$ & $105$ & $420$\\ $4$ & $0$ & $0$ & $0$ & $0$ & $0$ & $20$ & $35$ & $224$\\ $5$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $70$% \end{tabular} \caption{The number of octant walks with $l$ steps, and $c$ contacts with the diagonal \label{fig:TbleEndDiagonal2}}% %TCIMACRO{\TeXButton{E}{\end{table}}}% %BeginExpansion \end{table}% %EndExpansion This paper is based on the work of Janse van Rensburg \cite[p. 115]% {JanseVanRensburg00},\cite[p. 470]{JanseVanRensburg99}, who derived a generating function for $D_{2k}\left( 0_{\rightarrow}n;c\right) $, and on some computer experiments by my student Tom Campbell that uncovered certain difficulties in applying the generating function, as pointed out in the next section. Because Janse van Rensburg derived the generating function from a more general setting in many complex steps, we added a straightforward verification to that section. In Section \ref{SectSumming} we extract the coefficients $D_{2k}\left( 0_{\rightarrow}n;c\right) $ from the generating function. This involves finding a closed expression for a double sum. We have been assured that computer algebra can do such a summation; however, it is also easily done by classical arguments, which we sketch in that section. \section{The Contact Generating Function\label{SecGeneratingFunction}} Janse van Rensburg \cite{JanseVanRensburg00},\cite{JanseVanRensburg99} investigated the more general problem considering walks that end somewhere inside the octant, instead of just on the diagonal. Let $D_{k}\left( 0\rightarrow\left( j,l\right) ;c\right) $ be the number of diffusion walks from $\left( 0,0\right) $ to $\left( j,l\right) $ taking $k$ steps in the first octant contacting the diagonal $y=x$ exactly $c$ times, thus $D_{2k}\left( 0_{\rightarrow}n;c\right) =D_{2k}\left( 0\rightarrow\left( n,n\right) ;c\right) $, and let \[ r_{k}\left( j,l;0,0\right) =\sum_{c\geq0}D_{k}\left( 0\rightarrow\left( j,l\right) ;c\right) z^{c}. \] In Table \ref{fig:GeneratingFunctions} the first few generating functions $r_{k}\left( j,l;0,0\right) $ are shown, where each cell $\left( j,l\right) $ (in double frames) is subdivided into subcells for $k=1,2,3,4$.% %TCIMACRO{\TeXButton{B}{\begin{table}[h] \centering}}% %BeginExpansion \begin{table}[h] \centering %EndExpansion% %TCIMACRO{\TeXButton{tabcolsep}{\tabcolsep=3pt}}% %BeginExpansion \tabcolsep=3pt% %EndExpansion% \begin{tabular} [c]{l}% $l=2$\\ $l=1$\\ $l=0$\\ \\ \end{tabular}% \begin{tabular} [c]{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|}\hline\hline \multicolumn{1}{||l|}{} & & & & \multicolumn{1}{||l|}{} & & & & \multicolumn{1}{||l|}{} & & & \multicolumn{1}{|l||}{$z^{2}+z^{3}$} & & & & \multicolumn{1}{|l||}{}\\\hline\hline \multicolumn{1}{||l|}{} & & & & \multicolumn{1}{||l|}{} & $z^{2}$ & & $2z^{2}+3z^{3}$ & \multicolumn{1}{||l|}{} & & $z+z^{2}$ & \multicolumn{1}{|l||}{} & & & & \multicolumn{1}{|l||}{$2z+z^{2}$% }\\\hline\hline \multicolumn{1}{||l|}{} & $z^{2}$ & & $z^{2}+2z^{3}$ & \multicolumn{1}{||l|}{$z$} & & $z+2z^{2}$ & & \multicolumn{1}{||l|}{} & $z$ & & \multicolumn{1}{|l||}{$3z+3z^{2}$} & & & $z$ & \multicolumn{1}{|l||}{}% \\\hline\hline \multicolumn{1}{|c|}{$k=1$} & \multicolumn{1}{|c|}{$2$} & \multicolumn{1}{|c|}{$3$} & \multicolumn{1}{|c|}{$4$} & \multicolumn{1}{|c|}{$1$} & \multicolumn{1}{|c|}{$2$} & \multicolumn{1}{|c|}{$3$} & \multicolumn{1}{|c|}{$4$} & \multicolumn{1}{|c|}{$1$} & \multicolumn{1}{|c|}{$2$} & \multicolumn{1}{|c|}{$3$} & \multicolumn{1}{|c|}{$4$} & $1$ & $2$ & $3$ & $4$\\\hline \multicolumn{4}{|c|}{$j=0$} & \multicolumn{4}{c|}{$j=1$} & \multicolumn{4}{c|}{$j=2$} & \multicolumn{4}{|c|}{$j=3$}\\\hline \end{tabular} \caption{The generating functions $r_{k}\left( j,l\right) $ \label{fig:GeneratingFunctions}}% %TCIMACRO{\TeXButton{E}{\end{table}}}% %BeginExpansion \end{table}% %EndExpansion Janse van Rensburg constructed this generating function as a special case of walks starting somewhere in the octant, not necessarily at the origin. However, the general problem seems to be difficult to bring to an explicit form, and we will write now $r_{k}\left( j,l\right) $ instead of $r_{k}\left( j,l;0,0\right) $. Omitting many details he finally derives for $k\geq l+j>0$,% \begin{align} r_{k}\left( j,l\right) & =z\sum_{m_{1}=0}^{\infty}\sum_{m_{2}=0}^{\infty }\left( z-1\right) ^{m_{1}+m_{2}}U_{k}\left( j+m_{1}+m_{2},l+m_{1}% -m_{2}\right) \label{GenFunc}\\ & =z\sum_{i=0}^{\infty}\sum_{q=0}^{i}\left( z-1\right) ^{i}U_{k}\left( j+i,l+i-2q\right) ,\nonumber \end{align} where $U_{k}\left( n,m\right) =$% \begin{equation} \allowbreak\frac{\left( m+1\right) \left( 2+n\right) \left( m+3+n\right) \left( n+1-m\right) }{\left( k+1\right) \left( k+2\right) \left( k+3\right) ^{2}}\binom{k+3}{\frac{1}{2}\left( k+n-m\right) +2}% \allowbreak\binom{k+3}{\frac{1}{2}\left( k+n+m\right) +3}.\label{U(k,n,m)}% \end{equation} Only for $0\leq m\leq n$ we can say that $U_{k}\left( n,m\right) $ equals the number \[ D_{k}\left( 0\rightarrow\left( n,m\right) \right) :=\sum_{c\geq0}% D_{k}\left( 0\rightarrow\left( n,m\right) ;c\right) \] of all octant walks from $\left( 0,0\right) $ to $\left( n,m\right) $ in $k$ steps. For an elementary derivation of this result and references see \cite{Octant}. In the generating function (\ref{GenFunc}) we mean the \emph{formula} for $U_{k}\left( j+m_{1}+m_{2},l+m_{1}-m_{2}\right) $, not the number of walks, i.e., $U_{k}\left( j+m_{1}+m_{2},l+m_{1}-m_{2}\right) $ is not vanishing everywhere outside the first octant (unfortunately, this distinction was not made by Janse van Rensburg, aggravating the error in the formula \cite[(4.186)]{JanseVanRensburg00},\cite[(3.23)]{JanseVanRensburg99} for $U_{k}\left( n,m\right) $). Indeed, for the proof of (\ref{GenFunc}) it is essential that \begin{equation} U_{k}\left( n,n-2q\right) =-U_{k}\left( n,2q-n-2\right) ,\label{OddU}% \end{equation} a symmetry not shared by the counts $D_{k}\left( 0\rightarrow\left( n,m\right) \right) $. In the following proposition we verify (\ref{GenFunc}) in an elementary way. \begin{proposition} \cite{JanseVanRensburg99} If the binomial coefficient $\binom{u}{v}$ is defined the usual way, $\binom{u}{v}=0$ if $v>u$ or $v<0$ or $v$ not an integer, and $U_{k}\left( n,m\right) $ is given as in (\ref{U(k,n,m)}), then \[ \sum_{c\geq0}D_{k}\left( 0\rightarrow\left( j,l\right) ;c\right) z^{c}=z\sum_{i=0}^{k-j}\left( z-1\right) ^{i}\sum_{q=0}^{i}U_{k}\left( j+i,l+i-2q\right) \] for $k>0$. We define $D_{0}\left( 0\rightarrow\left( j,l\right) ;c\right) =1 $ if $j=l=c=0$, and $0$ otherwise. \end{proposition} \begin{proof} Let $\sigma_{k}\left( j,l\right) :=z\sum_{i=0}^{k-j}\left( z-1\right) ^{i}\sum_{q=0}^{i}U_{k}\left( j+i,l+i-2q\right) $. We show that $\sigma _{k}\left( j,l\right) $ solves the same recursion as $r_{k}\left( j,l\right) $,% \begin{equation} r_{k}\left( j,l\right) =r_{k-1}\left( j+1,l\right) +r_{k-1}\left( j-1,l\right) +r_{k-1}\left( j,l+1\right) +r_{k-1}\left( j,l-1\right) \label{Recursion_s_n}% \end{equation} for all $1\leq l\leq j\,$and $k>0$, and has the same initial values% \begin{align} r_{k}\left( j,j\right) & =z\left( r_{k-1}\left( j,j-1\right) +r_{k-1}\left( j+1,j\right) \right) \text{ for all }j\geq0,\text{ }k>0\label{IniValDiagonal}\\ r_{0}\left( j,l\right) & =\delta_{0,j}\delta_{0,l} \label{IniValOrigin}% \end{align} and% \begin{equation} r_{k}\left( j,0\right) =r_{k-1}\left( j+1,0\right) +r_{k-1}\left( j-1,0\right) +r_{k-1}\left( j,1\right) \text{ for all }l>0,\text{ }k>0. \label{IniValAxis}% \end{equation} The recursion (\ref{Recursion_s_n}) and condition (\ref{IniValOrigin}) hold for $U_{k}\left( j,l\right) $, and therefore for $\sigma_{k}\left( j,l\right) $. Condition (\ref{IniValAxis}) follows if we can show that $\sigma_{k}\left( j,-1\right) =0$. Thus we verify% \begin{align*} \sigma_{k}\left( j,-1\right) & =z\sum_{i\geq0}\left( z-1\right) ^{i}% \sum_{q=0}^{i}U_{k}\left( i+j,i-2q-1\right) \\ & =z\sum_{i\geq0}\left( z-1\right) ^{i}\left( \sum_{q=0}^{\left\lfloor \left( i-1\right) /2\right\rfloor }U_{k}\left( i+j,i-2q-1\right) +\sum_{q=\left\lfloor \left( i+1\right) /2\right\rfloor }^{i}U_{k}\left( i+j,i-2q-1\right) \right) \\ & =z\sum_{i\geq0}\left( z-1\right) ^{i}\left( \sum_{q=0}^{\left\lfloor \left( i-1\right) /2\right\rfloor }U_{k}\left( i+j,i-2q-1\right) +\sum_{q=0}^{\left\lceil \left( i-1\right) /2\right\rceil }U_{k}\left( i+j,2q-i+1-2\right) \right) \\ & =z\sum_{i\geq0}\left( z-1\right) ^{i}\left( \sum_{q=0}^{\left\lfloor \left( i-1\right) /2\right\rfloor }U_{k}\left( i+j,i-2q-1\right) -\sum_{q=0}^{\left\lceil \left( i-1\right) /2\right\rceil }U_{k}\left( i+j,i-1-2q\right) \right) \end{align*} using equation (\ref{OddU}). If $i$ is odd the two inner sums cancel each other. For even $i$ the difference equals $-U_{k}\left( i+j,-1\right) $, which is also $0$. Finally we verify (\ref{IniValDiagonal}), noting that% \begin{align*} & z\left( \sigma_{k-1}\left( j,j-1\right) +\sigma_{k-1}\left( j+1,j\right) \right) \\ & =\left( z-1\right) \left( \sigma_{k-1}\left( j,j-1\right) +\sigma_{k-1}\left( j+1,j\right) \right) +\sigma_{k-1}\left( j,j-1\right) +\sigma_{k-1}\left( j+1,j\right) \end{align*} A closer look at the first two term shows that% \begin{align*} & \left( z-1\right) \left( \sigma_{k-1}\left( j,j-1\right) +\sigma _{k-1}\left( j+1,j\right) \right) \\ & =z\sum_{i\geq0}\left( z-1\right) ^{i+1}\sum_{q=0}^{i}\left( U_{k-1}\left( j+i,j-1+i-2q\right) +U_{k-1}\left( j+1+i,j+i-2q\right) \right) \\ & =z\sum_{i\geq1}\left( z-1\right) ^{i}\sum_{q=0}^{i-1}\left( U_{k-1}\left( j-1+i,j-2+i-2q\right) +U_{k-1}\left( j+i,j-1+i-2q\right) \right) \\ & =z\sum_{i\geq1}\left( z-1\right) ^{i}\sum_{q=0}^{i}\left( U_{k-1}\left( j-1+i,j+i-2q\right) +U_{k-1}\left( j+i,j+1+i-2q\right) \right) \end{align*} using $U_{k-1}\left( j-1+i,j+i\right) =0$ and $U_{k-1}\left( j+i,j+1+i\right) =0$ in the last step. Hence \newline$z\left( \sigma _{k-1}\left( j,j-1\right) +\sigma_{k-1}\left( j+1,j\right) \right) =\sigma_{k-1}\left( j-1,j\right) +\sigma_{k-1}\left( j,j+1\right) +\sigma_{k-1}\left( j,j-1\right) +\sigma_{k-1}\left( j+1,j\right) $\newline$=\sigma_{k}\left( j,j\right) $, as desired. \end{proof} \section{Summing the Double Sum\label{SectSumming}} Extracting the coefficient of $z^{c}$ from the contact generating function \[ \sum_{c\geq0}D_{k}\left( 0\rightarrow\left( j,l\right) ;c\right) z^{c}=z\sum_{i=0}^{k-j}\left( z-1\right) ^{i}\sum_{q=0}^{i}U_{k}\left( j+i,l+i-2q\right) \] gives the double sum $D_{2k}\left( 0_{\rightarrow}n;c\right) =$% \begin{align} & \sum_{l=c-1}^{k}\binom{l}{c-1}\left( -1\right) ^{c-1-l}\sum_{q=0}^{l}% \frac{\left( n+l-2q+1\right) \left( 2+l+n\right) \left( 2l+2n+3-2q\right) \left( 1+2q\right) }{\left( 2k+3\right) ^{2}\left( 2k+2\right) \left( 2k+1\right) }\label{RensburgSum}\\ & \times\binom{2k+3}{k+q+2}\binom{2k+3}{k-n-l+q}.\nonumber \end{align} Finding a closed form for this double sum is completely elementary under the right approach; first note that (\ref{RensburgSum}) can be written as% \begin{align} D_{2k}\left( 0_{\rightarrow}n;c\right) & =\sum_{l=c-1}^{k}\binom{l}% {c-1}\left( -1\right) ^{c-1-l}\frac{2+l+n}{\left( 2k+2\right) \left( 2k+1\right) }\label{RensburgSum2}\\ & \times\left( s\left( k-n,k,n+l\right) -s\left( k-n-l-1,k,n+l\right) \right) ,\nonumber \end{align} where% \begin{align*} s\left( N,k,m\right) & =\sum_{q=0}^{N}\frac{\left( 2k+3-2q\right) }{2k+3}\binom{2k+3}{q}\frac{\left( 2k-m+1-2q\right) \left( 2m-2k+1+2q\right) }{2k+3}\\ & \times\binom{2k+3}{2k-m+1-q}. \end{align*} It easily follows by induction over $N$ that% \begin{align*} s\left( N,k,m\right) & =\frac{\left( 2k-2N+2\right) \left( m+N+2\right) -\left( 2k-2N+3\right) \left( k+1\right) }{k+1}\\ & \times\binom{2k+2}{N}\binom{2k+2}{2k-m-N}. \end{align*} Thus (\ref{RensburgSum2}) simplifies to a single summation. Repeated application of Vandermonde convolution leads to the closed form (\ref{ClosedForm}) for $D_{2k}\left( 0_{\rightarrow}n;c\right) $. \begin{thebibliography}{9} % \bibitem {JanseVanRensburg00}E. J. Janse van Rensburg, \textit{The Statistical Mechanics of Interacting Walks, Polygons, Animals and Vesicles}, Oxford University Press, Oxford, UK, 2000. \bibitem {JanseVanRensburg99}E. J. Janse van Rensburg, Adsorbing staircase walks and staircase polygons, \textit{Ann. Combinat.} \textbf{3 }(1999), 451--473. \bibitem {Octant}H. Niederhausen, Random Walks in Octants, and Related Structures. To appear in \textit{J. Statist. Plann. Inference} (2005), doi:10.1016/j.jspi.2005.02.013. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A05; Secondary 05A15. \noindent \emph{Keywords:} random walks, diffusion, contacts, adsorption. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A005558}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 29 2004; revised version received September 1 2005. Published in {\it Journal of Integer Sequences}, September 1 2005. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}