enumeration of lattice walks

Introduction

We present explicit formulas for the number of walks in certain lattices. Proofs are given in a separate entry.

Definitions

The following definitions formalize the concepts of square lattice, triangular lattice, honeycomb lattice, dice lattice, and walk.

Definition

The square lattice is the graph on vertex set $\mathbb{Z}\times\mathbb{Z}$ with each vertex $(i,j)$ adjacent to vertices $(i+1,j)$, $(i-1,j)$, $(i,j+1)$ and $(i,j-1)$.

Definition

The triangular lattice is the graph on vertex set $\mathbb{Z}\times\mathbb{Z}$ with each vertex $(i,j)$ adjacent to vertices $(i+1,j)$, $(i-1,j)$, $(i,j+1)$, $(i,j-1$, $(i-1,j+1)$, and $(i+1,j-1)$.

Definition

The honeycomb lattice is the graph on vertex set $\{(i,j)\in\mathbb{Z}\times\mathbb{Z}:i+j\not\equiv 2\pmod{3}\}$, and with the following adjacencies:

1. 1.

If $i+j\equiv 0\pmod{3}$, then $(i,j)$ is adjacent to vertices $(i+1,j)$, $(i,j+1)$, and $(i-1,j-1)$.

2. 2.

If $i+j\equiv 1\pmod{3}$, then $(i,j)$ is adjacent to vertices $(i-1,j)$, $(i,j-1)$, and $(i+1,j+1)$.

Definition

The dice lattice is the graph on vertex set $\mathbb{Z}\times\mathbb{Z}$ with the following adjacencies:

1. 1.

If $i+j\equiv 0\pmod{3}$, then $(i,j)$ is adjacent to vertices $(i+1,j)$, $(i-1,j)$, $(i,j+1)$, $(i,j-1)$, $(i+1,j+1)$, and $(i-1,j-1)$.

2. 2.

If $i+j\equiv 1\pmod{3}$, then $(i,j)$ is adjacent to vertices $(i-1,j)$, $(i,j-1)$, and $(i+1,j+1)$.

3. 3.

If $i+j\equiv 2\pmod{3}$, then $(i,j)$ is adjacent to vertices $(i+1,j)$, $(i,j+1)$, and $(i-1,j-1)$.

Definition

A walk in a graph is a sequence of vertices where consecutive vertices in the sequence are adjacent. Notice that the same vertex can appear multiple times in a walk. A closed walk is a walk starting and ending with the same vertex. We use the notation $w(x,y,n)$ for the number of walks of length $n$ from $(0,0)$ to $(x,y)$ in a lattice.

Square lattice

The number of walks $w(x,y,n)$ of length $n$ from $(0,0)$ to $(x,y)\in\mathbb{Z}\times\mathbb{Z}$ in the square lattice is given by

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

whenever $x+y$ and $n$ have the same parity. Otherwise $w(x,y,n)=0$.

Triangular lattice

The number of walks $w(x,y,n)$ of length $n$ from $(0,0)$ to $(x,y)\in\mathbb{Z}\times\mathbb{Z}$ in the triangular lattice is given by

 $\displaystyle w(x,y,n)$ $\displaystyle=\sum_{k=0}^{n}(-2)^{n-k}\binom{n}{k}\sum_{j=0}^{k}\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=0}^{n}(-2)^{n-k}\binom{n}{k}\sum_{j=0}^{k}% \binom{k}{j}^{3}$

Honeycomb lattice

The number of walks $w(x,y,n)$ of even length $n$ from $(0,0)$ to $(x,y)\in\mathbb{Z}\times\mathbb{Z}$ in the honeycomb lattice is given by

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

whenever $x+y\equiv 0\pmod{3}$. Otherwise w(x,y,n) = 0.

The number of walks of odd length $n$ from $(0,0)$ to $(x,y)\in\mathbb{Z}\times\mathbb{Z}$ is $w(x,y,n)=w(x-1,y,n-1)+w(x,y+1,n-1)+w(x+1,y+1,n-1)$ if $x+y\equiv 1\pmod{3}$. Otherwise $w(x,y,n)=0$.

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

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

Dice lattice

The number of walks $w(x,y,n)$ of even length $n$ from $(0,0)$ to $(x,y)$ in the dice lattice is given by

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

whenever $x+y\equiv 0\pmod{3}$. Otherwise $w(x,y,n)=0$.

The number of walks of odd length $n$ from $(0,0)$ to $(x,y)\in\mathbb{Z}\times\mathbb{Z}$ is $w(x,y,n)=w(x+1,y,n-1)+w(x,y+1,n-1)+w(x-1,y-1,n-1)$ if $x+y\equiv 2\pmod{3}$; if $x+y\equiv 1\pmod{3}$, $w(x,y,n)=w(x-1,y,n-1)+w(x,y-1,n-1)+w(x+1,y+1,n-1)$. Otherwise $w(x,y,n)=0$.

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

 $\displaystyle w(0,0,n)=2^{n/2}\sum_{k=0}^{n/2}\binom{n/2}{k}\sum_{j=0}^{k}% \binom{k}{j}^{3}=2^{n/2}\sum_{k=0}^{n/2}\binom{n/2}{k}^{2}\binom{2k}{k}$
Title enumeration of lattice walks EnumerationOfLatticeWalks 2013-03-22 19:20:54 2013-03-22 19:20:54 csguy (26054) csguy (26054) 5 csguy (26054) Topic msc 05A15