Counting Distinct Colourings
Counting distinct colourings of physical objects with symmetries
Combinatorics is the art of counting without counting it is the ability to do very complicated calculations involving integers in very clever ways making it unnecessary to actual physical “enumeration” by computer algorithm methods or physically. We speak of discrete mathematics.
Two AbcTales stories are planned for submission, the one more on the mathematical theory and combinatorics and the other on harder examples and of my own invention too.
As far as the mathematical theory goes for now I will only very briefly discuss some relevant ideas and definitions with relatively simple examples. The reader will have to make sketches, small physical models are even better, like a matchbox or square block or a little cardboard pyramid.
We will now be describing actual possible physical objects.
Permutations are different arrangements of k objects (without repetition) for example there are
3! = 3.2.1 = 6 permutations of three different digits, they are
1 2 3 1 3 2 // 2 1 3 2 3 1 // 3 2 1 3 1 2
Or number plates without repeated digits, the first place can be chosen one of 4 different digits, that leaves 3 to choose for the 2nd place and the 4th place just the 1 remaining. That gives 4.3.2.1 = 24 possible distinct plates.
There are k! = k(k-1)(k-2) … 2.1 permutations of k objects.
-
To understand the ideas and explain the concepts of symmetry, rotations and reflections I give examples. If a solid physical object has a symmetry it means one position can be obtained identically from another.
A rectangle has three axis' of symmetry (through the centre), 1 rotation and the lines joining opposite midpoints give two reflections.
Think of an equal sided triangle. It gives thus rise to a symmetry axis a line from a corner halving the opposite side. There are 1 rotation and 3 reflection axis', giving rise to my example on permutations.
A solid cube (block) has 10 symmetry axis' through it's centre, as rotations the 3 lines joining midpoints of opposing faces, and symmetries as reflections in the 4 lines through opposing edges and 4 through the opposing corners.
-
Following are simple colourings of objects as actual possible applications.
As a simple example a 2D rectangle divided on one side in two squares can be painted 3 ways (on top) with white and black as, both squares white, both black or one black one white. There are 3 orbits, or three distinct such figures.
When one physical object can be obtained from another as identical by simple rotations and reflections it is invariant it is called an equivalence class or an orbit, given as one same distinct object depending on symmetries.
These “equivalence classes” represent invariance of the object under rotation or reflection.
-
As an example consider a tile or matchbox (rectangular3D) which is divided in half through the breadth into 2 rectangles top and bottom, giving 4. The rectangles are each coloured in either white or black.
With four white rectangles there is only one such box, if there is one black rectangle and the other 3 still white, also only one such box, the same goes for black, so that gives you four different colourings.
2 rectangles black and 2 white is tricky, but there are 3 physically different boxes like this. That gives you 2 + 2 + 3 = 7 boxes altogether.
-
As other typical applications in making table seating arrangements how many ways can 8 people be assigned seating around a table? With an assigned head, as all the permutations there are 8! or 40320 different arrangements.
With 8 seats and not given an designated head? In other words there are repetitions identical under 8 rotations, in all there are 1/8 .8! = 7! = 5040 seating possibilities.
-
Counting necklaces with beads each of different colours how many distinguishable necklaces would there be?
An open neckless (as a string) such as with 6 different coloured beads has 6! = 720 possibilities.
The closed necklace (without clasp) with 6 beads can be strung in 1/6 .6! = 5! = 120 ways when including rotations, but each can be flipped too as a reflection so there is a total of 1/2 .120 = 60
-
A die is a child's block or cube with six markings of 1, 2, or 3 … 5, 6 dots each on a face called colours. A position of the block can be achieved from any other by rotations of the whole die.
There are 6x4 = 24 possible positions for a given fixed cube on the table as such without considering colours, firstly facing down in 6 ways. The side facing front can be one of the remaining 4, leaving the other five sides fixed.
With 6 colours the total permutations must be 6.5.4.3.2.1 = 6! = 720
The problem is calculating the total number of distinct dice. For this problem we know we know there are 30 = 720/24 such distinct different dice. Of course this must hold for a colouring too, i.e. a pristine Rubik's cube there in fact are thus 30 (as different cubes!)
Such colourings of all the convex regular polyhedra may be calculated thus, i.e. tetrahedron, octahedron dodecahedron and icosahedron.
-
As a last application we just formulate the question. As a more sophisticated problem find the number of distinguishable ways the edges of an equilateral triangle can be painted if 4 different colours are available assuming only one colour is used on a single edge, and the same colour can be used on different edges.
This is a bit more complicated problem. You would need more sophisticated mathematics, such as Burnside's Lemma. There are 20 but I think it would be hard doing this by direct enumeration.
However the same problem but with the assumption that a different colour is used on each edge is very easy, there are four ways to colour the edges it's not hard to see.
-
In the AbcTales stories Polya's Theorem will be formulated as an incredibly powerful tool and on counting colourings under symmetries.
Theoretically one might be able to do these calculations with a computer program in a brute force fashion as in physical counting but to write such a program might get very complicated and as the problem gets bigger quickly becoming unmanageable.
Compared to the sophisticated methods described involving very little actual computation however physical counting could be of value to confirm the results.
In an actual AbcTales “story” I will provide theory as the necessary definitions an results but without proofs this is advanced work in Abstract Algebra. If someone is interested they could do some reading on permutation groups, G-sets, counting orbits and Burnside's Lemma.
These were standard examples I will present some of my own ideas later in the stories.