<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,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}
&amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6\\\cline{7-8}%
5 &amp;  &amp;  &amp;  &amp;  &amp;  &amp; \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}} &amp;
\multicolumn{1}{|l|}{}\\\cline{6-8}%
4 &amp;  &amp;  &amp;  &amp;  &amp; \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$\hspace
{9pt}_{\downarrow}^{\bullet}$} &amp; \multicolumn{1}{|l}{$^{\leftarrow\bullet}$} &amp;
\multicolumn{1}{|l|}{$^{\leftarrow\bullet}$}\\\cline{5-8}%
3 &amp;  &amp;  &amp;  &amp; \multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$_{\hspace{9pt}\circ}
$} &amp; \multicolumn{1}{|l}{$\hspace{9pt}_{\downarrow}^{\bullet}$} &amp;
\multicolumn{1}{|l}{} &amp; \multicolumn{1}{|l|}{$\hspace{9pt}_{\bullet}%
^{\uparrow}$}\\\cline{4-8}%
2 &amp;  &amp;  &amp; \multicolumn{1}{|l}{$_{\bullet\longrightarrow}$\rule[-7pt]%
{0pt}{21pt}} &amp; \multicolumn{1}{|l}{$_{\bullet\longrightarrow}^{\hspace
{9pt}\uparrow}$} &amp; \multicolumn{1}{|l}{$_{\bullet\longrightarrow}%
^{\hspace{9pt}\downarrow}$} &amp; \multicolumn{1}{|l}{$_{\bullet\longrightarrow}
$} &amp; \multicolumn{1}{|l|}{$\hspace{9pt}_{\bullet}^{\uparrow}$}\\\cline{3-8}%
1 &amp;  &amp; \multicolumn{1}{|l}{} &amp; \multicolumn{1}{|l}{$_{\bullet}^{\uparrow}$} &amp;
\multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$\hspace{9pt}_{\bullet}^{\uparrow}$}
&amp; \multicolumn{1}{|l}{$\hspace{9pt}_{\downarrow}^{\bullet}$} &amp;
\multicolumn{1}{|l}{} &amp; \multicolumn{1}{|l|}{}\\\cline{2-8}%
0 &amp; \multicolumn{1}{|l}{$_{\circ\longrightarrow}$} &amp;
\multicolumn{1}{|l}{\rule[-7pt]{0pt}{21pt}$_{\bullet\longrightarrow}$} &amp;
\multicolumn{1}{|l}{$_{\bullet}^{\uparrow}$} &amp; \multicolumn{1}{|l}{$\hspace
{9pt}_{\bullet}^{\uparrow}$} &amp; \multicolumn{1}{|l}{$_{\leftarrow\bullet}$} &amp;
\multicolumn{1}{|l}{$\hspace{9pt}$} &amp; \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}
&amp;  \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}\\
&amp;  -\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\\
&amp;  +\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*}
&amp; \frac{\binom{2k+2}{k+n+2}\binom{2k}{k}}{\binom{2k+1}{c+1}2\left(
k+1\right)  ^{2}}\times\\
&amp; \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}
&amp;  &amp;  &amp;  &amp; \multicolumn{2}{l}{$k=$} &amp; \\
$c\downarrow$ &amp; $1$ &amp; $2$ &amp; $3$ &amp; $4$ &amp; $5$ &amp; $6$\\\hline\hline
$2$ &amp; $2$ &amp; $4$ &amp; $20$ &amp; $140$ &amp; $1176$ &amp; $11\,088$\\
$3$ &amp; $0$ &amp; $6$ &amp; $30$ &amp; $210$ &amp; $1764$ &amp; $16\,632$\\
$4$ &amp; $0$ &amp; $0$ &amp; $20$ &amp; $168$ &amp; $1512$ &amp; $14\,784$\\
$5$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $70$ &amp; $840$ &amp; $9240$\\
$6$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $252$ &amp; $3960$\\
$7$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $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}
&amp;  &amp;  &amp;  &amp; \multicolumn{2}{l}{$l=$} &amp;  &amp;  &amp; \\
$c\downarrow$ &amp; $1$ &amp; $2$ &amp; $3$ &amp; $4$ &amp; $5$ &amp; $6$ &amp; $7$ &amp; $8$\\\hline\hline
$1$ &amp; $1$ &amp; $1$ &amp; $3$ &amp; $6$ &amp; $20$ &amp; $50$ &amp; $175$ &amp; $490$\\
$2$ &amp; $0$ &amp; $2$ &amp; $3$ &amp; $8$ &amp; $20$ &amp; $60$ &amp; $175$ &amp; $560$\\
$3$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $6$ &amp; $10$ &amp; $45$ &amp; $105$ &amp; $420$\\
$4$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $20$ &amp; $35$ &amp; $224$\\
$5$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $0$ &amp; $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|}{} &amp;  &amp;  &amp;  &amp; \multicolumn{1}{||l|}{} &amp;  &amp;  &amp;  &amp;
\multicolumn{1}{||l|}{} &amp;  &amp;  &amp; \multicolumn{1}{|l||}{$z^{2}+z^{3}$} &amp;  &amp;  &amp;
&amp; \multicolumn{1}{|l||}{}\\\hline\hline
\multicolumn{1}{||l|}{} &amp;  &amp;  &amp;  &amp; \multicolumn{1}{||l|}{} &amp; $z^{2}$ &amp;  &amp;
$2z^{2}+3z^{3}$ &amp; \multicolumn{1}{||l|}{} &amp;  &amp; $z+z^{2}$ &amp;
\multicolumn{1}{|l||}{} &amp;  &amp;  &amp;  &amp; \multicolumn{1}{|l||}{$2z+z^{2}$%
}\\\hline\hline
\multicolumn{1}{||l|}{} &amp; $z^{2}$ &amp;  &amp; $z^{2}+2z^{3}$ &amp;
\multicolumn{1}{||l|}{$z$} &amp;  &amp; $z+2z^{2}$ &amp;  &amp; \multicolumn{1}{||l|}{} &amp; $z$
&amp;  &amp; \multicolumn{1}{|l||}{$3z+3z^{2}$} &amp;  &amp;  &amp; $z$ &amp; \multicolumn{1}{|l||}{}%
\\\hline\hline
\multicolumn{1}{|c|}{$k=1$} &amp; \multicolumn{1}{|c|}{$2$} &amp;
\multicolumn{1}{|c|}{$3$} &amp; \multicolumn{1}{|c|}{$4$} &amp;
\multicolumn{1}{|c|}{$1$} &amp; \multicolumn{1}{|c|}{$2$} &amp;
\multicolumn{1}{|c|}{$3$} &amp; \multicolumn{1}{|c|}{$4$} &amp;
\multicolumn{1}{|c|}{$1$} &amp; \multicolumn{1}{|c|}{$2$} &amp;
\multicolumn{1}{|c|}{$3$} &amp; \multicolumn{1}{|c|}{$4$} &amp; $1$ &amp; $2$ &amp; $3$ &amp;
$4$\\\hline
\multicolumn{4}{|c|}{$j=0$} &amp; \multicolumn{4}{c|}{$j=1$} &amp;
\multicolumn{4}{c|}{$j=2$} &amp; \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&gt;0$,%
\begin{align}
r_{k}\left(  j,l\right)   &amp;  =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}\\
&amp;  =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&gt;u$ or $v&lt;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&gt;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&gt;0$, and has the same initial values%
\begin{align}
r_{k}\left(  j,j\right)   &amp;  =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&gt;0\label{IniValDiagonal}\\
r_{0}\left(  j,l\right)   &amp;  =\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&gt;0,\text{ }k&gt;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)   &amp;  =z\sum_{i\geq0}\left(  z-1\right)  ^{i}%
\sum_{q=0}^{i}U_{k}\left(  i+j,i-2q-1\right) \\
&amp;  =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) \\
&amp;  =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) \\
&amp;  =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*}
&amp;  z\left(  \sigma_{k-1}\left(  j,j-1\right)  +\sigma_{k-1}\left(
j+1,j\right)  \right)  \\
&amp;  =\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*}
&amp;  \left(  z-1\right)  \left(  \sigma_{k-1}\left(  j,j-1\right)  +\sigma
_{k-1}\left(  j+1,j\right)  \right)  \\
&amp;  =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)  \\
&amp;  =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)  \\
&amp;  =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}
&amp; \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}\\
&amp; \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)    &amp; =\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}\\
&amp; \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)    &amp; =\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}\\
&amp; \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)    &amp; =\frac{\left(  2k-2N+2\right)  \left(
m+N+2\right)  -\left(  2k-2N+3\right)  \left(  k+1\right)  }{k+1}\\
&amp; \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}

                                                                                

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