Skip to main content
MathOverflow

Return to Answer

added 32 characters in body
Source Link
David E Speyer
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763
 
 
 
 
 
 
 
 
added 350 characters in body
Source Link
David E Speyer
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

If you only wanted to quotient by symmetries of the cube, and not by shift (and presumably, reversal) of paths, there would be a very clean answer. The symmetry group of the cube is $S_n \ltimes \{ \pm 1 \}^n$, which acts on $\{ \pm 1, \pm 2, \ldots, \pm n \}$ in the obvious way. We want to consider permutations of the set $\{ \pm 1, \pm 2, \ldots, \pm n \}$, up to the action of the symmetries of the cube. This action is free, so there are $$\frac{(2n)!}{2^n n!} = (2n-1) (2n-3) (2n-5) \cdots 5 \cdot 3 \cdot 1 = (2n-1)!!$$ walks up to symmetries of the cube. (If you aren't familiar with the double factorial notation, see WikipediaReference for double factorial notation.)

We can do this using Burnside's lemmaBurnside's lemma. Recall: Let $G$ be a finite group acting on a finite set $X$. Then Burnside's lemma says that the number of orbits of $G$ on $X$ is $$\frac{1}{|G|} \sum_{g \in G} |X^g|. $$ So, for each $g$ in the dihedral group, we need to figure out how many chord diagrams are fixed by $g$. (For an easier problem using the same strategy, see how we use Burnside's lemma to count necklaces up to rotation.)

\textbf{Case 1:}Case 1: $g$ is a rotation with period $d$ for $d$ odd.

\textbf{Case 2:}Case 2: $g$ is a rotation with period $d$ for $d$ even.

\textbf{Case 3:}Case 3: $g$ is a reflection with no fixed points.

\textbf{Case 4:}Case 4: $g$ is a reflection with two fixed points.

Summing over the whole dihedral group, we get our FINAL ANSWER: $$\frac{1}{4n} \left( \sum_{d|2n,\ d \ \text{odd}} \phi(d) \left( \frac{2n}{d} -1 \right)!! d^{n/d} + \sum_{d|2n,\ d \ \text{even}} \phi(d) \tau_{2n/d}(d) + n \tau_n(2) + n \tau_{n-1}(2) \right).$$ Here $\phi(d)$ is Euler's totient functionEuler's totient function, which counts the number of order $d$ rotations in the dihedral group.

If you only wanted to quotient by symmetries of the cube, and not by shift (and presumably, reversal) of paths, there would be a very clean answer. The symmetry group of the cube is $S_n \ltimes \{ \pm 1 \}^n$, which acts on $\{ \pm 1, \pm 2, \ldots, \pm n \}$ in the obvious way. We want to consider permutations of the set $\{ \pm 1, \pm 2, \ldots, \pm n \}$, up to the action of the symmetries of the cube. This action is free, so there are $$\frac{(2n)!}{2^n n!} = (2n-1) (2n-3) (2n-5) \cdots 5 \cdot 3 \cdot 1 = (2n-1)!!$$ walks up to symmetries of the cube. (If you aren't familiar with the double factorial notation, see Wikipedia.)

We can do this using Burnside's lemma. Recall: Let $G$ be a finite group acting on a finite set $X$. Then Burnside's lemma says that the number of orbits of $G$ on $X$ is $$\frac{1}{|G|} \sum_{g \in G} |X^g|. $$ So, for each $g$ in the dihedral group, we need to figure out how many chord diagrams are fixed by $g$.

\textbf{Case 1:} $g$ is a rotation with period $d$ for $d$ odd.

\textbf{Case 2:} $g$ is a rotation with period $d$ for $d$ even.

\textbf{Case 3:} $g$ is a reflection with no fixed points.

\textbf{Case 4:} $g$ is a reflection with two fixed points.

Summing over the whole dihedral group, we get $$\frac{1}{4n} \left( \sum_{d|2n,\ d \ \text{odd}} \phi(d) \left( \frac{2n}{d} -1 \right)!! d^{n/d} + \sum_{d|2n,\ d \ \text{even}} \phi(d) \tau_{2n/d}(d) + n \tau_n(2) + n \tau_{n-1}(2) \right).$$ Here $\phi(d)$ is Euler's totient function, which counts the number of order $d$ rotations in the dihedral group.

If you only wanted to quotient by symmetries of the cube, and not by shift (and presumably, reversal) of paths, there would be a very clean answer. The symmetry group of the cube is $S_n \ltimes \{ \pm 1 \}^n$, which acts on $\{ \pm 1, \pm 2, \ldots, \pm n \}$ in the obvious way. We want to consider permutations of the set $\{ \pm 1, \pm 2, \ldots, \pm n \}$, up to the action of the symmetries of the cube. This action is free, so there are $$\frac{(2n)!}{2^n n!} = (2n-1) (2n-3) (2n-5) \cdots 5 \cdot 3 \cdot 1 = (2n-1)!!$$ walks up to symmetries of the cube. (Reference for double factorial notation.)

We can do this using Burnside's lemma. Recall: Let $G$ be a finite group acting on a finite set $X$. Then Burnside's lemma says that the number of orbits of $G$ on $X$ is $$\frac{1}{|G|} \sum_{g \in G} |X^g|. $$ So, for each $g$ in the dihedral group, we need to figure out how many chord diagrams are fixed by $g$. (For an easier problem using the same strategy, see how we use Burnside's lemma to count necklaces up to rotation.)

Case 1: $g$ is a rotation with period $d$ for $d$ odd.

Case 2: $g$ is a rotation with period $d$ for $d$ even.

Case 3: $g$ is a reflection with no fixed points.

Case 4: $g$ is a reflection with two fixed points.

Summing over the whole dihedral group, we get our FINAL ANSWER: $$\frac{1}{4n} \left( \sum_{d|2n,\ d \ \text{odd}} \phi(d) \left( \frac{2n}{d} -1 \right)!! d^{n/d} + \sum_{d|2n,\ d \ \text{even}} \phi(d) \tau_{2n/d}(d) + n \tau_n(2) + n \tau_{n-1}(2) \right).$$ Here $\phi(d)$ is Euler's totient function, which counts the number of order $d$ rotations in the dihedral group.

Source Link
David E Speyer
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

If you only wanted to quotient by symmetries of the cube, and not by shift (and presumably, reversal) of paths, there would be a very clean answer. The symmetry group of the cube is $S_n \ltimes \{ \pm 1 \}^n$, which acts on $\{ \pm 1, \pm 2, \ldots, \pm n \}$ in the obvious way. We want to consider permutations of the set $\{ \pm 1, \pm 2, \ldots, \pm n \}$, up to the action of the symmetries of the cube. This action is free, so there are $$\frac{(2n)!}{2^n n!} = (2n-1) (2n-3) (2n-5) \cdots 5 \cdot 3 \cdot 1 = (2n-1)!!$$ walks up to symmetries of the cube. (If you aren't familiar with the double factorial notation, see Wikipedia.)

We can biject these "walks up to symmetries of the cube" with ways to partition $\{ 1,2,3,\ldots, 2n \}$ into $n$ sets of size $2$: We have a block $\{ i,j \}$ in the partition if the $i$-th step and the $j$-th step are edges in opposite directions. For example, your walk $(+1,+2,+3,-1,-3,-2)$ corresponds to the partition $\{ 1,4 \} \sqcup \{ 2,6 \} \sqcup \{ 3,5 \}$. I'll visualize this by drawing $2n$ points around the boundary of a circle, connected by chords.

The figure below, taken from Wikipedia, shows the $15 = 5!!$ chord diagrams in the $n=3$ case, corresponding to the walks in a $3$ dimensional cube.

The fifteen pairings of six points

Now, we want to quotient further by shifting the walk sequences, and I assume also by reversing them. This gives an action of the dihedral group of order $4n$. In terms of our chord diagrams, we want to count these chord diagrams up to rotation and reflections.

I have edited the Wikipedia figure to show how the $15$ walks, above, are grouped into the $5$ classes that you found.

The fifteen pairings of six points, grouped into five symmetry classes

We can do this using Burnside's lemma. Recall: Let $G$ be a finite group acting on a finite set $X$. Then Burnside's lemma says that the number of orbits of $G$ on $X$ is $$\frac{1}{|G|} \sum_{g \in G} |X^g|. $$ So, for each $g$ in the dihedral group, we need to figure out how many chord diagrams are fixed by $g$.

It will be convenient to introduce the notation. $$\tau_m(x) := \sum_{k=0}^{\lfloor m/2 \rfloor} \binom{m}{2k} (2k-1)!! \cdot x^k. $$ For example, $$\tau_4(x) = 1+\binom{4}{2} 1!! x + \binom{4}{4} 3!! x^2 = 1 + 6 x + 3 x^2.$$ In other words, the coefficients of $\tau_m$ are the rows of https://oeis.org/A100861 .

We now carry out the Burnside computation, and break into cases:

\textbf{Case 1:} $g$ is a rotation with period $d$ for $d$ odd.

So $g$ breaks $\{1,2,\ldots, 2n \}$ up into $\tfrac{2n}{d}$ orbits, each of size $d$. A $g$-invariant matching must pair these orbits up with each other. There are $\left( \tfrac{2n}{d} -1 \right)!!$ ways to pair off the orbits and then, for each pair of orbits, there are $d$ $g$-invariant ways to match them. (Match one element arbitrarily, the rest are fixed.) So, in this case, $$|X^g| = \left( \frac{2n}{d} -1 \right)!! d^{n/d}.$$

\textbf{Case 2:} $g$ is a rotation with period $d$ for $d$ even.

Again $g$ breaks $\{1,2,\ldots, 2n \}$ up into $\tfrac{2n}{d}$ orbits, each of size $d$. We can still pair off orbits with each other, but we can also choose one of the orbits and match it within itself. In each orbit $\{ z, gz, g^2 z, \ldots, g^d z \}$, there is a unique $g$-invariant matching, namely, matching $g^i z$ with $g^{i+d/2} z$.

So we must choose $n/2d - 2k$ of the orbits to match with themselves, then pair off the remaining $2k$ orbits in one of $(2k-1)!!$ possible ways and, finally, for each pair of orbits, choose one of the $d$ many possible matchings. In short, in this case, $$|X^g| = \tau_{2n/d}(d).$$

\textbf{Case 3:} $g$ is a reflection with no fixed points.

This is exactly like Case 2 for $d=2$, we have $$|X^g| = \tau_{n}(2).$$

\textbf{Case 4:} $g$ is a reflection with two fixed points.

The two fixed points must be matched to each other. The remaining $2n-2$ points act just like Case $3$, so $$|X^g| = \tau_{n-1}(2).$$

Summing over the whole dihedral group, we get $$\frac{1}{4n} \left( \sum_{d|2n,\ d \ \text{odd}} \phi(d) \left( \frac{2n}{d} -1 \right)!! d^{n/d} + \sum_{d|2n,\ d \ \text{even}} \phi(d) \tau_{2n/d}(d) + n \tau_n(2) + n \tau_{n-1}(2) \right).$$ Here $\phi(d)$ is Euler's totient function, which counts the number of order $d$ rotations in the dihedral group.

For example, when $n=3$, we get $$\frac{1}{12} \left( \phi(1) \cdot 5!! + \phi(3) \cdot 1!! \cdot 3 + \phi(2) \tau_{3}(2) + \phi(6) \tau_1(6) + 3 \tau_3(2) + 3 \tau_2(2) \right)=$$ $$\frac{1}{12} (1 \cdot 15 + 2 \cdot 3 + 1 \cdot 7 + 2 \cdot 1 + 3 \cdot 7 + 3 \cdot 3)=5.$$

You can enjoy going through the diagram of fifteen matchings above, considering the various elements in the hexagonal dihedral group, and seeing how they fix $15$, $3$, $7$, $1$, $7$ or $3$ matchings.