enumeration of lattice walks (derivation of formulas)

Square lattice

The method of counting walks hinges on the concept of walk generating function: a Laurent polynomial $F(a,b)$ in two variables $a, b$ such that $[a^{x}b^{y}]F^{n}$ equals the number of walks from $(0,0)$ to $(x,y)\in\mathbb{Z}\times\mathbb{Z}$ , where $[a^{x}b^{y}]P(a,b)$ denotes the coefficient of $a^{x}b^{y}$ in $P(a,b)$ .

The idea is to encode each possible step that can be taken from a vertex to an adjacent vertex as a term in $F(a,b)$ . In the case of the square lattice, there are four possible steps from a given vertex: left, right, up, or down. They are encoded as $a$ , $1/a$ , $b$ and $1/b$ . So the walk generating polynomial is $F(a,b)=a+1/a+b+1/b$ . Each term in the expansion of $F^{n}$ corresponds to a walk of length $n$ starting at a fixed vertex. For example, a term in $F^{4}$ such as $a\cdot 1/b\cdot 1/a\cdot 1/a=a^{-1}b^{-1}$ would correspond to the walk of length 4 consisting of the following sequence of steps: right, down,left, left. Moreover, when the term is written as a monomial $a^{x}b^{y}$ , the exponents $x, y$ are precisely the coordinates of the end point of the walk (assuming the origin as the starting point of the walk). Thus in this example the walk would end at vertex $(-1,-1)$ . When all like terms in the expansion are collected it becomes clear that $[a^{x}b^{y}]F^{n}$ counts the number of walks from $(0,0)$ to $(x,y$ ).

To obtain an explicit formula for the number of walks from the origin to $(x,y)$ we factor $F=(a+b)(1+1/ab)$ , raise to the n-th power, use the binomial expansion, and collect like terms:

	$\displaystyle F^{n}$	$\displaystyle=(a+b)^{n}(1+1/ab)^{n}$
		$\displaystyle=(\sum_{i}\binom{n}{i}a^{i}b^{n-i})(\sum_{j}\binom{n}{j}a^{-j}b^{% -j})$
		$\displaystyle=\sum_{(i,j)}\binom{n}{i}\binom{n}{j}a^{i-j}b^{n-i-j}$

The number of walks $w(x,y,n)$ of length $n$ is the coefficient of $a^{x}b^{y}$ , namely

\displaystyle w(x,y,n)

\displaystyle=\sum_{\begin{subarray}{c}i-j=x,\\ n-i-j=y\end{subarray}}\binom{n}{i}\binom{n}{j}

If $n$ and $x+y$ have different parity, there are no integers $i, j$ satisfying the summation constraints, and thus the coefficient of $a^{x}b^{y}$ is zero, indicating that there are no walks of length $n$ from the origin to $(x,y)$ . If, on the other hand, $n$ and $x+y$ have the same parity, the constraints admit only one solution $(i,j)$ , namely $i=(n+x-y)/2$ and $j=(n-x-y)/2$ . Thus, in this case,

\displaystyle w(x,y,n)=\binom{n}{\frac{n+x-y}{2}}\binom{n}{\frac{n-x-y}{2}}

Triangular lattice

In the case of a triangular lattice, the walk generating function is $F=a+1/a+b+1/b+b/a+a/b$ , where each term correspond to the possible steps that can be taken from a vertex to an adjacent vertex: right, left, up, down, diagonally up, diagonally down. It can also be written as $F=(1/a+1/b)(1+a)(1+b)-2$ . The number of walks of length $n$ from the origin to $(x,y)$ is given by the coeeficient of $a^{x}b^{y}$ in $F^{n}$ . Using the binomial expansion, one obtains:

	$\displaystyle F^{n}$	$\displaystyle=[(1/a+1/b)(1+a)(1+b)-2]^{n}$
		$\displaystyle=\sum_{k}(-2)^{n-k}\binom{n}{k}(1/a+1/b)^{k}(1+a)^{k}(1+b)^{k}$
		$\displaystyle=\sum_{k}(-2)^{n-k}\binom{n}{k}\sum_{i}\binom{k}{i}(1/a)^{k-i}(1/% b)^{i}\sum_{j}\binom{k}{j}a^{j}\sum_{j^{\prime}}\binom{k}{j^{\prime}}b^{j^{% \prime}}$
		$\displaystyle=\sum_{k}(-2)^{n-k}\binom{n}{k}\sum_{(i,j,j^{\prime})}\binom{k}{i% }\binom{k}{j}\binom{k}{j^{\prime}}a^{j-k+i}b^{j^{\prime}-i}$

The number of walks $(x,y,n)$ of length $n$ from the origin to $(x,y)$ is the coefficient of $a^{x}b^{y}$ :

\displaystyle w(x,y,n)

\displaystyle=\sum_{k}(-2)^{n-k}\binom{n}{k}\sum_{\begin{subarray}{c}j-k+i=x,% \\ j^{\prime}-i=y\end{subarray}}\binom{k}{i}\binom{k}{j}\binom{k}{j^{\prime}}

Adding the summation constraints for the inner sum, we get $j+j^{\prime}=k+x+y$ , thus $j^{\prime}=k+x+y-j$ and $i=j^{\prime}-y=k+x-j$ . Therefore

\displaystyle w(x,y,n)

\displaystyle=\sum_{k}(-2)^{n-k}\binom{n}{k}\sum_{j}\binom{k}{j}\binom{k}{j-x-% y}\binom{k}{j-x}

In particular, the number of closed walks of length $n$ starting and ending at $(0,0)$ is

\displaystyle w(0,0,n)=\sum_{k}(-2)^{n-k}\binom{n}{k}\sum_{j}\binom{k}{j}^{3}

Honeycomb lattice

First we observe that the honeycomb lattice is a bipartite graph: a graph with vertex set $V=V_{1}\cup V_{2}$ such that every edge is from $V_{1}$ to $V_{2}$ . In the case of the honeycomb lattice, $V=\mathbb{Z}\times\mathbb{Z}=V_{1}\cup V_{2}$ where $V_{1}=\{(x,y)\in V:x+y\equiv 0\pmod{3}\}$ and $V_{2}=\{(x,y)\in V:x+y\equiv 1\pmod{3}\}$ . Every edge in the honeycomb lattice joins a vertex in $V_{1}$ to a vertex in $V_{2}$ . Notice that a walk starting at a vertex in $V_{1}$ will end at a vertex in $V_{1}$ (resp. $V_{2}$ ) if it has even (resp. odd) length.

From a vertex $(i,j)\in V_{1}$ the possible steps are up, right, or diagonally down. These are encoded by $F=a+b+1/ab$ ; on the other hand, if $(i,j)\in V_{2}$ , the possible steps from $(i,j)$ are left, down, or diagonally up, encoded by $G=1/a+1/b+ab$ . Since a walk of even length $n$ from say $(0,0)$ must alternate between points in $V_{1}$ and points in $V_{2}$ , each such walk corresponds to a term in the expansion of $(FG)^{n/2}$ , and $w(x,y,n)=[a^{x}b^{y}](FG)^{n/2}$ . Since $FG=1+(a+b)(a+1/ab)(b+1/ab)$ , we have

	$\displaystyle(FG)^{n/2}$	$\displaystyle=\sum_{k}\binom{n}{k}(a+b)^{k}(a+1/ab)^{k}(b+1/ab)^{k}$
		$\displaystyle=\sum_{k}\binom{n}{k}\sum_{i}\binom{k}{i}a^{k-i}b^{i}\sum_{j}% \binom{k}{j}a^{k-j}(1/ab)^{j}\sum_{j^{\prime}}\binom{k}{j^{\prime}}b^{k-j^{% \prime}}(1/ab)^{j^{\prime}}$
		$\displaystyle=\sum_{k}\binom{n}{k}\sum_{i,j,j^{\prime}}\binom{k}{i}\binom{k}{j% }\binom{k}{j^{\prime}}a^{2k-i-2j-j^{\prime}}b^{k+i-j-2j^{\prime}}$

Thus for $n$ even,

	$\displaystyle w(x,y,n)$	$\displaystyle=[a^{x}b^{y}](FG)^{n/2}$
		$\displaystyle=\sum_{k}\binom{n}{k}\sum_{\begin{subarray}{c}2k-i-2j-j^{\prime}=% x,\\ k+i-j-2j^{\prime}=y\end{subarray}}\binom{k}{i}\binom{k}{j}\binom{k}{j^{\prime}}$

The constraints under the inner sum imply $j^{\prime}=k-j-(x+y)/3$ and $i=k-j-x+(x+y)/3$ . Thus if $x+y\not\equiv 0\pmod{3}$ they are not satisfied by any integers $i$ , $j$ , $j^{\prime}$ , and $w(x,y,n)=0$ . This simply reflects the fact that there are no even length walks from a vertex in $V_{1}$ to a vertex in $V_{2}$ . On the other hand, if $x+y\equiv 0\pmod{3}$ , using $\binom{p}{q}=\binom{p}{p-q}$ we obtain

\displaystyle w(x,y,n)=\sum_{k}^{n/2}\binom{n/2}{k}\sum_{j}\binom{k}{j+x-(x+y)% /3}\binom{k}{j}\binom{k}{j+(x+y)/3}

Walks of odd length $n$ from $(0,0)$ to $(x,y)\in V_{2}$ can be computed by $w(x,y,n)=w(x-1,y,n-1)+w(x,y+1,n-1)+w(x+1,y+1,n-1)$ , where the terms in the right hand side can be computed by the previous formula.

For $x=y=0$ we obtain the following formula for the number of closed walks of even length $n$ starting and ending at $(0,0)$ :

\displaystyle w(0,0,n)=\sum_{k}^{n/2}\binom{n/2}{k}\sum_{j}\binom{k}{j}^{3}

An alternative expansion yields another formula for $w(x,y,n)$ that contains a single summation. Writing $FG=(1+a^{2}b+ab^{2})(1+a^{-2}b^{-1}+a^{-1}b^{-2})$ , we obtain

	$\displaystyle(FG)^{n/2}$	$\displaystyle=\sum_{k}\binom{n/2}{k}(a^{2}b+ab^{2})^{k}\sum_{k^{\prime}}\binom% {n/2}{k^{\prime}}(a^{-2}b^{-1}+a^{-1}b^{-2})^{k^{\prime}}$
		$\displaystyle=\sum_{k,j}\binom{n/2}{k}\binom{k}{j}(a^{2}b)^{k-j}(ab^{2})^{j}% \sum_{k^{\prime},j^{\prime}}\binom{n/2}{k^{\prime}}\binom{k^{\prime}}{j^{% \prime}}(a^{-2}b^{-1})^{k^{\prime}-j^{\prime}}(a^{-1}b^{-2})^{j^{\prime}}$
		$\displaystyle=\sum_{k,j,k^{\prime},j^{\prime}}\binom{n/2}{k}\binom{n/2}{k^{% \prime}}\binom{k}{j}\binom{k^{\prime}}{j^{\prime}}a^{2k-2k^{\prime}-j+j^{% \prime}}b^{k-k^{\prime}+j-j^{\prime}}$

The number of walks $w(x,y,n)$ is the coefficient of $a^{x}b^{y}$ , namely

\displaystyle w(x,y,n)

\displaystyle=\sum_{\begin{subarray}{c}2k-2k^{\prime}-j+j^{\prime}=x,\\ k-k^{\prime}+j-j^{\prime}=y\end{subarray}}\binom{n/2}{k}\binom{n/2}{k^{\prime}% }\binom{k}{j}\binom{k^{\prime}}{j^{\prime}}

The constraints under the summation imply $3k-3k^{\prime}=x+y$ and $3j-3j^{\prime}=2y-x$ , thus $k^{\prime}=k-(x+y)/3$ and $j^{\prime}=j+(x-2y)/3$ . Therefore

\displaystyle w(x,y,n)

\displaystyle=\sum_{k}\binom{n/2}{k}\binom{n/2}{k-(x+y)/3}\sum_{j}\binom{k}{k-% j}\binom{k-(x+y)/3}{j+(x-2y)/3}

But

\displaystyle\sum_{j}\binom{k}{k-j}\binom{k-(x+y)/3}{j+(x-2y)/3}

\displaystyle=\binom{2k-(x+y)/3}{k+(x-2y)/3}

by Vandermonde’s convolution. Therefore

\displaystyle w(x,y,n)

\displaystyle=\sum_{k=0}^{n/2}\binom{n/2}{k}\binom{n/2}{k-(x+y)/3}\binom{2k-(x% +y)/3}{k+(x-2y)/3}

Setting $(x,y)=(0,0)$ we obtain the following formula for the number of closed walks starting and ending at $(0,0)$ :

\displaystyle w(0,0,n)=\sum_{k=0}^{n/2}\binom{n/2}{k}^{2}\binom{2k}{k}

Dice lattice

The dice lattice is also a bipartite graph, with vertex set $V_{0}\cup V_{1}\cup V_{2}$ , where $V_{i}=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}:x+y\equiv i\pmod{3}\}$ , and with edges going from $V_{0}$ to $V_{1}\cup V_{2}$ . The possible moves are:

•

From a vertex in $V_{0}$ : east,west,north,south, northeast,southwest, encoded as $a,1/a,b,1/b,ab,1/ab$ .
•

From a vertex in $V_{1}$ : west, south, northeast, encoded as $1/a,1/b,ab$ .
•

From a vertex in $V_{2}$ : east, north, southwest, encoded as $a,b,1/ab$ .

Moreover, starting at a vertex in $V_{1}$ , moves $a,b,1/ab$ take us to a vertex in $V_{2}$ , and moves $1/a,1/b,ab$ take us to a vertex in $V_{3}$ . Of course any move from a vertex in $V_{2}\cup V_{3}$ takes us back to a vertex in $V_{1}$ . After these observations and a moment’s reflection, we conclude that for even $n$ the number of walks of length $n$ starting at $(0,0)$ is the coefficient of $a^{x}b^{y}$ in

\displaystyle[FG+GF]^{n/2}

\displaystyle=2^{n/2}(FG)^{n/2}

where $F=a+b+1/ab$ and $G=1/a+1/b+ab$ are defined as in the case of the honeycomb lattice. So the number of walks of even length from $(0,0)$ to $(x,y)$ is $2^{n/2}$ times the corresponding number of walks in the honeycomb lattice, and the formulas for the dice lattice follow.

Title	enumeration of lattice walks (derivation of formulas)
Canonical name	EnumerationOfLatticeWalksderivationOfFormulas
Date of creation	2013-03-22 19:21:44
Last modified on	2013-03-22 19:21:44
Owner	csguy (26054)
Last modified by	csguy (26054)
Numerical id	4
Author	csguy (26054)
Entry type	Derivation
Classification	msc 05A15