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