Page 1 of 2 12 LastLast
Results 1 to 10 of 11

Thread: How to count equivalence classes

  1. Top | #1
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,742
    Rep Power
    17

    How to count equivalence classes

    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:
    • ((n)(e)(s)(w)) — identity — x1·x1·x1·x1
    • ((nesw)) — 90° clockwise rotation — x4
    • ((ns)(ew)) — 180° rotation — x2·x2
    • ((nwse)) — 90° counter-clockwise rotation — x4


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

    So how many ways are there to color the four corners black or white? 24 = 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 = (x14 + x22 + 2·x41) / 4
    (We divide by 4, the total number of elements in the permutation group. In a sense, Z is the average cycle structure! )

    The 'xk' are formal variables; we can play with them in various ways! For example
    . . . . xk = Bk + Wk
    With these substitutions, and some routine algebraic manipulations Z = (x14 + x22 + 2·x41) / 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.
    . . . . xk = 3
    Do the work; I think you'll find
    . . . . Z = Z3 = (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.

  2. Top | #2
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,742
    Rep Power
    17
    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:
    • ((n)(e)(s)(w)) --> ((ns)(e)(w)) — flip along horizontal axis — x2·x12
    • ((nesw)) --> ((nw)(se)) — flip along diagonal — x22
    • ((ns)(ew)) --> ((n)(s)(ew)) — flip along vertical axis — x2·x12
    • ((nwse)) --> ((ne)(sw)) — flip along diagonal — x22

    These four new permutations' cycle structures sum to:
    . . . . (2·x22 + 2·x2·x12)
    Referring to the 4-sized permutation group's polynomial, the rotate/reflect cyclic index polynomial becomes
    . . . . Z = (x14 + 3·x22 + 2·x2·x12 + 2·x41) / 8
    We could substitute xk = 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 xk = m just to find the number of distinct m-colorings.
    Z = (m^4 + 2m^3 + 3m^2 + 2m) / 8
    Zm=1 = 1
    Zm=2 = 6
    Zm=3 = 21
    Zm=4 = 55
    Zm=5 = 120
    Churning these out is effortless once we have the cyclic index polynomial.

    Zm=2 = 6 is the same number we saw in post #1, but what about Zm=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?

  3. Top | #3
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    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.

  4. Top | #4
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    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:
    Code:
    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.

  5. Top | #5
    Squadron Leader
    Join Date
    Dec 2017
    Location
    Land of Smiles
    Posts
    1,742
    Rep Power
    17
    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, Z24, for the vertices of a rotating cube; and Z48 for the same vertices when reflections are also permitted.

    Z24 = (x18 + 6·x42 + 9·x24 + 8·x12·x32) / 24
    Z48 = (x18 + 8·x12·x32 + 6·x14·x22 + 13·x24 + 8·x61·x2 + 12·x42) / 48

    As shown in a previous post, the simplest application of this formula is to set all xj = w:
    Z24 = (w8 + 17·w4 + 6·w2) / 24
    Z48 = (w8 + 6·w6 + 21·w4 + 20·w2) / 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!

  6. Top | #6
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    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)

  7. Top | #7
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    For rotations and reflections in n dimensions, the group of them is O(n) - the orthogonal group. For pure rotations, the group of them is SO(n) - 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(n).

    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(n), and the dihedral or r-r ones, D(n).

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

  8. Top | #8
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    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(n) and D(n): {R(all)} and {R(all), S(all)}. I will apply that to the 7 families of 3D axial groups:
    • C(n) -- {RR(all)} -- abstract group Z(n)
    • C(n,h) -- {RR(all), RS(all)} -- abstract group Z2*Z(n)
    • S(2n) -- {RR(even), RS(odd)} -- abstract group Z(2n)
    • C(n,v) -- {RR(all), SR(all)} -- abstract group Dih(n)
    • D(n) -- {RR(all), SS(all)} -- abstract group Dih(n)
    • D(n,h) -- {RR(all), SR(all), RS(all), SS(all)} -- abstract group Z2*Dih(n)
    • 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(n): Z(n) and D(n): Dih(n).

  9. Top | #9
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    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(n) - all permutations of n symbols
    Alt(n) - 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.

  10. Top | #10
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Rotation matrices can be expressed in terms of quaternions, 4-vectors with a certain multiplication law.

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

    ui*uj = δij + (sum over k) εijk*uk

    Breaking quaternions x down into scalar part x0 and vector part xv = {x1, x2, x3}, we get for quaternion multiplication

    (x*y)0 = x0*y0 - xv.yv
    (x*y)i = x0*yv + xv*y0 + (xv)x(yv)
    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 ui = - 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)2 + (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*q0*((qv)x(x)) + 2*((qv)x(qv)x(x)))

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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •