A Note on the Enumeration of Diffusion Walks in the First Octant by Their Number

of Contacts with the Diagonal

Heinrich Niederhausen Department of Mathematical Sciences Florida Atlantic University Boca Raton, FL 33431 USA

                   Niederhausen@math.fau.edu

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 (n, n) on the diagonal in k steps inside the first octant, touching the diagonal exactly c times.

1 Notation and Results

A diffusion walk is a random walk in the square lattice ℤ^{2}, equally likely taking one of the four unit steps North = (0, 1), South = (0, −1), East = (1, 0), and W est = (−1, 0). The walk stays in the first octant, also called principal wedge, if it only visits lattice points (n, m) satisfying 0 ≤ m ≤ n. We will call such restricted diffusion walks octant walks in this paper. We denote by D_{2k} (0_{→}n; c) the number of octant walks from (0, 0) to (n, n) 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 visits, and points of adsorption. Figure 1 shows a path from (0, 0) to (3, 3) making four visits.

0  1  2  3  4  5  6

5

4  • ↓  ←•  ←•
3  ∘  • ↓  ↑ •
2  •⟶ {↑ \atop •⟶} {↓ \atop •⟶} •⟶  ↑ •
1  ↑ •  ↑ •  • ↓
0 ∘⟶ •⟶ ↑ •  ↑ •  ←•

Table 1: A diffusion walk in the first octant from (0, 0) to (3, 3) with 20 steps and 4 contacts

We prove in this paper that D_{2k} (0_{→}n; c) =

\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}  (1)

− \frac{2n + 1}{k + 1}\binom{2k + 2}{k − n}\binom{2k − c}{k − c} + \frac{4 (n + 1)}{2k + 1}\binom{2k + 1}{k − n − 1}\binom{2k − c + 1}{k − c}

+ \frac{(2 + c + 2n)}{(2k + 1) (2k − c + 2)}\binom{2k + 1}{k}\binom{2k − c + 2}{k − n − c}.

Of course, there are various ways to shorten this expression; for example, D_{2k} (0_{→}n; c) =

\frac{\binom{2k+2}{k+n+2}\binom{2k}{k}}{\binom{2k+1}{c+1}2 (k + 1)^{2}} ×

((n + 1) (c − 1) \binom{k}{c − 1} + \frac{(2k + 1 − c) (2n + c + 2)}{c + 1} (\binom{k − n}{c} − \binom{k}{c} + n\binom{k}{c − 1})) .

We leave it to the reader to show that the total number of walks in the first octant ending somewhere on the diagonal after 2k steps and c visits equals

∑_{n≥0} D_{2k} (0_{→}n; c) = \frac{c (c − 1)}{2k + 1 − c}\binom{2k + 1 − c}{k}\frac{1}{k + 1}\binom{2k}{k} for k ≥ c − 1.

This follows from (1), but there may be better arguments, noticing the (generalized) Catalan numbers in the formula. Another challenge is an elementary proof showing that the number of octant walks with l steps and c visits (ending anywhere) equals f (l, c) = \frac{c}{⌊(l+1)/2⌋} \binom{l−c}{⌊l/2⌋+1−c}\binom{l}{⌊(l−1)/2⌋} for 1 ≤ c ≤ ⌊l/2⌋ + 1.

This paper is based on the work of Janse van Rensburg [1, p. 115],[2, p. 470], who derived a generating function for D_{2k} (0_{→}n; c), 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

k =
c ↓ 1 2 3 4 5  6
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

Table 2: The number of octant walks contacting the diagonal c times, and ending there after 2k steps

l =
c ↓ 1 2 3 4 5 6 7 8
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

Table 3: The number of octant walks with l steps, and c contacts with the diagonal

to that section. In Section 3 we extract the coefficients D_{2k} (0_{→}n; c) 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.

2 The Contact Generating Function

Janse van Rensburg [1],[2] investigated the more general problem considering walks that end somewhere inside the octant, instead of just on the diagonal. Let D_{k} (0 → (j, l) ; c) be the number of diffusion walks from (0, 0) to (j, l) taking k steps in the first octant contacting the diagonal y = x exactly c times, thus D_{2k} (0_{→}n; c) = D_{2k} (0 → (n, n) ; c), and let

r_{k} (j, l; 0, 0) = ∑_{c≥0} D_{k} (0 → (j, l) ; c) z^{c}.

In Table 4 the first few generating functions r_{k} (j, l; 0, 0) are shown, where each cell (j, l) (in double frames) is subdivided into subcells for k = 1, 2, 3, 4.

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} (j, l) instead of r_{k} (j, l; 0, 0).

\begin{matrix}l = 2 \\ l = 1 \\ l = 0 \end{matrix} \begin{aligned}& & & & & & & z^{2} + z^{3} \\ & & & z^{2} & 2z^{2} + 3z^{3} & & & z + z^{2} & & & 2z + z^{2} \\ z^{2} & z^{2} + 2z^{3} & z & z + 2z^{2} & z & 3z + 3z^{2} & z \\ k = 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 & 1 & 2 & 3 & 4 \\ & j = 0 & & & j = 1 & & & j = 2 & & & j = 3 \end{aligned}

Table 4: The generating functions r_{k} (j, l)

Omitting many details he finally derives for k ≥ l + j > 0,

r_{k} (j, l) = z ∑_{m_{1}=0}^{∞} ∑_{m_{2}=0}^{∞} (z − 1)^{m_{1}+m_{2}} U_{k} (j + m_{1} + m_{2}, l + m_{1} − m_{2})  (2)

= z ∑_{i=0}^{∞} ∑_{q=0}^{i} (z − 1)^{i} U_{k} (j + i, l + i − 2q) ,

where U_{k} (n, m) =

\begin{matrix}(m + 1) & (2 + n) & (m + 3 + n) & (n + 1 − m) \\ (k + 1) & (k + 2) & (k + 3) & 2 \end{matrix} \binom{k + 3}{\frac{1}{2} (k + n − m) + 2}\binom{k + 3}{\frac{1}{2} (k + n + m) + 3}. (3)

Only for 0 ≤ m ≤ n we can say that U_{k} (n, m) equals the number

D_{k} (0 → (n, m)) := ∑_{c≥0} D_{k} (0 → (n, m) ; c)

of all octant walks from (0, 0) to (n, m) in k steps. For an elementary derivation of this result and references see [3]. In the generating function (2) we mean the formula for U_{k} (j + m_{1} + m_{2}, l + m_{1} − m_{2}), not the number of walks, i.e., U_{k} (j + m_{1} + m_{2}, l + m_{1} − m_{2}) is not vanishing everywhere outside the first octant (unfortunately, this distinction was not made by Janse van Rensburg, aggravating the error in the formula [1, (4.186)],[2, (3.23)] for U_{k} (n, m)). Indeed, for the proof of (2) it is essential that

U_{k} (n, n − 2q) = −U_{k} (n, 2q − n − 2) ,  (4)

a symmetry not shared by the counts D_{k} (0 → (n, m)).

In the following proposition we verify (2) in an elementary way.

Proposition 2.1. [2] 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} (n, m) is given as in (3), then

∑_{c≥0} D_{k} (0 → (j, l) ; c) z^{c} = z ∑_{i=0}^{k−j} (z − 1)^{i} ∑_{q=0}^{i} U_{k} (j + i, l + i − 2q)

for k > 0. We define D_{0} (0 → (j, l) ; c) = 1 if j = l = c = 0, and 0 otherwise.

Proof. Let σ_{k} (j, l) := z ∑_{i=0}^{k−j} (z − 1)^{i} ∑_{q=0}^{i} U_{k} (j + i, l + i − 2q). We show that σ_{k} (j, l) solves the same recursion as r_{k} (j, l),

r_{k} (j, l) = r_{k−1} (j + 1, l) + r_{k−1} (j − 1, l) + r_{k−1} (j, l + 1) + r_{k−1} (j, l − 1)  (5)

for all 1 ≤ l ≤ j and k > 0, and has the same initial values

r_{k} (j, j) = z (r_{k−1} (j, j − 1) + r_{k−1} (j + 1, j)) for all j ≥ 0, k > 0  (6)
r_{0} (j, l) = δ_{0,j}δ_{0,l}  (7)

and

r_{k} (j, 0) = r_{k−1} (j + 1, 0) + r_{k−1} (j − 1, 0) + r_{k−1} (j, 1) for all l > 0, k > 0.  (8)

The recursion (5) and condition (7) hold for U_{k} (j, l), and therefore for σ_{k} (j, l). Condition (8) follows if we can show that σ_{k} (j, −1) = 0. Thus we verify

σ_{k} (j, −1) = z ∑_{i≥0} (z − 1)^{i} ∑_{q=0}^{i} U_{k} (i + j, i − 2q − 1)

= z ∑_{i≥0} (z − 1)^{i} ( ∑_{q=0}^{⌊(i−1)/2⌋} U_{k} (i + j, i − 2q − 1) + ∑_{q=⌊(i+1)/2⌋}^{i} U_{k} (i + j, i − 2q − 1))

= z ∑_{i≥0} (z − 1)^{i} ( ∑_{q=0}^{⌊(i−1)/2⌋} U_{k} (i + j, i − 2q − 1) + ∑_{q=0}^{⌈(i−1)/2⌉} U_{k} (i + j, 2q − i + 1 − 2))

= z ∑_{i≥0} (z − 1)^{i} ( ∑_{q=0}^{⌊(i−1)/2⌋} U_{k} (i + j, i − 2q − 1) − ∑_{q=0}^{⌈(i−1)/2⌉} U_{k} (i + j, i − 1 − 2q))

using equation (4). If i is odd the two inner sums cancel each other. For even i the difference equals −U_{k} (i + j, −1), which is also 0.

Finally we verify (6), noting that

z (σ_{k−1} (j, j − 1) + σ_{k−1} (j + 1, j))
= (z − 1) (σ_{k−1} (j, j − 1) + σ_{k−1} (j + 1, j)) + σ_{k−1} (j, j − 1) + σ_{k−1} (j + 1, j)

A closer look at the first two term shows that

(z − 1) (σ_{k−1} (j, j − 1) + σ_{k−1} (j + 1, j))

= z ∑_{i≥0} (z − 1)^{i+1} ∑_{q=0}^{i} (U_{k−1} (j + i, j − 1 + i − 2q) + U_{k−1} (j + 1 + i, j + i − 2q))

= z ∑_{i≥1} (z − 1)^{i} ∑_{q=0}^{i−1} (U_{k−1} (j − 1 + i, j − 2 + i − 2q) + U_{k−1} (j + i, j − 1 + i − 2q))

= z ∑_{i≥1} (z − 1)^{i} ∑_{q=0}^{i} (U_{k−1} (j − 1 + i, j + i − 2q) + U_{k−1} (j + i, j + 1 + i − 2q))

using U_{k−1} (j − 1 + i, j + i) = 0 and U_{k−1} (j + i, j + 1 + i) = 0 in the last step. Hence z (σ_{k−1} (j, j − 1) + σ_{k−1} (j + 1, j)) = σ_{k−1} (j − 1, j)+σ_{k−1} (j, j + 1)+σ_{k−1} (j, j − 1)+σ_{k−1} (j + 1, j) = σ_{k} (j, j), as desired.

3 Summing the Double Sum

Extracting the coefficient of z^{c} from the contact generating function

∑_{c≥0} D_{k} (0 → (j, l) ; c) z^{c} = z ∑_{i=0}^{k−j} (z − 1)^{i} ∑_{q=0}^{i} U_{k} (j + i, l + i − 2q)

gives the double sum D_{2k} (0_{→}n; c) =

∑_{l=c−1}^{k} \binom{l}{c − 1} (−1)^{c−1−l} ∑_{q=0}^{l} \begin{matrix}(n + l − 2q + 1) & (2 + l + n) & (2l + 2n + 3 − 2q) & (1 + 2q) \\ (2k + 3) & 2 & (2k + 2) & (2k + 1) \end{matrix} (9)

× \binom{2k + 3}{k + q + 2}\binom{2k + 3}{k − n − l + q}.

Finding a closed form for this double sum is completely elementary under the right approach; first note that (9) can be written as

D_{2k} (0_{→}n; c) = ∑_{l=c−1}^{k} \binom{l}{c − 1} (−1)^{c−1−l} \frac{2 + l + n}{(2k + 2) (2k + 1)}  (10)
× (s (k − n, k, n + l) − s (k − n − l − 1, k, n + l)) ,

where

s (N, k, m) = ∑_{q=0}^{N} \frac{(2k + 3 − 2q)}{2k + 3}\binom{2k + 3}{q}\frac{(2k − m + 1 − 2q) (2m − 2k + 1 + 2q)}{2k + 3}

× \binom{2k + 3}{2k − m + 1 − q}.

It easily follows by induction over N that

s (N, k, m) = \frac{(2k − 2N + 2) (m + N + 2) − (2k − 2N + 3) (k + 1)}{k + 1}

× \binom{2k + 2}{N}\binom{2k + 2}{2k − m − N}.

Thus (10) simplifies to a single summation. Repeated application of Vandermonde convolution leads to the closed form (1) for D_{2k} (0_{→}n; c).

References

[1] E. J. Janse van Rensburg, The Statistical Mechanics of Interacting Walks, Polygons, Animals and Vesicles, Oxford University Press, Oxford, UK, 2000.

[2] E. J. Janse van Rensburg, Adsorbing staircase walks and staircase polygons, Ann. Combinat. 3 (1999), 451–473.

[3] H. Niederhausen, Random Walks in Octants, and Related Structures. To appear in J. Statist. Plann. Inference (2005), doi:10.1016/j.jspi.2005.02.013.

2000 Mathematics Subject Classification: Primary 05A05; Secondary 05A15. Keywords: random walks, diffusion, contacts, adsorption.

(Concerned with sequence \underline{A005558}.)

Received October 29 2004; revised version received September 1 2005. Published in Journal of Integer Sequences, September 1 2005.

Return to Journal of Integer Sequences home page.