Number of orbits with Burnside's lemma

Question

We color a equilateral triangle by coloring each edge with one of $k \geq 1$ colors. Find a formula for the number of orbits under the action of $D_6$, the dihedral group of $6$ elements, on the resulting set.

---

I'm supposed to use Burnside's lemma for this question. So let's call the set of colored triangles $X$. The number of elements in $X$ equals $k^3$.

Burnside's lemma gives us:

The number of orbits $=\frac{1}{6}\sum_{g \in D_6} |X^g|$, where $X^g$ is the set of elements that are fixed by $g \in D_6$.

$e$ fixes all the elements of $X$, so $|X^e|=k^3$

$r$ also fixes all the elements of $X$ because a rotation doesn't really produce a different triangle.

The same goes for $X^{r^2}$.

$s$ fixes the triangles that have at least two edges with the same color, so $|X^s|=k^2$. And since rotations don't really change anything, the same goes for $X^{sr}$ and $X^{sr^2}$.

So now we have that the number of orbits equals:

$$\frac{3k^3 + 3k^2}{6}$$

But.. I don't believe this is correct. If $k=2$ we have two distinct triangles whose edges share the same color and two distinct triangles that have two edges with the same color. So we would expect to have $4$ orbits. But when I plug in $k=2$ in my formula I get $\frac{36}{6}=6$ orbits.

Where did I go wrong?

Answer 1

Actually we have

$$|X^r| = |X^{r^2}| = k$$

and so the number of orbits is $$|X/G| = \frac{k^3 + 3k^2 + 2k}{6}$$

which gives the right answer ($(8+12+4)/6=24/6=4$) for $k = 2$.

---

There seems to be a problem with your reasoning, as reflected in your language use ("$X^s$ fixes..."). It is not $X^g$ which fixes elements of $X$, but rather $g$; and $X^g$ is the set of all coloured triangles fixed by $g$. Incidentally, this is very different from $Gx$, the orbit of the element $x$; and from $G_x$, the set of group elements which fix (or "get stuck on") $x$.

We can count $|X^g|$ by realizing that being fixed by $g$ is a severe restriction on the form of the colouring.

For example, to count $|X^r|$, we ask ourselves: if $x = r.x$ i.e. if a triangle looks the same after a rotation, how must it be coloured? All the edges have to be the same! So they can be all one red, or all one blue, etc. Thus, $|X^r| = k$.

Another example: to count $|X^s|$, we consider (for concreteness sake) $s$ to be a flip through an altitude. If $s.x = x$ then the two sides meeting at the vertex (of the altitude) have to have the same colour; the remaining side can be any colour. This gives the exponent 2 on $k$.

Answer 2

The rotation $r$ doesn't fix all the elements. It only fixes the elements that are colored with a single color, of which there are $k$, so $|X^r|=k$. The same goes for $r^2=r^{-1}$. It follows that the number orbits equals $$\frac{1}{6}(k^3+3k^2+2k)=\frac{1}{6}k(k+1)(k+2).$$

Answer 3

Let $X$ be the set of different $k$-coloring of the edges of a triangle. Then, the number of configurations in $X$ is $|X|=k^3$. Some of these configurations are indistinguishable under the action of $D_6$. We want to find the number of orbits $t$ of the action of $D_6$ on $X$. Each element of $D_6$ effects a permutation of the configurations in $X$, and this permutation can have fixed points. By the Cauchy-Frobenius (not-Burnside) lemma, $t = \frac{1}{6} \sum_{g \in D_6} |fix(g)|$, where $fix(g)$ is the set of configurations in $X$ which are fixed by $g$.

Observe that if $g$ is the rotation $r$, then the set of configurations which are fixed by $g$ is the set of configurations that assign the same color to each of the three edges. The number of such monochromatic configurations in $X$ is equal to $k$. Hence, the number $|fix(r)|$ of configurations fixed by $r$ is equal to $k$.

The remaining parts of your calculation are correct: the identity $e$ fixes $k^3$ configurations, and a reflection fixes $k^2$ configurations. Hence, the number of orbits is $t=\frac{1}{6} (2k+k^3+3k^2)$.