Thread: "Calculating the number of permutation of 2by2by2by2by2"

type="cite">

David,

I'm sorry that I have exasperated you. I really don't mean to argue
anything and I believe that I get what you are saying. I think the
tension is due to the fact that each of us is interested in related but
different concepts here. In the 2D case you see 24 distinct states in a
way that is both mathematically clean, meaningful and interesting to
you. I on the other hand see only 8 states that are interesting to me,
however messy they may be to count.

Regarding recolorings, please don't think that I care about the
particular colors. I only care about the patterns that they create.
Perhaps we can clear this up by talking about those color pairs that are
important to you. Imagine a pristine cube. If you swap two opposite sets
of stickers, then you feel that nothing has changed even though you
can't rotate the whole cube to match the original colors. (Perhaps you
mean to allow only an even number of pair swaps.) For the things that I
care about, definitely nothing has changed when you do that because the
puzzle is still in what I consider to be *the* solved state which I
define as the one in which all sides have a single different color. For
that matter I am also perfectly happy swapping the stickers of two
adjacent faces because that gives the same result as when swapping
opposite sides. The puzzle remains solved.

Unless I've just said something whacky, I think we can leave it at that.
At least I hope so!
-Melinda

On 5/9/2012 9:11 PM, David Vanderschel wrote:
> 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.
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>

LS0tLS1CRUdJTiBQR1AgU0lHTkVEIE1FU1NBR0UtLS0tLQ0KSGFzaDogU0hBMQ0KDQpPbiBU
aHUsIDEwIE1heSAyMDEyIDE5OjA1OjUxIC0wNTAwDQoiRGF2aWQgVmFuZGVyc2NoZWwiIDxE
dmRTQEF1c3Rpbi5SUi5jb20+IHdyb3RlOg0KDQo+IEkgYW0gaW50ZXJlc3RlZCBib3RoIGlu
IHRoZSBudW1iZXIgb2YgZGlzdGluY3Qgc3RhdGVzIGFzIA0KPiBkZXRlcm1pbmVkIGJ5IHRo
ZSBwb3NpdGlvbnMgYW5kIG9yaWVudGF0aW9ucyBvZiB0aGUgY3ViaWVzIGFzIHdlbGwgYXMN
Cj4gdGhlIGVxdWl2YWxlbmNlIGNsYXNzZXMgb2YgdGhvc2Ugc3RhdGVzIHVuZGVyIGNvbmp1
Z2F0aW9uIGJ5IGEgDQo+IHN5bW1ldHJ5LiBZb3VyICJpbnRlcmVzdCIgaW4gdGhlIGVxdWl2
YWxlbmNlIGNsYXNzZXMgdW5kZXINCj4gY29uanVnYXRpb24gKG9yIHdoYXRldmVyIHlvdSBo
YXZlIGluIG1pbmQpIHNlZW1zIHRvIGdvIHNvIGZhciB0aGF0DQo+IHlvdSB3b3VsZCBhY3R1
YWxseSBleGNsdWRlIHRoZSBkaXN0aW5jdCBzdGF0ZXMgb24gd2hpY2ggdGhlIHB1Ymxpc2hl
ZA0KPiBjb3VudHMgYXJlIGJhc2VkIC0gdG8gdGhlIGV4dGVudCB0aGF0IHlvdSBleHByZXNz
ZWQgY29uY2VybiB0aGF0IHRoZSANCj4gcHVibGlzaGVkIG51bWJlcnMgYXJlIGluIGVycm9y
Lg0KDQpJJ2xsIGp1bXAgaW4gaGVyZSB3aXRoIGEgY29uY3JldGUgZXhhbXBsZS4gIEEgd2hp
bGUgYmFjayBJIGVudW1lcmF0ZWQNCnRoZSBzaG9ydGVzdCBwb3NzaWJsZSBzZXF1ZW5jZSBv
ZiBtb3ZlcyB0byBnZW5lcmF0ZSBldmVyeSAzLWN5Y2xlDQp0aGUgY29ybmVycyBvbiBhIFBl
bnR1bHRpbWF0ZSBjYW4gYmUgaW4uDQoNCkRlcGVuZGluZyBvbiB0aGUgcmVsYXRpdmUgcG9z
aXRpb25zIG9mIHRoZSBjb3JuZXJzICh0aGUgcGF0dGVybiBvZiB0aGUNCmN5Y2xlKSwgdGhl
IHBhdHRlcm4gY2FuIGhhdmUgbm8gc3ltbWV0cnksIG1pcnJvciBzeW1tZXRyeSwgcm90YXRp
b25hbA0Kc3ltbWV0cnksIG9yIG1pcnJvciAmIHJvdGF0aW9uYWwgc3ltbWV0cnkuDQoNCkhl
cmUgaXMgYW4gZXhhbXBsZSBvZiBhIDMtY3ljbGUgdGhhdCBkb2Vzbid0IGhhdmUgYW55IHN5
bW1ldHJ5Og0KaHR0cDovL3d3dy5icmFuZG9uZW5yaWdodC5uZXQvdHdpc3R5cHV6emxlcy9w
b3N0X2ltYWdlcy9wZW50dWx0aW1hdGUvMDFfMDAwLnBuZw0KDQpUaGlzIG9uZSBoYXMgbWly
cm9yIHN5bW1ldHJ5Og0KaHR0cDovL3d3dy5icmFuZG9uZW5yaWdodC5uZXQvdHdpc3R5cHV6
emxlcy9wb3N0X2ltYWdlcy9wZW50dWx0aW1hdGUvMDJfMDAwLnBuZw0KDQpUaGlzIG9uZSBo
YXMgcm90YXRpb25hbCBzeW1tZXRyeSAodGhpcyBwYXR0ZXJuIGlzIGNoaXJhbCk6DQpodHRw
Oi8vd3d3LmJyYW5kb25lbnJpZ2h0Lm5ldC90d2lzdHlwdXp6bGVzL3Bvc3RfaW1hZ2VzL3Bl
bnR1bHRpbWF0ZS8wOV8wMDAucG5nDQoNClRoaXMgb25lIGhhcyBib3RoIHJvdGF0aW9uYWwg
YW5kIG1pcnJvciBzeW1tZXRyeToNCmh0dHA6Ly93d3cuYnJhbmRvbmVucmlnaHQubmV0L3R3
aXN0eXB1enpsZXMvcG9zdF9pbWFnZXMvcGVudHVsdGltYXRlLzA2XzAwMC5wbmcNCg0KVGhl
IHJlYXNvbiB0aGUgc3ltbWV0cnkgb2YgdGhlc2UgcGF0dGVybnMgbWF0dGVyIGlzIHRoYXQg
YnkNCnJlLW9yaWVudGF0aW9uIC8gbWlycm9yaW5nIC8gaW52ZXJ0aW5nIGEgc2VxdWVuY2Ug
eW91IGNhbiBhY2hpZXZlIG1vcmUNCnRoYW4gb25lIGRpc3RpbmN0ICJwZXJtdXRhdGlvbiIg
b2YgdGhlIHB1enpsZSBldmVuIHRob3VnaCBhbGwgb2YgdGhlc2UNCmRpc3RpbmN0IHBlcm11
dGF0aW9ucyBhcmUgZXF1aXZhbGVudCB1bmRlciBjb25qdWdhdGlvbi4NCg0KT25lIG9mIHRo
ZSBjb21wbGljYXRpb25zIG9mIGxvb2tpbmcgYXQgdGhlIHBlcm11dGF0aW9uIG9mIGNvcm5l
cnMgb24NCnRoZSBQZW50dWx0aW1hdGUgaXMgdGhhdCB0aGUgY29ybmVycyBoYXZlIG9yaWVu
dGF0aW9uIGluIGFkZGl0aW9uIHRvDQpqdXN0IHRoZWlyIHBvc2l0aW9uLiAgVGhpcyBtZWFu
cyB0aGF0IHRoZXJlIGFyZSA5IGRpc3RpbmN0IGNsb2Nrd2lzZQ0KMy1jeWNsZXMgZGVwZW5k
aW5nIG9uIHRoZSByZXN1bHRpbmcgdHdpc3Qgb2YgZWFjaCBjb3JuZXIuDQoNCkZvciBzaW1w
bGljaXR5IHJhdGhlciB0aGFuIGRlc2NyaWJpbmcgaG93IHRvIHJlLW9yaWVudCAvIG1pcnJv
ciB0aGUNCnB1enpsZSBJIGhhdmUgaW5zdGVhZCBpbnZlcnRlZCAvIG1pcnJvcmVkIC8gcmUt
b3JpZW50ZWQgdGhlIHNlcXVlbmNlIG9mDQptb3ZlcyB0aGVtc2VsdmVzLg0KDQpCeSB0YWtp
bmcgdGhlIHNlcXVlbmNlIFtEJywgRScyLCBEJywgRTIsIEMsIEEnLCBFMiwgQSwgRScyLCBD
JywgRDJdIGFuZA0KYXBwbHlpbmcgdGhlc2Ugc3ltbWV0cmllcywgeW91IGNhbiByZWFjaCA2
IGRpc3RpbmN0IHBlcm11dGF0aW9ucyB0aGF0DQphcmUgYWxsIGEgY2xvY2t3aXNlIDMtY3lj
bGUgb2YgdGhlIHNhbWUgcGllY2VzIG9uIHRoZSBQZW50dWx0aW1hdGU6DQoNClR3aXN0czog
MDAwIC8gMDIxIC8gMTAyIC8gMTExIC8gMjEwIC8gMjIyICgxMSBtb3Zlcyk6DQowMDAgOiBb
RCcsIEUnMiwgRCcsIEUyLCBDLCBBJywgRTIsIEEsIEUnMiwgQycsIEQyXQ0KMDIxIDogW0gy
LCBDJywgSScyLCBCLCBJMiwgQicsIEMsIEkyLCBIJywgSScyLCBIJ10NCjEwMiA6IFtKMiwg
SScsIEUnMiwgRiwgRTIsIEYnLCBJLCBFMiwgSicsIEUnMiwgSiddDQoxMTEgOiBbSicsIEkn
MiwgSicsIEkyLCBFLCBGJywgSTIsIEYsIEknMiwgRScsIEoyXQ0KMjEwIDogW0QyLCBFJywg
QycyLCBBLCBDMiwgQScsIEUsIEMyLCBEJywgQycyLCBEJ10NCjIyMiA6IFtIJywgQycyLCBI
JywgQzIsIEksIEInLCBDMiwgQiwgQycyLCBJJywgSDJdDQoNClRoZSAjIyMgZGVzaWduYXRp
b25zIGRlc2NyaWJlIHRoZSByZXN1bHRpbmcgdHdpc3Qgb2YgdGhlIGNvcm5lcnMuICAwDQpi
ZWluZyBubyB0d2lzdCwgMSBiZWluZyBjbG9ja3dpc2UsIGFuZCAyIGJlaW5nIGNvdW50ZXIt
Y2xvY2t3aXNlLg0KDQpGb3IgdGhlIHNha2Ugb2YgY291bnRpbmcgdGhlIG51bWJlciBvZiBw
b3NzaWJsZSBwZXJtdXRhdGlvbnMgb2YgdGhlDQpQZW50dWx0aW1hdGUsIGVhY2ggb2YgdGhl
c2UgYXJlIGNvdW50ZWQgYXMgZGlzdGluY3QgcG9zaXRpb25zLiAgSSB0aGluaw0KdGhleSBz
aG91bGQgYmUuICBUaGlzIGlzIHRoZSBjYXNlIHdpdGggZXZlcnkgdHdpc3R5IHB1enpsZS4N
Cg0KVGhlcmUgaXMgYWxzbyB0aGUgbXVjaCBtb3JlIGNvbXBsaWNhdGVkIHF1ZXN0aW9uIG9m
IGhvdyBtYW55DQoiZXNzZW50aWFsbHkgZGlzdGluY3QiIHBvc2l0aW9ucyB0aGUgcHV6emxl
IGhhcy4gIFRoYXQgY291bnQgd291bGQNCmNvbnNpZGVyIHRoZSBhYm92ZSA2IHBlcm11dGF0
aW9ucyBhcyBqdXN0IG9uZS4NCg0KQ2FsY3VsYXRpbmcgaXQgd291bGQgYmUgdmVyeSBkaWZm
aWN1bHQuICBGb3IgYSBkb2RlY2FoZWRyb24gdGhlcmUgYXJlDQoxMjAgb3JpZW50YXRpb25z
IChjb25zaWRlcmluZyBtaXJyb3JpbmcgdG9vKSBidXQgbm90IGFsbCBwb3NpdGlvbnMgaGF2
ZQ0KdGhlIHN5bW1ldHJpZXMgbmVjZXNzYXJ5IHRvIGJlIGVxdWl2YWxlbnQgdW5kZXIgdGhl
c2UgcmUtb3JpZW50YXRpb25zDQphbmQgbWlycm9yaW5nLg0KDQpUaGUgbnVtYmVyIG9mIGVz
c2VudGlhbGx5IGRpZmZlcmVudCBwb3NpdGlvbnMgc2hvdWxkIGJlIGxlc3MgdGhhbjoNCigo
MjAhIC8gMikgKiAoM14xOSkgKiAoMTIhIC8gMikpIC8gNjANCg0KQnV0IGdyZWF0ZXIgdGhh
bjoNCigoKDIwISAvIDIpICogKDNeMTkpICogKDEyISAvIDIpKSAvIDYwKSAvIDEyMA0KDQpJ
J2QgY2VydGFpbmx5IGxpa2Ugc29tZSBpbnNpZ2h0IGludG8gaG93IHRvIGdldCBhdCB0aGUg
bnVtYmVyIGJ1dCBJDQpkb24ndCBoYXZlIGFueSBpZGVhcyBhYm91dCBob3cgdG8gYXBwcm9h
Y2ggdGhlIHByb2JsZW0uDQoNCkJyYW5kb24NCg0KLS0tLS1CRUdJTiBQR1AgU0lHTkFUVVJF
LS0tLS0NClZlcnNpb246IEdudVBHIHYyLjAuMTcgKEdOVS9MaW51eCkNCg0KaUVZRUFSRUNB
QVlGQWsrc2FzY0FDZ2tRcWFHUHpBc2w5NEo3eGdDY0RjMHQwL0NLekRkYXg1bXFiNFFDeWpR
cA0KVGlZQW4xL3BrNFNsZDQzK250ZTREbjQ1ODBFamZUOFANCj1uaXd0DQotLS0tLUVORCBQ
R1AgU0lHTkFUVVJFLS0tLS0NCg==