Colourings nobody can tell apart

Colour the four corners of a square, each one filled or open. There are sixteen ways to do it, and the sixteen are easy to list. The harder question is how many of them are different, given that a square can be turned over and put back, and nobody looking at the result would know.

Six. And the six are not a tidy division of sixteen — the rows have sizes one, four, four, two, four and one, which add to sixteen without dividing it. That irregularity is the first sign that the counting here is not going to be arithmetic of the ordinary kind.

What the question is asking, exactly #

Before either count, the question needs to be pinned down, because two reasonable readings of it give different answers and the picture can only draw one.

The first reading: two colourings are the same when a motion of the square carries one to the other. That is the reading here, and it is the reading in which the square is a physical thing that can be lifted and turned over.

The second reading: two colourings are the same when a rotation carries one to the other — the square stays flat on the table and is never picked up. That is a different question with, in general, a different answer, and the difference is the whole subject of a later section.

A third reading is available and is not used: two colourings are the same when they use the same number of filled corners. That one is not a symmetry question at all; it discards information the square has not been asked to discard, and it happens to give five rather than six, since it merges the adjacent pair with the opposite pair. It is included here as the reminder that a class is only ever as meaningful as the relation that built it.

The pooling, done directly #

The direct method is exactly what the picture shows. Take a colouring. Apply all eight motions of the square to it, collecting whatever comes back. That collection is the colouring’s class — everything the square cannot distinguish it from. Cross the whole class off the list, take the next uncrossed colouring, repeat.

That is a finite procedure and it terminates, and the figure runs it. It also checks the two things a reader would otherwise have to take on trust: that the classes between them account for all sixteen colourings, and that no colouring appears in two classes. Both are consequences of the fact that “some motion carries one to the other” is an equivalence — reflexive because doing nothing is a motion, symmetric because every motion is undoable, transitive because motions compose — and all three of those properties are exactly what the composition table established.

The class sizes are worth looking at before moving on. One, four, four, two, four, one. Every one of them divides eight. That is not an accident and it is not a coincidence about squares: a class has size equal to the number of motions, divided by the number of motions that leave the colouring alone. The all-filled colouring is left alone by all eight, so its class has one member. A colouring with one filled corner is left alone only by the flip through that corner and by doing nothing — two motions — so its class has four.

Why the direct method stops working #

The pooling is honest and it does not scale. Colouring the corners of a square in three colours gives eighty-one arrangements; in four colours, two hundred and fifty-six. A twelve-bead necklace in three colours has half a million. The pooling has to touch every one of them, and the answer it is heading for — the number of classes — is a small number obtained by an enormous amount of bookkeeping.

Worse, the bookkeeping is the wrong shape. To pool, the classes have to be built; to count, only their number is wanted. Anything that builds the classes is doing work whose output is thrown away.

So the question is whether the number of classes can be reached without ever forming one. It can, and the method is strange enough to be worth stating before it is justified: instead of counting the classes, count how many colourings each motion leaves untouched, and take the average.

The average of the wrong-looking quantity #

Doing nothing fixes all sixteen colourings, because it changes nothing. A quarter turn fixes only the two colourings that are constant, since a corner and the corner it moves to must agree, and following that chain round forces every corner to agree with every other. A half turn fixes four: opposite corners must match, and the two pairs are free. A flip through a diagonal fixes eight: the two corners on the axis are free, and the other two must match. A flip through two edge midpoints fixes four: the corners pair up, two pairs, each free.

Add them: sixteen, two, four, two, and then eight, four, eight, four as the flips alternate between the two kinds of axis. Forty-eight. Divide by the eight motions: six.

Six is the number the pooling found. The two computations share no step. One of them builds classes and never counts a fixed point; the other counts fixed points and never builds a class.

Why the average is the count #

The reason is a single change of perspective, and it is the best argument in the subject.

Consider all pairs consisting of a motion and a colouring that motion leaves untouched. This is one set of pairs, and it can be counted in two directions. Sorting by motion gives the column that was just added up: for each motion, the colourings it fixes. Sorting by colouring gives, for each colouring, the number of motions leaving it alone — which is precisely the number that, divided into eight, gives its class size.

So the total is the sum over colourings of eight divided by the class size. Group the colourings by class: a class of size k contributes k colourings, each with eight over k motions fixing it, for a total of eight per class. Every class contributes exactly eight, whatever its size. The grand total is therefore eight times the number of classes, and dividing by eight gives the count.

This is a counting-two-ways argument in its purest form: one collection, two orders of summation, and an identity because both answers describe the same set of pairs. It is the same move that makes the necklace proof of Fermat’s little theorem work and the same move behind counting one rectangle twice in the reciprocity essay.

The coincidence at two colours, and what breaks it #

Here is a trap. Throw the reflections away and keep only the four rotations. Fewer motions means less pooling and so, one would expect, more classes. The count is six.

The same six. And it is a coincidence, in the precise sense that it does not survive one more colour.

With three colours the rotations alone give twenty-four classes and the full group gives twenty-one. Three colourings that the rotations keep apart are joined by a reflection. At two colours there happened to be none.

That is exactly the situation the theme small cases lie exists for. Two colours is the case anyone checks first, it is the case that fits on one page, and it is the case where the distinction between the rotation group and the full symmetry group is invisible. Anyone who inferred from it that flips do not matter would be wrong at the very next value, and would have no way of knowing from the picture in front of them.

The cost of each method, counted #

It is worth being explicit about what the second method actually saves, because “avoid building the classes” sounds like tidiness rather than an argument.

Pooling costs one pass over every colouring, and for each colouring one application of every motion: the number of colourings times the size of the group. Averaging costs one pass over every motion, and for each of those, a look at its cycle structure — which does not depend on the number of colourings at all. For the square in two colours that is sixteen times eight against eight; for a necklace of twenty beads in three colours it is three and a half thousand million against forty.

The saving is not a constant factor. It is the difference between a cost that grows with the objects and a cost that grows with the symmetries, and the symmetries are almost always the smaller collection. A necklace of a thousand beads has two thousand symmetries and more colourings than there are atoms anywhere.

There is one honest caveat, and this site’s figure standard is the reason to state it: the averaging figure on this page does not take that saving. It recomputes each fixed set by brute force, precisely so that the cycle formula is checked against a count made without it. A figure that used the cheap method to draw a picture of the cheap method would be asserting the very thing it exists to demonstrate.

Where the same count has been made before #

The necklace argument for Fermat’s little theorem is this counting, done on a ring of beads with a prime number of positions, and the theorem falls out of a detail that looks minor here. When the number of positions is prime, a rotation class has either one member or exactly that prime number, because the class size divides the prime and there is nothing in between. Subtract the constant strings and the rest divides exactly.

Squares do not have that property, because four is not prime, and the class sizes one, two and four are the evidence. This is a case where the general machinery and the special result diverge helpfully: the averaging argument works for every group and every set it acts on, while the theorem needs the sizes to be forced, which needs a prime.

Three corners and three colours #

The triangle is small enough that the whole picture fits and large enough that the class sizes are varied. Three colourings are constant and are fixed by everything, so they are alone in their classes. Six classes have three members each: these are the colourings using exactly two colours, where one corner differs from the other two and the flip through that corner is the one motion that leaves the arrangement alone. The class of six is the one where all three corners have different colours — six arrangements, all reachable from one another, and none of them fixed by anything but doing nothing. Three, eighteen and six add to twenty-seven, and one, six and one add to ten.

The averaging gives the same ten: doing nothing fixes twenty-seven, each of the two turns fixes three, each of the three flips fixes nine. Twenty-seven plus three plus three plus nine plus nine plus nine is sixty, and sixty over six is ten.

Worth noticing: the fixed count for a motion is always the number of colours raised to the number of cycles the motion makes among the corners. A flip of the triangle fixes one corner and swaps two: two cycles, so nine. A quarter turn of the square puts all four corners in a single cycle: one cycle, so however many colours there are, only that many colourings survive. The whole computation reduces to reading cycle structure off a permutation, which is why it costs so little.

What the picture cannot show #

The figures draw the classes for small squares and small triangles, and the honest limit is exactly there: every count on this page was obtained by a method whose cost grows with the number of colourings, even the averaging one, because the averaging figure recomputes the fixed sets by brute force in order to check the cycle formula against something independent.

The formula does not need that. Once the cycle structure of each motion is known, the count is a sum of a handful of powers, and it is as cheap for a necklace of thirty beads in seven colours as for a square in two. No picture on this site draws that case, and the reason is not modesty about the arithmetic — the number is about ten to the twenty-third — but that a class of that size cannot be shown, only reported.

There is a second limit worth naming. The classes here answer how many, and they do not answer which. Knowing that a twelve-bead necklace in three colours has twenty-two thousand and some classes is a different kind of knowledge from being able to name one, or to say whether two given necklaces are the same. The averaging method is silent on both.

Where the ladder goes next #

Two directions lead out of here, and both are already on the site.

Counting objects up to a symmetry is what makes enumerating the regular solids a finite job, and what makes the thirty-six officers a search over a manageable space rather than an impossible one. Wherever an exhaustive search on this site reports a number in the hundreds rather than the millions, some quotient by a symmetry group has been taken, usually silently.

There is also a direction that leads out of counting altogether. The classes on this page are being counted, but they are also being named — the row with two filled corners adjacent is a thing, distinct from the row with them opposite, and the naming is what a reader takes away. In larger cases the naming problem separates from the counting problem completely: the four-colour theorem is settled by a computer that never enumerates maps up to symmetry but does have to decide, thousands of times, whether two configurations are the same one drawn differently. That decision is the hard half, and averaging says nothing about it.

The other direction is towards what the group is, independently of the square it came from. The eight motions have a composition table; so do the six motions of a triangle; so do the rotations of a clock. Two groups with the same table are the same group, and classifying groups by their tables rather than by the shapes they came from is where the subject stops being about shapes at all. That is the rung this ladder has not yet built, and it will need a different kind of figure than a page of coloured corners.