Counting Symmetric Objects

[Note: This essay ought to be considered a "work in progress", except I'm not working on it.]

How many four-bead necklaces can you make with black and white beads?

Well, what's a necklace? Is it just a sequence of four beads in a circle? With that interpretation, the answer is $2^4 = 16$:

There are two possibilities for the first bead, then two for the second bead, and so on, giving a total of $2\times2\times2\times2=2^4=16$ possibilities for the full chain.

But we drew these necklaces as circles, probably for a good reason. You can slide beads along a necklace, in effect rotating it. So a necklace that looks like can be turned into one that looks like , while neither of these can be turned into .

Mathematicians adopt a sort of strange terminology here. They say that the pictures and represent one and the same necklace. In other words, they are two different pictures of the same underlying necklace, in the same way that $\frac{2}{3}$ and $\frac{4}{6}$ are two different pictures of the same underlying fraction. This is mostly just a matter of definition. To a mathematician, a necklace is a little bead-loop picture, with the caveat that two pictures represent the same necklace if one can be rotated to produce the other.

What we did above was count 2⁴ necklace-pictures, rather than the actual underlying necklaces. We overcounted, because some necklaces are represented by more than one picture.

Let's group the 16 pictures above according to their underlying necklace:

To be totally clear about what went into this grouping: If one picture can be rotated into another, they should be in the same group. If one picture cannot be rotated into another, they should be in different groups. In that way, we ensure that each group represents a unique underlying necklace, and by counting groups, we will count the underlying necklaces.

There are 6 groups, so that's our final answer: you can make 6 four-bead necklaces with black and white beads.

Getting from our 16 necklace-pictures to our 6 necklaces wasn't easy. It involved an ad-hoc process, sorting through all the pictures, comparing them to one another, and grouping them together. If the groups were all the same size, some $n$, then we could count the number of groups by calculating $16/n$. But they're not equal sizes. Some necklaces have 4 pictures, some have 2 pictures, and some only have one picture. The pattern looks chaotic.

And if we were making necklaces out of three colors of bead instead of two colors, or six beads long instead of four beads long, the number of pictures would increase dramatically. Putting them into groups, like we did above, would be a tedious, obnoxious, error-prone process. And although we would get the numeric answer we were looking for, the process would leave us without any real understanding of what was going on.

Fortunately, that there is a powerful technique that we can use to count the number of necklaces. In fact, this technique reaches far beyond this one problem and gives us insight into a broad range of problems which have to do with counting some objects "up to" some kind of symmetry. The technique goes by many names, but here we will call it Burnside's lemma. I will show you

the deep concepts of "group" and "action" that Burnside's lemma relies upon,
how the lemma works, and
how you can use the lemma to solve problems which would be very difficult without it.

Transforming necklaces

At the heart of the necklace-counting problem is the concept of turning one picture into another via a transformation. We should make clear and precise what we mean by this.

Consider the necklace-picture $N=$ . It represents the same necklace as the pictures , , and . Why?

Well, we can rotate $N$ into any of the other pictures. The first comes from a 90°-clockwise rotation, the second from a 180°-clockwise rotation, and the third from a 270°-clockwise rotation.

These rotation transformations are the key to understanding the necklace-counting problem, so we will consider them as objects in their own right. We can notate them with arcs, as , , and . With this notation, we can write equations telling what these rotations do to necklace-pictures. Our convention will be to put a rotation before the necklace-picture it acts on, like the $f(x)$ function notation:

=
=
=

We're building an algebra of rotations and necklace-pictures! Nice. In fact, we can make a whole multiplication table, which shows what happens when apply any rotation to any necklace-picture:

This table encodes everything there is to know about how necklaces rotate into one another. And it contains key information to solve our counting problem. See, the column below a necklace-picture shows every other picture that represents the same underlying necklace. Let's re-order the columns, so that necklace-pictures representing the same necklace are next to each other horizontally:

Some order is beginning to emerge from the top table's chaos. Nowhere in this table are the groups mixed up with each other. Taking a picture from one group and rotating it always gives some other picture in the same group. You could imagine breaking the table up into separate tables for each group, each its own little world:

…

I mentioned near the start of this article how counting the number of groups was tricky because the groups were different sizes. (If they were all the same size, we could just count the number of necklace-pictures and then divide by the group size.) Let's take a closer look at the groups and see if we can find any patterns that tell us about their sizes.

It looks like the groups have size 1, 2, and 4. Let's take a sample group of each size to see how they work:

A: B: C:

Group A consists of only one necklace-picture: the one with all black beads. The table shows that, no matter how you rotate this picture, you just get the same picture back again. That's why it's alone in its group -- there's no alternate picture you can turn it into through rotation.

Group C consists of four necklace-pictures: all the pictures with exactly one white bead. This shows an opposite situation. If you take a picture in this group and rotate it, you will always get back a different picture, unless, of course, you applied a 0° rotation. That's why there are four pictures in this group -- one picture for each kind of rotation.

Group B consists of two necklace-pictures: the two which alternate white and black beads. This shows a situation between groups A and C. If you take a picture in this group and rotate it, you will get the same picture back again half the time, and half the time you will get the other picture in the group. That's why there are two pictures in this group.

Symmetry and fixed points

Fundamentally, what we are talking about here is symmetry. The necklace in group A is maximally symmetric -- every way you rotate it, you get back what you started with. The necklaces in group C are maximally asymmetric -- there are no rotations that bring them back to themselves (except the 0° rotation). And the necklaces in group B are somewhere in-between -- some rotations bring you back to the starting picture, and some don't.

The more symmetric a picture is, the smaller its group will be. The less symmetric a picture is, the bigger its group will be.

We can capture this concept of symmetry by looking at fixed points in the table. These are places where a rotation applied to a picture gives back the picture we started with. Here are our three sample groups, with fixed points shaded in:

A: B: C:

This shows a remarkable pattern. Each group has the same number of fixed points! They are distributed different ways, from group to group.

Group A has four fixed points, because it is highly symmetric. There is only one picture, but each of the four rotations make a fixed point for it.
Group C has four fixed points, because it is highly asymmetric. Each picture only gets one fixed point -- the obvious 0° one, but its asymmetry means there are four pictures in the group, the largest number possible.
Group B has four fixed points. Its intermediate level of symmetry means each picture has two fixed points, and there are two pictures.

Here is the full table, with the fixed-point multiplications marked:

Now we know that each group leaves its mark on this table in a very precise way -- each group makes four fixed points. We can leave off the lines marking the group structure:

or even go back to our original, group-ignorant column order:

and we can still extract the number of groups by counting the number of fixed points, and dividing by four! This is fantastic -- we've come up with a mechanical process to count the number of groups without going through and comparing the pictures to each other pair by pair. Just make the table (see above), mark the fixed points (see above), count them up (24), and divide by four (6). Fantastic.

But it gets even better.

Counting fixed points

A mechanical process is a great thing to have. For instance, if I asked you how many necklaces were made of six beads each (black and white), you could make a table, count the fixed points, divide that by six, and answer my question without having to put any real thought into the matter.

But that table would have $2^6=64$ columns in it, so your process would take a fair amount of time. And if I asked you how many necklaces were made of six beads, using three different colors (say, black, white, and red), you would have $3^6=729$ columns to grapple with. This manual fixed-point counting is starting to seem unreasonable. You could write a computer program to do the counting for you, but, with a bit of cleverness, we can do far better than that.

Let's look at our fixed-point table again:

We want to count the number of shaded cells in this table. So far, we've done that by sorting the columns into groups, and counting by groups. But what if, instead of counting by columns, we counted by rows? Can we come up with some way of counting how many fixed points occur in a given row?

Each row corresponds to some rotation transformation. The first is rotation by $\frac{0}{4}360^\circ = 0^\circ$, the second is rotation by $\frac{1}{4}360^\circ = 90^\circ$, and so on. Let's call the first one $R_0$, the second $R_1$, and so on, so $R_k$ is rotation by $\frac{k}{4}360^\circ$. We want to know -- how many necklace-pictures get sent to themselves when rotated by $R_k$, for each $k$?

$R_0$ is easy. Every picture gets sent to itself under a 0° rotation:

Fixed point count: $2^4=16$

$R_1$ is a 90° rotation. What does a fixed point of $R_1$ look like? Well, it's a necklace picture which is sent to itself by a 90° (clockwise) rotation.

	If the top bead is some color $a$,
	then the right bead must be the same color $a$, because the top bead rotates onto the right bead under $R_1$.
	Then, since the right bead is the color $a$, the bottom bead must be the color $a$,
	and so on.

So, to choose a fixed point of $R_1$, you only have one color choice -- pick $a$, and everything else is determined by the fact that your necklace picture must be sent to itself by $R_1$. Hence, there are $2^1 = 2$ fixed points of $R_1$.

Fixed point count: $2^1 = 2$

$R_2$ is a 180° rotation. What does a fixed point of $R_2$ look like?

	If the top bead is some color $a$,
	then the bottom bead must be the same color $a$, because the top bead rotates onto the bottom bead under $R_2$.

This is a different situation than we had with $R_1$. The choice of a top color determines the bottom color, but that's all. We still have freedom to choose the right color as we please:

	If the right bead is some color $b$,
	then the left bead must be the same color $a$, because the top bead rotates onto the bottom bead under $R_2$.

To choose a fixed point of $R_2$, you have two color choices -- pick $a$ and $b$, and everything else is determined. Hence, there are $2^2 = 4$ fixed points of $R_2$.

Fixed point count: $2^2 = 2$

$R_3$ is a 270° rotation. This is really the same thing as a 90° rotation in the other direction, though, so ultimately, the situation for $R_3$ is the same as $R_1$.

Fixed point count: $2^1 = 2$

Let's count these up: We have $2^4 + 2^1 + 2^2 + 2^1 = 24$ fixed points in total. There are four fixed points per picture-group, so there are $\frac{24}{4} = 6$ underlying necklaces, as we showed above.

So far, this is just an especially tedious derivation of something we already knew, but here's the payoff. Suppose we had $k$ colors, rather than 2. Any $k$. Then the derivation above, in terms of counting "free color choices", applies just as well to $k$ as it does to 2. So the total number of fixed points is $k^4 + k^1 + k^2 + k^1 = k^4 + k^2 + 2k$, so the total number of underlying necklaces is $\frac{1}{4}\left(k^4 + k^2 + 2k\right)$.

For the first time, we have a totally general formula:

You can make $\frac{1}{4}\left(k^4 + k^2 + 2k\right)$ four-bead necklaces if there are $k$ colors to choose from.

Let's check this. If $k=3$, this gives us a count of $24$. I'll do the grouping for you…

The $3^4 = 81$ necklace pictures fall perfectly into 24 groups, just as the formula predicted.

[That's as far as the essay got. Just for fun, here's a gadget which automatically performs this analysis for any $n$ and $k$. At the bottom, it shows a representative of each group. Hover over a representative to see how it appears as a fixed point in $n$ different ways.]

n: k:

Joshua Horowitz (December 2014)