How to count equivalence classes

[Swammerdami]

Imagine a rotatable square, with each corner colored black or white. (Make it a "lazy susan" with four places for a food dish atop a dining table if you wish.) Partial rotations are outlawed; the square can be rotated only by exactly 90°, 180°, 270°, or 360°.

Rather than making little square graphics, we'll just list the four corners in the order (north, east, south, west) or (n,e,s,w).

This structure is called a permutation group. The group has four elements; each element is a permutation that can be denoted by its cycle structure:

• ((e)(s)(w)) — identity — x₁·x₁·x₁·x₁
• ((nesw)) — 90° clockwise rotation — x₄
• ((ns)(ew)) — 180° rotation — x₂·x₂
• ((nwse)) — 90° counter-clockwise rotation — x₄

I've shown the cyclic structure of each permutation: we will get to these later. x₁ denotes a singleton-cycle, and x₁·x₁·x₁·x₁ denotes four singletons. This can also be written x₁⁴, but sometimes the old-fashioned form is more convenient.

So how many ways are there to color the four corners black or white? 2⁴ = 16 is the obvious answer but we don't want to count two colorings as distinct if they one can be changed to the other by one of our four permutations. Here are the different ways to color the corners, shown in (n,e,s,w) order:

• BBBB
• WBBB : BWBB BBWB BBBW
• WWBB : BWWB BBWW WBBW
• BWBW: WBWB
• BWWW : WBWW WWBW WWWB
• WWWW

This list shows 16 colorings, but only 6 of them are distinct. The colorings have been partitioned into equivalence classes.


So ... We've shown how many distinct ways there are to 2-color the 4 corners of a rotating square, but we did it with manual inspection. If we are asked how many ways to 3-color the 8 corners of a rotating cube, we would NOT want to try a manual enumeration! This thread will discuss how to do such an enumeration automatically. We'll start by working this toy example, the rotating square.

By summing the cycle structures of the four permutations, we first form the cyclic index polynomial:
. . . . Z = (x₁⁴ + x₂² + 2·x₄¹) / 4
(We divide by 4, the total number of elements in the permutation group. In a sense, Z is the average cycle structure! )

The 'x_k' are formal variables; we can play with them in various ways! For example
. . . . x_k = B^k + W^k
With these substitutions, and some routine algebraic manipulations Z = (x₁⁴ + x₂² + 2·x₄¹) / 4 becomes
. . . . Z = (BBBB + BWWW + 2·BBWW + WBBB + WWWW)
And indeed this is precisely the list of equivalence classes we found above. (BWBW has been replaced with BBWW, but the commutative law of multiplication is too nice to pass up!)

Let's try a simpler substitution for our variables, but now with 3 colors instead of 2.
. . . . x_k = 3
Do the work; I think you'll find
. . . . Z = Z₃ = (9 + 6 + 81) / 4 = 24
Let's double-check this result. Are there exactly 24 ways to color with the 3 colors B, W, G?
BBBB times 3 colors; GBBB times 6 ordered color-pairs; BBGG and BGBG each times 3 unordered color-pairs; BBRG and BBGR and BRBG each times 3 colors. Yes, that totals 24!

I'll write a little more on this topic if nobody beats me to it! I confess it may have been decades since I last felt an urgent need or desire to count equivalence classes this way, but I was reminded of this fun method by the thread on counting groups.

 

[Swammerdami]

Before leaving the simple 4-point example, let's consider the case where we're allowed to turn the square upside-down, or reflect it in a mirror. We now have 8 legal permutations. The four new ones can be derived by applying the permutation ((ns)(e)(w)) to each of the original four. Here they are:

• ((e)(s)(w)) --> ((ns)(e)(w)) — flip along horizontal axis — x₂·x₁²
• ((nesw)) --> ((nw)(se)) — flip along diagonal — x₂²
• ((ns)(ew)) --> ((s)(ew)) — flip along vertical axis — x₂·x₁²
• ((nwse)) --> ((ne)(sw)) — flip along diagonal — x₂²

These four new permutations' cycle structures sum to:
. . . . (2·x₂² + 2·x₂·x₁²)
Referring to the 4-sized permutation group's polynomial, the rotate/reflect cyclic index polynomial becomes
. . . . Z = (x₁⁴ + 3·x₂² + 2·x₂·x₁² + 2·x₄¹) / 8
We could substitute x_k = R^k + G^k + B^k + W^k to find the color populations of all distinct 4-colorings ... but let's do something much less cumbersome.
Let's substitute x_k = m just to find the number of distinct m-colorings.
Z = (m^4 + 2m^3 + 3m^2 + 2m) / 8
Z_m=1 = 1
Z_m=2 = 6
Z_m=3 = 21
Z_m=4 = 55
Z_m=5 = 120
Churning these out is effortless once we have the cyclic index polynomial.

Z_m=2 = 6 is the same number we saw in post #1, but what about Z_m=3 = 21. Wasn't that number 24 before? Yes, but now we allow reflections. RRGB is the same as RRBG when reflections are allowed, and similarly for BBRG/BBGR and GGRB/GGBR.

Next up: The 48 rotation/reflections of a cube?

 

[lpetrich]

There is a nice bit of group theory that one can use here, the "orbit-stabilizer theorem".

(Number of distinct configurations) = (size of group) / (number of group elements that preserve each configuration)

Looking at a square, its rotation group I call C4 and its rotation-reflection group I call D4. For vertices 1,2,3,4:

Rotations: identity (0d) 1234, R90d 2341, R180d 3412, R270d 4123, reflections: (axial) S12-34 2143, S14-23 4321, (diagonal) S1-3, 1432, S2-4 3214

Vertex markings / colorings: 1111. All of both groups, one config.

1112 -- id, S1-3. Configs: 4

1122 - id, S12-34. Configs: 4

1212 - id, R180d, S1-3, S2-4. Configs: 2

1123 - id. Configs: 4 / 8

1213 - id, S2-4. Configs: 4

1234 - id. Configs: 4 / 8

With two numbers of configurations, the first is for pure rotations and the second for reflections also. The second one includes mirror images.

 

[lpetrich]

One can do a similar analysis for triangles. For them, the elements are id 123, R120d 231, R240d 312, S1-23 132, S2-13 321, S3-12 213

Rotation: C3, with reflection D3

111 - entire groups. Configs: 1

112 - id, S3-12. Configs: 3

123 - id. Configs: 3 / 6

I tried doing that for pentagons and hexagons, and I ended up writing a short Mathematica program for doing so:

sortconfigs[baseconfig_,symmgen_] := Module[{configs,symmconfigs={},smcfg},
configs = Permutations[baseconfig];
While[Length[configs]>0,
smcfg = symmgen[First[configs]];
AppendTo[symmconfigs,smcfg];
configs = Complement[configs,smcfg]
];
symmconfigs
]

(* Rotation group *)
rotgrp[xlst_] := Union[Table[RotateLeft[xlst,k],{k,0,Length[xlst]-1}]]

(* Rotation and reflection group *)
rrgrp[xlst_] := Union[rotgrp[xlst],rotgrp[Reverse[xlst]]]

(* Partial rotation group - first arg is its rotation stepping *)
prtrotgrp[n_,xlst_] := Union[Table[RotateLeft[xlst,n*k],{k,0,Length[xlst]/n-1}]] /; Divisible[Length[xlst],n]

(* Partial rot-rfl group - first arg is its rotation stepping *)
prtrrgrp[n_,xlst_] := Union[prtrotgrp[n,xlst],prtrotgrp[n,Reverse[xlst]]]

It would be easy to translate this into Python or C++ or whatever.

 

[Swammerdami]

Yes, as Ipetrich points out the Cauchy-Frobenius Orbit-Counting Theorem (also known as  Burnside's Lemma) underlies this method. But you'll get most Google hits on  Pólya enumeration theorem.

Here is the cyclic index polynomial, Z₂₄, for the vertices of a rotating cube; and Z₄₈ for the same vertices when reflections are also permitted.

Z₂₄ = (x₁⁸ + 6·x₄² + 9·x₂⁴ + 8·x₁²·x₃²) / 24
Z₄₈ = (x₁⁸ + 8·x₁²·x₃² + 6·x₁⁴·x₂² + 13·x₂⁴ + 8·x₆¹·x₂ + 12·x₄²) / 48

As shown in a previous post, the simplest application of this formula is to set all x_j = w:
Z₂₄ = (w⁸ + 17·w⁴ + 6·w²) / 24
Z₄₈ = (w⁸ + 6·w⁶ + 21·w⁴ + 20·w²) / 48

If I've made no error, the numbers of distinct ways to color a cube's vertices with w colors are now seen to be
w=1) 1 / 1
w=2) 23 / 22
w=3) 333 / 267
w=4) 2916 / 1996
w=5) 16725 / 10375
w=6) 70911 / 41406
w=7) 241913 / 135877
w=8) 701968 / 384112
w=9) 1798281 / 966141
w=10) 4173775 / 2212750
The second number is for the case where mirror-images are considered equivalent.

The hardest part of the whole process is to find the cycle structures of the permutation graph. Ipetrich provided source code to do that. I have my own C program for this, but it would NOT be a pleasure to behold!

 

[lpetrich]

A cube is rather complicated, but here are some constructions of its parts and symmetry groups:

• Octahedron vertices = cube faces = tetrahedron edges = permutations of {+-1,0,0} -- 6
• Octahedron edges = cube edges = permutations of {+-1,+-1,0} -- 12
• Octahedron faces = cube vertices = {+-1,+-1,+-1} -- 8
• Tetrahedron vertices = (oct fcs) with product = +1 -- 4
• Tetrahedron faces = (oct fcs) with product = -1 -- 4

Their symmetry groups one can construct with:

• Octahedral reflection = (permutations of the identity matrix). (diagonal matrices with +-1's) -- 48
• Octahedral = (oct rfl) with det(mat) = 1 for matrices mat in the group -- 24
• Tetrahedral flipped = (oct rfl) with det(abs(mat)) = 1 -- 24
• Tetrahedral reflection = (oct rfl) with det(abs(mat))*det(mat) = 1 -- 24
• Tetrahedral = (oct rfl) with det(mat) = 1 and det(abs(mat)) = 1 -- 12

One can also construct matrices for the icosahedral symmetry group, but that one is more complicated. Doing so will also give the positions of icosahedron and dodecahedron vertices, edges, and faces.

To give a hint as to how to do that, one uses the quaternion representation of 3D rotation groups. A quaternion is a 4-vector with a certain multiplication law, and one can find a rotation matrix by taking a sort of square of a unit quaternion. Quaternions also have a nice relationship with Pauli matrices.

The quaternions for the tetrahedral group: permutations of (+-1,0,0,0) and (1/2)*(+-1,+-1,+-1,+-1). For the octahedral group, one adds permutations of (1/sqrt(2))*(+-1,+-1,0,0)

For the icosahedral group, its quaternions are formed by adding to the tetrahedral group the even permutations of (+-(sqrt(5)+1)/4, +-1/2, +-(sqrt(5)-1)/4, 0)

 

[lpetrich]

For rotations and reflections in n dimensions, the group of them is O - the orthogonal group. For pure rotations, the group of them is SO - the special orthogonal group. The rotation matrices D have properties D.tp(D) = tp(D).D = 1 where tp is the transpose, (rows) <-> (columns). Its determinant det(D) is 1 or -1, and is only 1 for SO.

Rotation-reflection multiplication table:

	rot	rfl
rot	rot	rfl
rfl	rfl	rot

This means that in a rotation-reflection group, there are the same number of reflections as rotations.

It's evident that r-r groups are semidirect products of Z2 and pure-rotation groups. The Z2 is for rotations and reflections combined as single elements.

In some cases, r-r groups are direct products. For instance, O(2n+1) = {I,-I} * SO(2n+1) -- something not true for O(2n) and SO(2n). This is because -I is a member of SO(2n+1) but not SO(2n), because its determinant is (-1)^n.

-

The 1D groups are SO(1) = {1}, O(1) = {1,-1} simplifying matrix {{a}} into a.

-

The 2D matrices are:

• Rotation: R(a) = {{cos(a), -sin(a)}, {sin(a), cos(a)}}
• Reflection: S(a) = {{cos(a), sin(a)}, {sin(a), -cos(a)}}

S is from German Spiegel, "mirror".

with multiplication table

• R(a).R(b) = R(a+b)
• R(a).S(b) = S(a+b)
• S(a).R(b) = S(a-b)
• S(a).S(b) = R(a-b)

There are two infinite families of 2D r-r groups, the cyclic or pure-rotation ones, C, and the dihedral or r-r ones, D.

The elements of C are R(2pi*k/n) for k = 0 to (n-1) and the elements of D are those of C and S(a0+2pi*k/n) for k = 0 to (n-1) for some a0.

 

[lpetrich]

Number of finite groups:

• 1D: 2
• 2D; 2 infinite families: cyclic and dihedral
• 3D: 7 infinite families: axial, and 7 extra ones: quasi-spherical
• More than 3 dimensions: much more complicated

"Axial" and "quasi-spherical" are my names; I've seen "prismatic" for the axial ones.

The axial-group elements are

• RR(a) = {{cos(a), -sin(a), 0}, {sin(a), cos(a), 0}, {0, 0, 1}}
• RS(a) = {{cos(a), -sin(a), 0}, {sin(a), cos(a), 0}, {0, 0, -1}}
• SR(a) = {{cos(a), sin(a), 0}, {sin(a), -cos(a), 0}, {0, 0, 1}}
• SS(a) = {{cos(a), sin(a), 0}, {sin(a), -cos(a), 0}, {0, 0, -1}}

They form 5 infinite axial groups: {RR}, {RR, RS}, {RR, SR}, {RR, SS}, and {RR, RS, SR, SS}.

The 2 infinite quasi-spherical groups are SO(3) and O(3) = {I,-I} * SO(3).

Here is a simplified way of writing the elements of 2D groups C and D: {R(all)} and {R(all), S(all)}. I will apply that to the 7 families of 3D axial groups:

• C -- {RR(all)} -- abstract group Z
• C(n,h) -- {RR(all), RS(all)} -- abstract group Z2*Z
• S(2n) -- {RR(even), RS(odd)} -- abstract group Z(2n)
• C(n,v) -- {RR(all), SR(all)} -- abstract group Dih
• D -- {RR(all), SS(all)} -- abstract group Dih
• D(n,h) -- {RR(all), SR(all), RS(all), SS(all)} -- abstract group Z2*Dih
• D(n,d) -- {RR(even), SR(even), RS(odd), SS(odd)} -- abstract group Dih(2n)

I've used Schoenflies's notation. I think that S(2n) ought to be C(n,s) or C(n,d). The abstract groups for the 2D case are C: Z and D: Dih.

 

[lpetrich]

The seven quasi-spherical groups are

• T - tetrahedral rotation -- abstract group Alt(4)
• Th - tetrahedral r+i -- abstract group Z2*Alt(4)
• Td - tetrahedral r+r -- abstract group Sym(4)
• O - octahedral rotation -- abstract group Sym(4)
• Oh - octahedral r+r -- abstract group Z2*Sym(4)
• I -icoshedral rotation -- abstract group Alt(5)
• Ih - icosahedral r+r -- abstract group Z2*Alt(5)

In the octahedron (cube) and the icosahedron (dodecahedron), all the reflections are inversion * rotations

The tetrahedral case is different. The group Th has rotations + inversions, while Td has rotations + tetrahedron-preserving reflections

Inversion: multiplication by -1.

Sym - all permutations of n symbols
Alt - all even permutations of n symbols (even/odd permutations = even/odd number of interchanges)

Cyclic permutations are even for odd length, odd for even length. So if a permutation has an odd number of even-length cycles, it is odd, otherwise, it is even.

 

[lpetrich]

Rotation matrices can be expressed in terms of quaternions, 4-vectors with a certain multiplication law.

Quaternion imaginary units i, j, k follow i² = j² = k² = i*j*k = -1. Distinct ones are anti-commutative.

u_i*u_j = δ_ij + (sum over k) ε_ijk*u_k

Breaking quaternions x down into scalar part x₀ and vector part x_v = {x₁, x₂, x₃}, we get for quaternion multiplication

(x*y)₀ = x₀*y₀ - x_v.y_v
(x*y)_i = x₀*y_v + x_v*y₀ + (x_v)x(y_v)
where the last terms are dot and cross products.

Quaternions are related to Pauli matrices: the scalar part multiplies the 2*2 identity matrix and u_i = - i * σ_i

Though quaternion multiplication is not commutative, it is associative. Quaternions also have an identity, scalar part = 1 and vector part = 0, a magnitude or absolute square, (scalar part)² + (vector part).(vector part), and an inverse, with the quaternion divided by its magnitude and with its vector part having reversed sign.

Quaternions also show up in rotation matrices:

R(q,x) = x + 2*q₀*((q_v)x(x)) + 2*((q_v)x(q_v)x(x)))

where the quaternion is a unit one, magnitude = 1.

 

[lpetrich]

Another way to find the parity of a permutation (even vs. odd) is to sort its members and count how many interchanges are necessary to get the identity permutation. One then returns whether that number was even or odd.

Back to quaternions, they can also be used to implement 4D rotations. One has to use pairs of them, each one with a different matrix parity, for lack of a better term:
R({q1,q2}) = R(q1,+1).R(q2,-1)

R(q,s) has form
R₀₀ = q₀
R_0i = - s * q_i
R_i0 = s * q_i
R_ij = δij*q₀ + (sum over k) εijk*q_k

R's of different parities commute.

The R that makes -I (minus identity): R({-1,0,0,0},s)

R(q1,+1).R(q2,-1) = R(-q1,+1).R(-q2,-1) -- reversing the signs of both quaternions makes the same value.
R(q1,+1).R(q2,-1) = R(q2,-1).R(q1,+1) -- opposite parities commute
R(q1,s).R(q2,s) = R(q1*q2,s) -- same parities combine with the quaternion multiplication law

Reflection can be done with diagonal({-1,1,1,1}) or diagonal({1,-1,-1,-1}). I will call it S0.

It flips the rotation parity: S0.R(q,s) = R(q,-s).S0

This gives 4D rotation groups a rather complicated structure.