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 $\mathrm{Z}\mathrm{\times }\mathrm{Z}$ with each vertex $\mathrm{(}i\mathrm{,}j\mathrm{)}$ adjacent to vertices $\mathrm{(}i\mathrm{+}\mathrm{1}\mathrm{,}j\mathrm{)}$, $\mathrm{(}i\mathrm{-}\mathrm{1}\mathrm{,}j\mathrm{)}$, $\mathrm{(}i\mathrm{,}j\mathrm{+}\mathrm{1}\mathrm{)}$ and $\mathrm{(}i\mathrm{,}j\mathrm{-}\mathrm{1}\mathrm{)}$.

Definition

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

Definition

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

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

2. If $i+j\equiv 1(mod3)$, 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 $\mathrm{Z}\mathrm{\times }\mathrm{Z}$ with the following adjacencies:

1. If $i+j\equiv 0(mod3)$, 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. If $i+j\equiv 1(mod3)$, then $(i,j)$ is adjacent to vertices $(i-1,j)$, $(i,j-1)$, and $(i+1,j+1)$.

3. If $i+j\equiv 2(mod3)$, 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\mathit{}\mathrm{(}x\mathrm{,}y\mathrm{,}n\mathrm{)}$ for the number of walks of length $n$ from $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{0}\mathrm{)}$ to $\mathrm{(}x\mathrm{,}y\mathrm{)}$ 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

$w(x,y,n)=\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n+x-y}{2}}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n-x-y}{2}}}\right)$

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

$w(x,y,n)$ $={\displaystyle \sum _{k=0}^n}{(-2)}^{n-k}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){\displaystyle \sum _{j=0}^k}\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j-x-y}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j-x}}\right)$

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

$w(0,0,n)={\displaystyle \sum _{k=0}^n}{(-2)}^{n-k}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right){\displaystyle \sum _{j=0}^k}{\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j}}\right)}^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

$w(x,y,n)$ $={\displaystyle \sum _{k=0}^{n/2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right){\displaystyle \sum _{j=0}^k}\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j+x-(x+y)/3}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j+(x+y)/3}}\right)$

$={\displaystyle \sum _{k=0}^{n/2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k+(x+y)/3}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{2k+(x+y)/3}{k+(2x-y)/3}}\right)$

whenever $x+y\equiv 0(mod3)$. 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(mod3)$. 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)$:

$w(0,0,n)={\displaystyle \sum _{k=0}^{n/2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right){\displaystyle \sum _{j=0}^k}{\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j}}\right)}^3={\displaystyle \sum _{k=0}^{n/2}}{\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right)}^2\left({\displaystyle \genfrac{}{}{0pt}{}{2k}{k}}\right)$

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

$w(x,y,n)$ $=2^{n/2}{\displaystyle \sum _{k=0}^{n/2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right){\displaystyle \sum _{j=0}^k}\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j+x-(x+y)/3}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j+(x+y)/3}}\right)$

$=2^{n/2}{\displaystyle \sum _{k=0}^{n/2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k+(x+y)/3}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{2k+(x+y)/3}{k+(2x-y)/3}}\right)$

whenever $x+y\equiv 0(mod3)$. 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(mod3)$; if $x+y\equiv 1(mod3)$, $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)$:

$w(0,0,n)=2^{n/2}{\displaystyle \sum _{k=0}^{n/2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right){\displaystyle \sum _{j=0}^k}{\left({\displaystyle \genfrac{}{}{0pt}{}{k}{j}}\right)}^3=2^{n/2}{\displaystyle \sum _{k=0}^{n/2}}{\left({\displaystyle \genfrac{}{}{0pt}{}{n/2}{k}}\right)}^2\left({\displaystyle \genfrac{}{}{0pt}{}{2k}{k}}\right)$

Title	enumeration of lattice walks
Canonical name	EnumerationOfLatticeWalks
Date of creation	2013-03-22 19:20:54
Last modified on	2013-03-22 19:20:54
Owner	csguy (26054)
Last modified by	csguy (26054)
Numerical id	5
Author	csguy (26054)
Entry type	Topic
Classification	msc 05A15