Counting the tiles in the game Tsuro I'd like to count the number of Tsuro game tiles. In the game, a tile is a square with two points on each side where each point is connected to exactly one other point (no point connects to itself). Tiles can be rotated, so I'd like to count the number of unique tiles. The game comes with 35 tiles.
Should I treat this as a coloring problem on the number of pairs of points and try using Polya enumeration? If so, I'd appreciate a hint.
Is there a better method -- something easy that I'm missing?
Ultimately, I'd like a generalizable method (say n points on each side).
Thanks.
 A: The usual way to do this is using Burnside's lemma, which says that the size of the quotient group is given by
$$
|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^{g}|,
$$
where $|X^{g}|$ is the number of elements of $X$ fixed by $g$.  Here $G$ is the cyclic group of order four, and each Tsuro tile can have no symmetry, or $180^{\circ}$ rotational symmetry, or full $90^{\circ}$ rotational symmetry.  So the number of inequivalent Tsuro tiles is given by
$$
\frac{1}{4}\left(|X|+|X_{2}|+2|X_{4}|\right).
$$
When counting tiles with $180^{\circ}$ rotational symmetry, consider two adjacent sides.  You can choose some of these spots to pair with their mirror partners; the remainder (which must be even) must be paired with each other, but each pairing can be done in $2$ different ways (you can pair a spot with a different spot on the same half or on the mirror half).  Similarly, when counting tiles with $90^{\circ}$ rotational symmetry, you choose some spots to pair with their mirror partners, leaving an even number to pair with each other, and each such pairing can be done in $4$ different ways.  Given $q$ spots, where $q$ is even, there are $(q-1)!!$ ways to pair them with each other.  So if there are $n$ spots on each side, then
$$
|X| = (4n-1)!!,
$$
$$
|X_2|=\sum_{k\le n}2^{k}{{2n}\choose{2k}}(2k-1)!!,
$$
and
$$
|X_4|=\sum_{k\le n/2}4^{k}{{n}\choose{2k}}(2k-1)!!.
$$
For $n=2$, then
$$
|X|=7!!=105, \\ |X_2|=4\cdot 3!! + 2\cdot {{4}\choose{2}} + 1 = 25, \\ |X_4|=4+1=5,$$
so
$$
T_2 = \frac{1}{4}\left(105 + 25 + 2\cdot 5\right)=35.
$$
A straightforward Python implementation is:
def fac(n, k=1):
  if n<=1: return 1
  return n*fac(n-k, k)

def ch(m, n):
  return fac(m)/(fac(n)*fac(m-n))

def T(n):
  x = fac(4*n-1, 2)
  x2 = sum([2**k * ch(2*n, 2*k) * fac(2*k-1, 2) for k in xrange(n+1)])
  x4 = sum([4**k * ch(n, 2*k) * fac(2*k-1, 2) for k in xrange(n/2+1)])
  return (x + x2 + 2*x4) / 4

The known results are reproduced:
>>> [T(n) for n in xrange(2,8)]
[35, 2688, 508277, 163715822, 79059439095, 53364540054860]

