# Enumerating/counting paths of a given length on a 2D lattice

All,

I'm wondering if anyone can point me to a reference on how to address the following problem. In my thesis work on lattice QCD many years ago I had to enumerate all possible paths of a given length on a 2D lattice, up to the symmetries of reflection and rotation (plus some other internal symmetries we won't concern ourselves with here). I've been wondering whether it would be possible to compute the number of such paths without explicitly listing them all, for example using generating-function techniques. The paths were used to generate coherent-states for fermionic operators. Each path had a quark at one end and an anti-quark at the other end.

To make this more concrete, I'll give some examples. Write the link in the plus and minus $x$ directions as 'x' and 'X', likewise use 'y' and 'Y' for the plus and minus $y$ directions, respectively. Note that these 'links' represent unitary operators so combinations like $xX$ and $Yy$ cancel, so are not counted. Then the first few examples are:

Length 1: $x$

Length 2: $xx$, $xy$

(note here, for example, that the other paths $yy$, $YY$, $XX$, $xY$, $yX$, $yx$, etc, are related to the two that I listed by symmetry, so are not counted).

Length 3: $xxx$, $xxy$, $xyx$, $xyX$

Length 4: $xxxx$, $xxxy$, $xxyx$, $xxyy$, $xxyX$, $xyxY$, $xyxy$, $xyyx$, $xyyX$, $xyXY$

and so on.

Let $A_n$ be the number of paths of length $n$. As $n$ gets large, it seems like there could be a simple asymptotic relation for $A_{n+1}/A_n$, since most paths would be extended by adjoining the three possible directional links (that don't cancel) to the end of the path, so maybe the ratio would go to 3 (NOTE - which it seems to from Liviu's result)?

Again, this work was done years ago, but this problem has stuck in my mind. I never had any formal training in combinatorics or graphs, but from what I've read this seems like it could be a tractable problem. For me, the issue of having to not count paths that are related by symmetries makes it quite difficult.

Thanks for any information/references/thoughts on this! I plan to write some code to numerically check the behavior of $A_n$. My goal is to have someone point me in the right direction to get started on an 'analytic' solution or asymptotic estimate. By the way, the same problem arises in 3D, but I will stick to 2D first.

EDIT: Using Liviu's solution I found this sequence in OEIS, related to bending of a wire in 2D (the same problem). It is here: link text

Regards, Tom

-
When you say "2D lattice" you mean explicitly $\mathbb{Z}^2$? – David Benson-Putnins May 6 '13 at 21:45
It seems to me that this should be solvable by a straightforward application of Burnside's lemma. – Ira Gessel May 6 '13 at 21:49
@Liviu: I was afraid that I did not describe the problem well enough! The symmetries are reflection in $x$ and $y$, and rotations by any multiple of $\pi /2$. So the symmetry group you wrote down is correct, but as Gerhard noted reversals are also identified with each other (This corresponds to 'charge conjugation.') Any path that can converted to another by these symmetries is considered identical. For example, $xxyX$ and $YYXY$ are the same; take the second one and reflect about the $y$ axis, then rotate by $\pi / 2$. I will look up Burnside's lemma, thanks for the information! – Tom Dickens May 6 '13 at 23:13
If you add the extra global symmetry $C$, path reversal,then clearly $C^2=1$ and $C$ commutes with the other symmetries $R_x,R_y,J$. The symmetry group has order $16$ and you need to count the number of admissible paths invariant under each of the sixteen symmetries. This looks like an enjoyable and doable problem. – Liviu Nicolaescu May 7 '13 at 9:26
Hint: There is more then 7 paths of length 4. After you count the ones of length 5, you can probably look the sequence up in OEIS. – JHI May 8 '13 at 18:06

I am trying to make sense of your problem. From what I can gather you are talking about walks with steps of size $1$ in each of the cardinal directions East, West, North, South, (E,W,N,S). To use your notation $E=x$, $W=X$, $N=y$, $S=Y$. You are not allowed to immediately backtrack, i.e., if say you take an $E$-step, then your next step cannot be a $W$-step. I will refer to such paths as admissible. I think that you need to fix the starting point. Assume it is the origin.

The number of admissible paths of length $n$ starting at the origin is $4\cdot 3^{n-1}$.

Alas, there is a symmetry in the problem and this is where I am a bit confused. Its looks to me that the symmetry group is the group $G$ of symmetries of the square with vertices $(\pm 1,0)$, $(0,\pm 1)$. (I could be wrong, but that is what I am getting from your description.) The center of this square is the origin, an the vectors obtained by joining the center with the vertices are the unit vectors $\vec{E},\vec{W},\vec{N},\vec{S}$ pointing in the four cardinal directions.

The group has eight elements and it is generated by the reflection $R_x$ in the $x$-axis and the counterclockwise rotation $J$ by ninety degrees. The elements of this group are

$$1, J, J^2, J^3, R_x, R_xJ, R_xJ^2, R_xJ^3.$$

Assuming that my guess is correct you need to count admissible paths, where two paths that are related by one of the above eight symmetries are considered identical. Denote by $Q_n$ the number of such paths of length $n$.

Here you need to invoke Burnside's theorem. Here is what it says in this case.

For each $g\in G$ denote by $P_n(g)$ the number of admissible paths of length $n$ that admit $g$ as symmetry. More precisely a path

$$v_1\dotsc,v_n, \;\;v_1,\dotsc,v_n\in \lbrace E,W,N,S\rbrace$$

admits $g$ as symmetry if $g(v_1)\dotsc g(v_n)=v_1\dotsc v_n$. Then Burnside's theorem states that

$$Q_n= \frac{1}{|G|}\sum_{g\in G} P_n(g).$$

There are only three elements $g\in G$ for which $P_n(g)\neq 0$. They are $1, R_x, R_y$, where $R_y$ denotes the reflection in the $y$-axis. Putting all the above together we deduce that

$$Q_n= \frac{1}{8}\Bigl( 4\cdot 3^{n-1}+ 2+2)=\frac{1}{2}\bigl(3^{n-1}+1\bigr).$$

Update. I have worked out the details taking into account the correct symmetry group.

Here is what I found. If $n$ is odd, $n=2m-1$, then

$$Q_n=\frac{1}{4}\bigl(3^{n-1}+2\cdot 3^{m-1}+1\bigr).$$

If $n$ is even, $n=2m$, then

$$Q_n = \frac{1}{4}\bigl( 3^{n-1}+4\cdot 3^{m-1}+1\bigr).$$

Here are a few values.

$$Q_1=1, \;\; Q_2=2,\;\; Q_3=4, \;\; Q_4= 10,\;\; Q_5=25,\;\; Q_6=70.$$

Note that I get $Q_4=10\neq 8,9$. In any case, the details can be found here. Maybe somebody can explain the discrepancy involving $Q_4$.

-
Not quite. v1v2 and v2v1 are identified, as are a path and its reversal. Also, your formula does not match the case n=3. Gerhard "Ask Me About System Design" Paseman, 2013.05.06 – Gerhard Paseman May 6 '13 at 22:37
I guess I screwed up the symmetry group. – Liviu Nicolaescu May 6 '13 at 22:48
Liviu, thanks for the answer. I don't even have around any of the results from this work anymore, I hope to write a simple routine to reconstruct some of it and compare to your formula. (Sorry for the mistakes for n=4.) If anyone is interested the original paper on the lattice gauge theory problem is here: sciencedirect.com/science/article/pii/0550321388902349?np=y – Tom Dickens May 8 '13 at 21:13
@Liviu - Once I listed the correct paths, your solution matches for $n=4$. Thanks for this, I'll take a look at your detailed derivation. I've certainly learned something new! – Tom Dickens May 9 '13 at 1:07
@Liviu - Using your solution I computed several terms and found the sequence in OEIS. See edit to my question for the link. – Tom Dickens May 16 '13 at 15:38