[Math] Enumerating/counting paths of a given length on a 2D lattice

Question

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

Answer 1

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$.