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 Z×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 Z×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)Z×Z:i+j2(mod3)}, and with the following adjacencies:

  1. 1.

    If i+j0(mod3), then (i,j) is adjacent to vertices (i+1,j), (i,j+1), and (i-1,j-1).

  2. 2.

    If i+j1(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 Z×Z with the following adjacencies:

  1. 1.

    If i+j0(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. 2.

    If i+j1(mod3), then (i,j) is adjacent to vertices (i-1,j), (i,j-1), and (i+1,j+1).

  3. 3.

    If i+j2(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 multipleMathworldPlanetmath 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 the square lattice is given by

w(x,y,n)=(nn+x-y2)(nn-x-y2)

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 the triangular lattice is given by

w(x,y,n) =k=0n(-2)n-k(nk)j=0k(kj)(kj-x-y)(kj-x)

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

w(0,0,n)=k=0n(-2)n-k(nk)j=0k(kj)3

Honeycomb lattice

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

w(x,y,n) =k=0n/2(n/2k)j=0k(kj+x-(x+y)/3)(kj)(kj+(x+y)/3)
=k=0n/2(n/2k)(n/2k+(x+y)/3)(2k+(x+y)/3k+(2x-y)/3)

whenever x+y0(mod3). Otherwise w(x,y,n) = 0.

The number of walks of odd length n from (0,0) to (x,y)× 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+y1(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)=k=0n/2(n/2k)j=0k(kj)3=k=0n/2(n/2k)2(2kk)

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) =2n/2k=0n/2(n/2k)j=0k(kj+x-(x+y)/3)(kj)(kj+(x+y)/3)
=2n/2k=0n/2(n/2k)(n/2k+(x+y)/3)(2k+(x+y)/3k+(2x-y)/3)

whenever x+y0(mod3). Otherwise w(x,y,n)=0.

The number of walks of odd length n from (0,0) to (x,y)× 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+y2(mod3); if x+y1(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)=2n/2k=0n/2(n/2k)j=0k(kj)3=2n/2k=0n/2(n/2k)2(2kk)
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