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