enumeration of lattice walks (derivation of formulas)
The method of counting walks hinges on the concept of walk generating function: a Laurent polynomial in two variables such that equals the number of walks from to , where denotes the coefficient of in .
The idea is to encode each possible step that can be taken from a vertex to an adjacent vertex as a term in . 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 , , and . So the walk generating polynomial is . Each term in the expansion of corresponds to a walk of length starting at a fixed vertex. For example, a term in such as 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 , the exponents 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 . When all like terms in the expansion are collected it becomes clear that counts the number of walks from to ).
To obtain an explicit formula for the number of walks from the origin to we factor , raise to the n-th power, use the binomial expansion, and collect like terms:
The number of walks of length is the coefficient of , namely
If and have different parity, there are no integers satisfying the summation constraints, and thus the coefficient of is zero, indicating that there are no walks of length from the origin to . If, on the other hand, and have the same parity, the constraints admit only one solution , namely and . Thus, in this case,
In the case of a triangular lattice, the walk generating function is , 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 . The number of walks of length from the origin to is given by the coeeficient of in . Using the binomial expansion, one obtains:
The number of walks of length from the origin to is the coefficient of :
Adding the summation constraints for the inner sum, we get , thus and . Therefore
In particular, the number of closed walks of length starting and ending at is
First we observe that the honeycomb lattice is a bipartite graph: a graph with vertex set such that every edge is from to . In the case of the honeycomb lattice, where and . Every edge in the honeycomb lattice joins a vertex in to a vertex in . Notice that a walk starting at a vertex in will end at a vertex in (resp. ) if it has even (resp. odd) length.
From a vertex the possible steps are up, right, or diagonally down. These are encoded by ; on the other hand, if , the possible steps from are left, down, or diagonally up, encoded by . Since a walk of even length from say must alternate between points in and points in , each such walk corresponds to a term in the expansion of , and . Since , we have
Thus for even,
The constraints under the inner sum imply and . Thus if they are not satisfied by any integers , , , and . This simply reflects the fact that there are no even length walks from a vertex in to a vertex in . On the other hand, if , using we obtain
Walks of odd length from to can be computed by , where the terms in the right hand side can be computed by the previous formula.
For we obtain the following formula for the number of closed walks of even length starting and ending at :
An alternative expansion yields another formula for that contains a single summation. Writing , we obtain
The number of walks is the coefficient of , namely
The constraints under the summation imply and , thus and . Therefore
by Vandermonde’s convolution. Therefore
Setting we obtain the following formula for the number of closed walks starting and ending at :
The dice lattice is also a bipartite graph, with vertex set , where , and with edges going from to . The possible moves are:
From a vertex in : east,west,north,south, northeast,southwest, encoded as .
From a vertex in : west, south, northeast, encoded as .
From a vertex in : east, north, southwest, encoded as .
Moreover, starting at a vertex in , moves take us to a vertex in , and moves take us to a vertex in . Of course any move from a vertex in takes us back to a vertex in . After these observations and a moment’s reflection, we conclude that for even the number of walks of length starting at is the coefficient of in
where and are defined as in the case of the honeycomb lattice. So the number of walks of even length from to is 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)|
|Date of creation||2013-03-22 19:21:44|
|Last modified on||2013-03-22 19:21:44|
|Last modified by||csguy (26054)|