# Number of orbits with Burnside's lemma

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?

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

• Can you explain why? Why would we consider a triangle that's only rotated distinct from the original triangle? – Bernie Jun 24 '16 at 14:46
• You should think of $|X^g|$ as asking, "if $g$ fixes the object, what must the object look like?". In our case, if rotating the triangle leaves the triangle looking exactly the same, all the edges have to be the same colour! – Unit Jun 24 '16 at 14:54
• I guess you're right as the math works out. I figured since a triangle with a particular coloring is in the same orbit as its rotations we don't make a distinction between them when counting $|X^g|$ – Bernie Jun 24 '16 at 15:03
• @Bernie I elaborated my answer. – Unit Jun 24 '16 at 15:14

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).$$

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)$.