# Message #2128

From: David Vanderschel <DvdS@Austin.RR.com>

Subject: Re: [MC4D] Calculating the number of permutation of 2by2by2by2by2 (2^5)

Date: Wed, 09 May 2012 23:11:14 -0500

Melinda wrote:

>On 5/7/2012 6:34 PM, David Vanderschel wrote:

>>Melinda wrote:

>>>It sounds like we are getting closer to closure.

>>>>Does this mean that you now understand why you must

>>>>maintain the pairs of opposing colors when reassigning

>>>>sticker colors? With all my effort at trying to explain

>>>>it for you, I was hoping for an "I see now!" I was also

>>>>hoping that you would realize that it is easier to talk

>>>>about conjugation by a symmetry than to get involved in

>>>>talking about remapping sticker colors, which are

>>>>actually somewhat tangential to the real problem.

>I’m not sure that I feel much closer to that "ah ha" moment

>but I do feel as if we are converging on a story that will

>feel right for all of us.

Unfortunately, I can tell from your later questions that you

have yet to get it.

>If conjugation is the operation that allows us to compose

>all the symmetries into one state space, then it does feel

>like a useful way to describe what we are doing.

I don’t think there is any "if" to it. However, I am not

sure that I can interpret your "compose all the symmetries

into one state space" meaningfully. In particular, we are

not composing symmetries. Without reducing to the

equivalence classes of states related by conjugation by a

symmetry, we have a perfectly meaningful state space; and I

don’t really understand why you are fighting it. Why do you

suppose Dan Hoey titled his article "The _real_ size of cube

space"? It is because the approach of regarding states as

distinct just by sticker color arrangement was already well

established even back in ‘94. He was "injecting the

complication" of grouping those states which were related by

conjugation by a symmetry, and he realized that that was not

the accepted approach. His observation became relevant to

those who were actually trying to analyze relationships

between _particular_ states for the conventional 3D puzzle

because the reduction actually brought the problem into a

range that was computationally feasible. When we are just

interested in counting distinct states, that is not our

issue. You get just as good a sense of how many states

there are without the much more complex additional reduction

by a factor somewhat less than n!*2^n.

I think the important thing about the distinction is that,

when we reduce to equivalence classes of the (first pass)

distinct states with the conjugation approach, we are

focusing more on the nature of the _process_ (aka permutation)

which gives rise to a state rather than to the state itself.

The result of that process depends on the initial

orientation of the pile.

>>> The main MC4D page claims to give the exact counts for

>>> the 3D and 4D puzzles. Is that not true? If not, then I

>>> need to change it.

>>>>It is true. Also the counts that David Smith came up

>>>>with for 5D are intended to be exact. (I am not ruling

>>>>out the possibility of an error.) As I said, the

>>>>problem that Eric and David were solving is much more

>>>>straightforward and admits a precise answer. The

>>>>problem only arises when you start trying to get the

>>>>number of equivalence classes of the distinct states

>>>>they counted that are related through conjugation by a

>>>>symmetry, which is the complication that it would seem

>>>>you were trying to inject. That would result in a

>>>>reduction of Eric’s and David’s numbers by a factor

>>>>close to (but less than) n!*2^n. But it is not

>>>>practical to do that in an exact sense.

>I am not trying to inject a complication, rather I am trying

>to account for what appears to be an error in our claim. I

>certainly don’t want to count two states as unique when they

>share all the same properties other than handedness. I

>understand that attempting to account for this one rare

>symmetry won’t change the state count by much and that maybe

>it is currently impractical to attempt to do that.

Melinda, it is not an error! The configurations are truly

different in the sense that no amount of reorientation will

cause a matchup of sticker colors all around. There is no

unavoidable reason to want to regard the assignment of

sticker colors as being mutable.

>This may be covered in previous messages, but would you

>please explain how you derive the n!*2^n and why it is not

>(n-1)! as I had thought?

Melinda, I am losing patience on this one. Brandon tried to

explain it in his recent post. Nan mentioned it in that old

one I cited. It comes down to the fact that many of the

remappings of sticker colors you are proposing are just not

physical - the puzzles can’t do that! In particular, the

two sticker colors that are on the same axis in initial

state must always be on the same axis no matter how you

otherwise remap the stickers. Thus what is really possible

for remapping colors comes down to a permutation of the axes

and possible swapping of the two colors on an axis. E.g.,

on a standard Rubik’s cube, yellow/white and blue/green are

so paired. Thus you could not swap yellow with blue unless

you also swapped white and green. You could also swap just

blue and green. The n in the formulae Roice and I were

tossing about is the dimension of the puzzle. So, with

that understanding, I thought you were saying (2n-1)!, where

2n is the number of sticker colors. (Not sure why you took

out one factor of 2n. I guess you were thinking of one

color as being a reference with respect to which the others

were being permuted.)

I will make one more brief attempt at the end; but you

should really try to reread earlier postings in this thread

more carefully. It has been explained.

>>You have already worked out a simple example giving

>>representative members of the equivalence classes for the

>>case of the 2D puzzle with mirroring twists allowed. I

>>would hope you would remember the previous occasion on which

>>some folks on the list tried to explain the relationship of

>>your equivalence classes to conjugation by a symmetry:

>>http://games.groups.yahoo.com/group/4D_Cubing/message/1843

>>Perhaps that previous discussion will make better sense to

>>you now.

>A little bit. Nan’s link to

>http://kociemba.org/math/symmetries.htm on that message is

>definitely what I am talking about. I think that the fact

>that MC2D appears to require reflections to operate at all

>probably confused the issue more than clarifying, because

>the real issue applies to all of our puzzles, not just to

>that one.

I don’t think that allowing mirroring twists makes any

difference at all with respect to the problems of

enumerating the distinct states or the equivalence classes

of these distinct states under conjugation by a symmetry.

>I definitely do not get the bit about how using axes and

>color pairs is better than thinking about color

>equivalencies but it is good enough if the result is the

>same.

It is important, because, if you fail to maintain the opposing

color pairs, then you do _not_ get the same result.

More generally, I regard the whole issue of remapping

colors as a red herring. If you understand conjugation

by a symmetry, then the recoloring is just an obvious side

effect which is not worth getting worked up about. It is

true; but it is not what is important. The actual colors

themselves were always unimportant. What you should

actually regard as identifying a sticker ‘color’ is the

direction it faces in initial state - not some particular

hue that is being used to render it for visualization

purposes.

>I am still a little troubled by the "exact" values that you

>guys seem to prefer. MC2D is indeed a great example of the

>problem and I just can’t see how we can really say that

>there are 24 states in that puzzle that I think David S

>claimed in Wikipedia. Looking at my state graph on the MC2D

>page there are clearly only 8 that make any real sense to

>me.

It is really quite simple. The state of this particular

puzzle is characterized solely by the permutation of the 4

corner cubies, and any permutation of the 4 cubies is

possible. Thus there are 4! different arrangements. This

is a perfectly legitimate way to count distinct states. You

have observed that lots of them are not essentially

different. E.g., you would regard as being essentially the

same any two states for which just two adjacent corners have

been transposed without regard to which pair that is. That

is an additional complication by which you are grouping the

states into equivalence classes; and, yes, the relation is

conjugation by a symmetry.

The relevant conjugator for the example is rotation by a

multiple of 90 degrees in the plane of the puzzle. So start

with "swap the top 2". Then, if I rotate a quarter turn

clockwise, swap the top 2, and rotate back, I will have

achieved "swap the left 2". Those two _different_

permutations of the cubies are related by conjugation by a

90 degree rotation. It really is a different pair of cubies

that get swapped in the two cases. It is perfectly

legitimate to regard the two states as being different

without worrying about their relationship by conjugation.

Melinda, whether you wish to recognize it or not, you really

are trying to unnecessarily complicate the problem of

counting distinct puzzle states. And, as may be seen from

the "real size" article, the complication is by no means

trivial.

Let me go back once more to a more complex puzzle and some

non-trivial twist sequence. Do that sequence starting with

the pile in initial state and you get one particular

arrangement. Now get another identical puzzle in initial

state, but, without twisting any slices, first reorient the

whole pile so that it is no longer in initial state. Now

perform the same twist sequence again. You get a new

arrangement which is not the same as the arrangement on the

first puzzle. You cannot (in general) make them match up

sticker-for-sticker just by reorienting one. However, your

sticker color remapping approach will make them match up

with appropriate relative orientations. But there is no

mystery about the required sticker remapping!: It is

precisely that which was induced by the initial

reorientation of the second puzzle before performing the

twist sequence. So there is no need to talk about it.

Furthermore, it is clear that a reorientation of the pile

cannot change which pairs of sticker colors occur facing in

opposite directions on the same axis. Other than that

restriction, lots of sticker color mappings are possible via

the orientation step preceding the twist sequence. Indeed,

that number is n!*2^n.

Mirroring transforms for the conjugator are perfectly

legitimate even if they are not allowed for the puzzle,

because the conjugate will not induce any mirroring if none

of the twists do. (Indeed, you can actually practice

conjugation by a reflection on a 3D cube by watching what

you are doing in a mirror. Left/right and up/down do not

change, but front/back switches as well as the directional

sense of all twists (always looking towards the twisted

slice from its side of the cube).)

Regards,

David V.