Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum
 It is currently Fri Jul 25, 2014 1:50 pm

 All times are UTC - 5 hours

 Page 1 of 1 [ 46 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 11:17 am

Joined: Mon Sep 29, 2008 9:41 am
Location: Spijkenisse, the Netherlands
How exactly do you calculate the number of possible combinations on various puzzles? I know the basics of permutations and ! (I don't know what it's called in english) but I don't know how to apply them on these puzzles, and how to take parity and limitations (like when on a 3x3 one corner is turned, anotherone has to be turned in the opposite directions) into account.
So I'm not really asking for formulas for various puzzles, I'm asking how you can come up with ways to calculate it.
Thanks

Sjoerd

_________________
Olivér Nagy wrote:
43,252,003,274,489,856,000. Or the full number in Hungarian is:
Negyvenháromtrillió-kétszázötvenkétbilliárd-hárombillió-kétszázhetvennégymiliárd-négyszáznyolcvankilencmillió-nyolcszázötvenhatezer )

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 11:36 am

Joined: Sun Dec 07, 2008 6:42 pm
I don't know but, in english ! means X(number)!(factorial) so ! means factorial

Funny bit: my Math teacher for highschool prep taught us a little joke about it, its 3 factorial not THREE(shout cause it's an exclamation) not that funny but it help's me remember it somehow

_________________
~-=Tyler=-~

Fastest Times:3x3x3-37 seconds
Magic: 2.48 seconds(after having it for 2 days)

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 11:42 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Well, you'll need a good understanding of math. Jaap's Website has a good article.

The best way to find out parity limitations is by simply observing the puzzle as you play with it. This way you can make up a hypothesis (it is impossible to swap just two corners) and then you can confirm or dismiss that hypothesis by mathematical proof if you want to be scientifically correct.

There are also limitations other than parity such as pieces being constrained to rings, orbits. A good example of this is the helicopter cube, where each 'inner triangle' would appear to be able to go anywhere, but in fact it is constrained to only six positions (one for each face). That is, without jumbling moves.

All you need to do then is for each individual type of pieces work out how many different permutations and orientations it has. Then you simply multiply those figures with each other (and compensate for any constraints) to come up with the final number.

Permutation:
Eight corners: 8!
Twelve edges: 12!
Parity must be even: divide by two

Orientation:
Corners: 3^8, but there is a parity constraint so it's only 3^7
Edges: 2^12, but there is a parity constraint so it's only 2^11

So in total there are 8!*12!*0.5*3^7*2^11 possible combinations for a 3x3.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 1:22 pm

Joined: Mon Sep 29, 2008 9:41 am
Location: Spijkenisse, the Netherlands
That was a very quick and understandable explanation, as usual, TomZ. There was just one thing I didn’t understand: ‘Parity must be even: divide by two.’

But from this explanation, I can do the same thing for a megaminx:
Permutation:
20 corners: 20!
30 edges: 30!
Parity must be even: divide by two (?)

Orientation:
Corners: 3^20, but there is a parity constraint so it's only 3^19
Edges: 2^30, but there is a parity constraint so it's only 2^29

So in total there are 20!*30!*0.5*3^19*2^29 possible combinations for a megaminx.
But if I were to calculate the Pyraminx Crystals number of possible combinations, I would wind up with the exact same calculation. But because of the lack of centers on a Pyraminx Crystal, the number would have to be smaller. How do I take this into account in my calculations and why like that?

And a simpler one, the Pyraminx,:
Permutation:
4 corners (the things underneath the tips): can not change place, so no permutation
4 tips: can not change place, so no permutation
6 edges: can change places, so just 6!
Parity must be even: divide by two

Orientation:
Corners: 3^4, and no parity constraint.
Tips: 3^4
Edges: 2^6, but there is a parity constraint, so it’s only 2^5

So in total there are 6!*0.5*3^4*2^6, without taking the twistable tips into account, and
6!*0.5*3^4*3^4*2^6 if you would take them into account.

Then my next question:
On the 4x4x4, Jaap Scherhuis gives this calculation: 7!*24!*24!*3^6/4!^6
7= number of corners – 1
24= number of edge wings
3^6=corner orientation

But why does he calculate it like this? I don’t understand.

Sjoerd

_________________
Olivér Nagy wrote:
43,252,003,274,489,856,000. Or the full number in Hungarian is:
Negyvenháromtrillió-kétszázötvenkétbilliárd-hárombillió-kétszázhetvennégymiliárd-négyszáznyolcvankilencmillió-nyolcszázötvenhatezer )

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 2:11 pm

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Sjoerd wrote:
Megaminx: Parity must be even: divide by two (?)
Not true. Parity for edges and corners isn't
related. They both have different and individual parity constraints. In this case, it happens to be that you can never swap just two corners so you have to divide by two for that, and divide by two again because the edges have the same constraint.

But because of the lack of centers on a Pyraminx Crystal, the number would have to be smaller. How do I take this into account in my calculations and why like that?

Consider one corner fixed in it's position, I believe that solves the problem. If not, then simply count the number of ways you can orient a dodecahedron and then divide by that figure.

Then my next question:
On the 4x4x4, Jaap Scherhuis gives this calculation: 7!*24!*24!*3^6/4!^6
7= number of corners – 1
24= number of edge wings
3^6=corner orientation

But why does he calculate it like this? I don’t understand.

He considers one corner fixed to eliminate the floating centers problem.

Edit: Further analysis reveals that what I said about fixing one corner is not true. What made Jaap's calculation look so strange is simply the fact that he hid the /24 by changing 8! into 7! and lowering some exponents.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Last edited by TomZ on Sun Mar 01, 2009 9:02 am, edited 1 time in total.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 2:35 pm

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
TomZ wrote:
Sjoerd wrote:
Megaminx: Parity must be even: divide by two (?)
Not true. Parity for edges and corners isn't
related. They both have different and individual parity constraints. In this case, it happens to be that you can never swap just two corners so you have to divide by two for that, and divide by two again because the edges have the same constraint.

A good question to ask now is "Why is it like that? Why do I have to divide by 4 on a megaminx and only 2 on a cube?"
The answer comes from what is meant by "even" and "odd" parity.
Even parity means that, if you could swap individual pieces, it would take an even number of swaps to solve your puzzle.
Well, it turns out that if you want EVEN parity, you need an ODD number of pieces incorrect in a cycle. (ABCDE -> BCDEA)

With a cube, when you do a twist of one side, you are doing 2 separate four-cycles. Well, 4 cycle = odd. Odd+odd = even.
If you did another twist (odd + odd) + (odd + odd) = even + even = even.
So, you either have odd+odd OR even+even. Both of which equal even. So as long as they're both the Same, we're OK.
So of the 4 possibilities (OE EO EE OO) only 2 are possible. 2 out of 4 = 1/2

With a megaminx, every twist is two 5-cycles. Since a 5-cycle = even, then you're ALWAYS in even parity for BOTH corners and edges. even + even = even ALWAYS.
So, we're left with only one possibility (EE) out of four (OE EO EE OO), so we have to divide by 4.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 7:25 pm

Joined: Mon Feb 02, 2009 8:19 am
Location: Uppsala, Sweden
i made a possibility calculator in gamemaker. it workes great from 2x2 to 8x8 cubes but then it gets error because its to high numbers

_________________
Jared wrote:
THIS IS TWISTYPUZZLES DOT COOOOOOOOOOM!!!

Swedish cuber/builder

my epic 1x2x5

My super awesome website
http://www.olzcubez.tk/ - down for the moment...

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sat Feb 28, 2009 9:17 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Number of Positions of Generalized Twisty Polyhedra
Advanced Counting: Burnside's Lemma (for puzzles with a lot of pieces that look the same)

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 7:51 am

Joined: Mon Sep 29, 2008 9:41 am
Location: Spijkenisse, the Netherlands
Thanks you guys, I'm learning a lot here!
But can you please enlighten me a bit more on even and odd parity? I just don't get what you mean.

But now I can conclude the following:
number of possible positions on the
- 3x3x3: 8!*12!*0.5*3^7*2^11 = 4,3252 x 10^19
-megaminx: 20!*30!*0.25*3^19*2^29 = 1,00669 x 10^68
-pyraminx: 6!*0.5*3^4*2^5 = 933120, without taking the twistable tips into account, and
6!*0.5*3^4*3^4*2^6 = 75582720 if you would take them into account.

-pyraminx crystal: (20!*30!*0.25*3^19*2^29) / (12!*5^12) = 8,6084 x 10^50

I'm not sure about the last one though. I am not able to test the fine details of megaminx edges and corners in correlation to each other, but I do have a pyraminx crystal at hand. The crystals corners work exactly the same as megaminx corners, but the edges are different, in the way they move in a turn. Does this affect the parity cases you get on a crystal, or is it the same? If it is the same, my calculation above is correct. I did the same as with the megaminx, and then divided by the number of possible stances the core can be in.

The translation from megaminx to pyraminx crystal made me think about the void cube. I started thinking, and I can't understand how the centerpieces, the core pieces, are taken into the calculation. Because if four centers were to be scrambled on a 3x3x3, there could be a possiblility of two corners being switched.
So, is the orientation of the core taken into the calculations, or is it just right by coincidence?
If 8!*12!*0.5*3^7*2^11 it is right for the core too, I could conclude:
Number of possible positions on Void Cube: (8!*12!*0.5*3^7*2^11) / (6!*4^6) = 1,466607 x 10^13

_________________
Olivér Nagy wrote:
43,252,003,274,489,856,000. Or the full number in Hungarian is:
Negyvenháromtrillió-kétszázötvenkétbilliárd-hárombillió-kétszázhetvennégymiliárd-négyszáznyolcvankilencmillió-nyolcszázötvenhatezer )

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 9:00 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Parities:

Any permutation can be reached by swapping two pieces (regardless of if it is possible to do on the puzzle - mentally). Consider a 3-cycle edges as being made by doing two swaps. Because you need two swaps to do a 3-cycle, a 3-cycle would have even parity. Swapping two pieces however, is odd parity as the number one happens to be odd.

To determine which parities are possible on a puzzle, look at the permutation that is achieved by doing a single move, for example U. U cycles four edges and four corners. Since a four cycle can be made by doing three swaps, the parity of a four cycle is odd.

Because the parity is odd, any position of edges or corners can be reached, as multiplying and odd number by any natural number will either equal an odd or an even number.

However, the total parity of a U turn is even. Because two four cycles require six swaps, the parity is even. Because an even number of swaps times any natural number will always equal an even number of swaps, the total parity must always be even. Because parity must always be even, odd parities cannot exist. This is why you must divide the amount of possible permutations by two as you can only reach half the possible positions.

Another way of looking at it:
After doing U, the permutation parity of both edges and corners is odd. Doing U2 will make both parities even. So you will always either have odd odd or even even, but never even odd or odd even. You can only get 2/4 possible parity situations, so you have to multiply by 2/4 or in other words, divide by two.

Void Cube:

Your calculation for the void cube seems incorrect. This is what I did:

Orientation is the same as a regular cube, so 3^7 * 2^11

Corner permutation is the same, so 8!

Edge permutation is the same, so 12!

Orientation is space does not matter, so 1/(6*4) (six possible top faces, 4 possible front faces)

The only tricky part is that any permutation parity can be reached. So the final figure is (8!*12!*3^7*2^11)/(24), which is 3604333606207488000 or 3.60*10^18.

Pyraminx Crystal:

Any turn on a pyraminx crystal does a 5 cycle of the edges on the face you are turning, and the edges below the face also undergo a 5 cycle. Five cycles are even parity so you can only reach even parity. You got the majority of the calculation correct, but the way you compensate for the amount of possible orientations of a dodecahedron in space seems to be incorrect.

The face facing up can be any of 12, and then we can choose from 5 faces for the front face. This comes down to sixty possible orientations in space.

So: (30!*2^29*20!*3^19)/(60*2*2) = 1677826942558722452041933871894091752811468606850329477120000000000

Please note that I think my way of fixing one corner does not work after all.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 10:56 am

Joined: Mon Sep 29, 2008 9:41 am
Location: Spijkenisse, the Netherlands
Ok, I think I understand odd and even parity now:
A 3-cycle has even parity, because it needs 2 (even) 2-cycles, not thinking about the fact if it is even possible at all on the certain puzzle.
So a 2-cycle, which is of course 1 2-cycle, is odd parity.
A 4-cycle requires 3 2-cycles, which is odd parity.
But, on most twistypuzzles, a perfect 2-cycle is impossible, so odd parity is impossible, so this means only half of the positions can be real, so divide by 2.

I completely understand your void cube and pyraminx crystal solution. I was very wrong about the number of possible positions of a dodecahedron and a cube in space. I was completely wrong in my calculation...

Back to the 4x4x4,
Jaap writes on his puzzle page (the red text is what I think he means):

Quote:
There are 8 corner pieces with 3 orientations each, 24 edge pieces with 2 orientations each, 24 centre pieces, giving a maximum of 8!·24!·24!·3^8·2^24 positions. This limit is not reached because:

The total twist of the corners is fixed (3)
instead of taking the six centers, he uses one corner to let the rest of the cube sramble around. so only 7 corners can be scrambled, so 7! instead of 8!
The edge orientation is dependent on its position (2^24)
this I don't get at all
There are indistinguishable face centres (4!^6)
4 centers on six sides, so on one side 4! possible positions. This is invalid because scrambing the centers per side won't cause a scrambled cube, so divide by 4!^6. This I do get
The orientation of the puzzle does not matter (24)
I don't know what this means either...
This leaves 7!·24!·24!·3^6/4!^6= 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000 or 7.4·10^45 positions.

Reading this over and over again also made me understand why the fixed centers aren't visible in the calculations. All moveable parts revolve around a fixed core. turning the core means the same as turning all the pieces in opposite direction. unless, of course you were to turn the core 45 degrees.

_________________
Olivér Nagy wrote:
43,252,003,274,489,856,000. Or the full number in Hungarian is:
Negyvenháromtrillió-kétszázötvenkétbilliárd-hárombillió-kétszázhetvennégymiliárd-négyszáznyolcvankilencmillió-nyolcszázötvenhatezer )

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 11:22 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Quote:
There are 8 corner pieces with 3 orientations each, 24 edge pieces with 2 orientations each, 24 centre pieces, giving a maximum of 8!·24!·24!·3^8·2^24 positions. This limit is not reached because:

The total twist of the corners is fixed (3)
This is corner twist restriction. NOT the cube in space problem - fixing corners does not work for this, unlike I what said earlier.
The edge orientation is dependent on its position (2^24)
A bit harder to explain. In the calculation above, he considers that each edge 'half' has an orientation. But they don't as the orientation is basically the permutation (OLL parity is really the two edge wings being swapped).
The orientation of the puzzle does not matter (24)
This is to compensate for the rotation of the cube in space. He doesn't do this via the corner trick I wrongly mentioned earlier. It doesn't work correctly, I told you something that wasn't at all true about this earlier on.

OK, so the first thing I would do is remove the 2^24 from the maximum, leaving:

8!*24!*24!*3^8

Next, I will decrease the exponent of 3^8 to compensate for corner parity:

8!*24!*24!*3^7

Next, I will divide by 24 for the cube orientation, but jaap does something very very sneaky:

(8-1)!*24!*24!*3^(7-1) (3*8 = 24, isn't it?)

And finally divide by 4!6 for the identical pieces.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 12:01 pm

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Sort of on topic here... how is it that Rubik's Cheese has parity restrictions, but Rubik's UFO has none?

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 12:17 pm

Joined: Mon Sep 29, 2008 9:41 am
Location: Spijkenisse, the Netherlands
This must be because of the cheese has 2 pieces of each color, so if two of the same color were to be swapped, you wouldn't notice. The UFO on the other hand has only unique pieces. So if you use UFO algorithms on a cheese, there would be invisible differences in pieces and order of pieces. To solve cheese parity, you have to switch between the pieces you want switched, and two pieces of the same color.
The same problem can occur on any twisty puzzle with two of each piece.
Another problem similar to this is the 'corner' parity you get on original Golden Cubes: there may be a case where only one 'corner' is oriented wrong, which is impossible with normal skewbs. This is due to one piece, that always looks the same, even if oriented 120 degrees wrong. You also have this problem with the half-truncated cube, pyramorphix, mastermorphix, practically every puzzle which originally had a problem with pieces being oriented wrong, but doesn't have anymore.

_________________
Olivér Nagy wrote:
43,252,003,274,489,856,000. Or the full number in Hungarian is:
Negyvenháromtrillió-kétszázötvenkétbilliárd-hárombillió-kétszázhetvennégymiliárd-négyszáznyolcvankilencmillió-nyolcszázötvenhatezer )

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 1:01 pm

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Sjoerd, that is not true. While the Cheese has pieces that appear to be identical, they are mechanically different and cannot exchange places. The puzzles have very different mechanisms.

The UFO is split into two layers whereas the cheese is only one layer.

The cheese has a much simpler mechanism. Three of the six pieces are fixed centers and the other three are held in by these. One move turns around the center, and swaps two of the floating pieces while also flipping them. I'm not entirely sure of this, but this is what I think:

The two piece swap has and odd parity. The orientation swap also has an odd parity (you flip three pieces which is three twists, but as we are modulo 2 [two possible twists] 3=1). This means that the parity of the orientation is related to that of the permutation, so you will have a even orientation and permuation or odd orientation and permutation, but never odd and even or even and odd. (Does anyone know why you need to divide by four rather than two to compensate for this?)

On the ufo however, doing the turn that splits the two layers does a six cycle. A six cycle has odd parity, so any permutation can be achieved.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Sun Mar 01, 2009 5:22 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Fixing a piece always works (to remove problems about orientation) if you fix a piece that is unique and shows both orientation and permutation. For example you can fix a corner on the void cube, pyraminx crystal, or even 4x4, because for every position there is exactly one way to put the corner in a specific place with a specific orientation. But you can't fix an edge on the Alexander's Star because there are two possible edges of each type.

So for void cube, just fix a corner, and then corners have 7! positions and 3^6 orientations, whereas the edges have 12! positions and 2^11 orientations, so you get 7! * 3^6 * 12! * 2^11 = 3.604 * 10^18. I always prefer to fix a piece (if possible) than to consider orientation afterwards, because it makes the calculations much neater.

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Mon Mar 02, 2009 10:17 am

Joined: Mon Sep 29, 2008 9:41 am
Location: Spijkenisse, the Netherlands
I guess I didn´t take a good enough look at the Cheese/Sajt topic in Puzzle Collecting. I thought there were two layers

That is a very nice way to calculate the Void, and it´s very funny to see the same outcome with both different ways.

Now, without looking at Jaap´s website, I´m going to try out the 5x5x5 for myself. I don´t exactly know what the pieces are commonly called on this one, but I believe my names are pretty clear.
permutation orientation
8 Corners: 8! 3^8
12 Middle edges: 12! 2^12
24 Edge wings: 24! 2^24
24 Central edges: 4!^6 --
24 central corners: 4!^6 --

The following rules are valid:
-No two corners can be swapped.
-No two middle edges can be swapped.
-It doesn´t matter if two central edges or central corners of the same color are swapped.
-Two edge wings can be swapped.
So it breaks down to this:
permutation orientation
8 Corners: 8! 3^7
12 Middle edges: 12! 2^11
24 Central edges: 4!^6 --
24 central corners: 4!^6 --

So this creates the following: 8!*12!*24!*3^7*2^11*2^24/4!^6/4!^6

Please correct me if I´m wrong, and correct or enlighten me on the red parts.

Thanks

P.S. I opened this topic because in a year or so I have to have made my very important graduation report, which will be about either chance-calculations in the whole or on Rubik´s Cube, concerning these calculations and the use of polyhedra, because, well, I know a LOT about it

_________________
Olivér Nagy wrote:
43,252,003,274,489,856,000. Or the full number in Hungarian is:
Negyvenháromtrillió-kétszázötvenkétbilliárd-hárombillió-kétszázhetvennégymiliárd-négyszáznyolcvankilencmillió-nyolcszázötvenhatezer )

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Mon Mar 02, 2009 10:48 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Sjoerd wrote:
8 Corners: 8! 3^8
12 Middle edges: 12! 2^12
24 Edge wings: 24! 2^24 They don't have an orientation. Try taking one out and inserting it in a different way. You can't!

These are just wrong:
24 Central edges: 4!^6 --
24 central corners: 4!^6 --
It should be 24! for both. You have twenty four pieces that can go anywhere, so that is the only correct thing.

The following rules are valid:
-No two corners can be swapped.
-No two middle edges can be swapped.
Not true the way you put it (they can be swapped but not on their own) but you don't reflect it in your calculations. To solve this problem you need to divide by two just like on the rubik's cube.

-It doesn´t matter if two central edges or central corners of the same color are swapped.
-Two edge wings can be swapped.
So it breaks down to this:
permutation orientation
8 Corners: 8! 3^7
12 Middle edges: 12! 2^11
24 Edge wings: 24! No orientation.
24 Central edges: 24!/(4!^6) --
24 central corners: 24!/(4!^6) --

The 4!^6 figure is used to compensate for the pieces that are the same. There are 4 pieces that can be swapped without it looking different, and then can be swapped in 4! ways. There are six groups of pieces so you have to raise it to the sixth power (or divide your figure by 4! six times).

Breakdown: 8!*3^7 * 12!*2^10 * 24! * 24!/(4!^6) * 24!/(4!^6) [I am raising 2 to the tenth power rather than the eleventh because I need to compensate for the parity of edges and corners.]

Funnily, I also have this 'profielwerkstuk' that you are talking about this and next year. And of course I have also chosen this subject.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Mon Mar 02, 2009 1:34 pm

Joined: Mon Feb 02, 2009 8:19 am
Location: Uppsala, Sweden
here is 2 functions that will calculate all posible orientations on a cube...

for centerless cues (2x2,4x4,6x6,etc...)
-(co!*cop^(co-1)*24!^cp+eed)/(4!^(cp*6))

for cubes with centers (3x3,5x5,7x7,etc...)
-(co!*cop^(co-1)*ed!*edp^(ed-2)*24!^(cp+eed))/(4!^(cp*6))

explanation:
co = corners
cop = corner permutations
ed = 3x3 edges (only the center edge(12 on a 5x5 & 0 on a 4x4))
edp = edge permutations
cp = center pieces (not the core center)
eed = extra edges (the ones not counted in ed)

to calculate the centers after layers use this function.
centerless: (layers-2)^2/4
center: (layers-3)^2/4+(layers-3)/2

and to calculate extra edges use this one.
centerless: (layers-2)/2
center: (layers-3)/2

example (5x5):
co = 8
cop = 3
ed = 12
edp = 2
cp = 2^2/4+2/2 = 2
eed = 2/2 = 1

calculation:
(8!*3^7*12!*2^10*24!^3)/(4!^12) = 2,828710129*10^74

this function works but the only problem is that my calculator gets error at 10^100. (2x2-5x5)
and my computer gets error at 10^250 (2x2-8x8)

_________________
Jared wrote:
THIS IS TWISTYPUZZLES DOT COOOOOOOOOOM!!!

Swedish cuber/builder

my epic 1x2x5

My super awesome website
http://www.olzcubez.tk/ - down for the moment...

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Mon Mar 02, 2009 6:35 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Google calculator doesn't like calculating REALLY big numbers either, that's why I use logarithms
So for stuff like the Petaminx, instead of (60!)^12 or whatever, I just do 12log(60!), and then at the end I can extract out the exponent of 10 from the integer part, and take 10 to the power of the decimal part to get the rest.
(If I wanted the WHOLE number I could also use Mathematica - it actually doesn't mind calculating out a 1000+ digit number. But I don't ever need the whole number )

Sjoerd: The calculations are:
permutation orientation
8 Corners: 8! 3^7
12 Middle edges: 12!/2 2^11 [either corners or edges must have permutation parity, I chose edges]
24 Edge wings: 24! 1 [edges can have any permutation, and they have no orientation]
24 Central edges: 24!/(4!^6) 1 [there are 24 pieces that can be in any permutation, but we divide by 4!^6 because there are six sets of four identical pieces]
24 central corners: 24!/(4!^6) 1 [same as center edges]
So the full number is (8!*3^7)(12!*2^10)(24!^3/4!^12).

olz: Can you write that with less variables? I can't make head or tail of it.

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Mon Mar 02, 2009 8:31 pm

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
qqwref wrote:
(If I wanted the WHOLE number I could also use Mathematica - it actually doesn't mind calculating out a 1000+ digit number. But I don't ever need the whole number )

But that doesn't mean we don't want to know the whole number anyway

FYI: For those who don't have access to Mathematica, you can always use Python. There's no special setup for big integers
Powers are x**y
You can use this for factorials, though it doesn't work well for values over ten thousand (around 35000 digits):
def f(x): return reduce(lambda x,y: x*y, xrange(1,x+1))

8! * 12! * 24! * 3^7 * 2^11 * 2^24 / (4!^6)^2
would look like
f(8) * f(12) * f(24) * 3**7 * 2**11 * 2**24 / (f(4)**6)**2

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Mon Mar 02, 2009 11:18 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Well... it's not useful for numbers that have a simple closed form. But what about the ones that don't?

Here's a challenge to anyone who thinks they are really good at calculating the numbers of positions: Suppose I took a 6x6 and took off all of the stickers on the corner and edge pieces. Now how many positions does it have?

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 1:39 am

Joined: Tue Mar 25, 2008 2:51 am
Location: Malibu, California
qqwref wrote:
Here's a challenge to anyone who thinks they are really good at calculating the numbers of positions: Suppose I took a 6x6 and took off all of the stickers on the corner and edge pieces. Now how many positions does it have?

4 different types of center pieces each having 24 pieces gives 24!^4
but because there are indistinguishable pieces, divide by 4!^24
all other pieces have one distinguishable position
thus a total of 24!^4/4!^24 = 111 109 931 429 587 260 177 560 270 582 060 177 705 848 534 410 000 000 000 000 000 or about 1.11*10^62 positions

_________________
I am taking a break from the forum. You can reach me by PM if needed.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 1:55 am

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
No, it's not so easy, you have to take into account orientation of the puzzle as well, since only the center pieces have stickers on them. For example if you did this on a 3x3 and allowed the centers to be moved to any position, there are not 720 (6!) positions, but just 30... (You can't just divide by 24 for the answer on the 6x6 version, though, it's not so easy as that )

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 2:27 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Interesting challenge...

For the 3x3 center, one center could be considered fixed on top, leaving 5! permutations. Then you would still have to divide by four to compensate for orientation.

If you were to use the same logic on the 6x6, you would be left with:

23!*24!^4*4!^-24*0.25=1.157*10^60

I don't really know if this would work, but maybe it will. What would be an argument against what I'm doing is that the center pieces aren't rotationally symmetric so rotating the puzzle would move my fixed piece, but I'm going to give this a try as it could very well be the solution.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 3:02 am

Joined: Tue Mar 25, 2008 2:51 am
Location: Malibu, California
Okay, so I would then say that it's
24!^4/((4!^24)*24) = 4 629 580 476 232 802 507 398 344 607 585 840 737 743 688 933 750 000 000 000 000 or about 4.63*10^60
but you say this is wrong... hmm, I will have to give this more thought

_________________
I am taking a break from the forum. You can reach me by PM if needed.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 10:40 am

Joined: Mon Feb 02, 2009 8:19 am
Location: Uppsala, Sweden
qqwref wrote:
olz: Can you write that with less variables? I can't make head or tail of it.

this is the only numbers that changes in the functions.
the others always stay the same

 Attachments: 6677 copy.jpg [ 225.2 KiB | Viewed 4908 times ]

_________________
Jared wrote:
THIS IS TWISTYPUZZLES DOT COOOOOOOOOOM!!!

Swedish cuber/builder

my epic 1x2x5

My super awesome website
http://www.olzcubez.tk/ - down for the moment...

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 1:55 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
TomZ wrote:
What would be an argument against what I'm doing is that the center pieces aren't rotationally symmetric so rotating the puzzle would move my fixed piece, but I'm going to give this a try as it could very well be the solution.

Your number would be correct if the pieces were somehow labeled, but unfortunately they're not You say "fix this blue piece" and I say "which one? there are four!". And the problem is that you can't just divide by four, because for each position there are not necessarily four distinct ways to fix a blue piece to a given spot - two of those ways to fix a blue piece might look the same.

Consider a problem I mentioned on my blog, with a cube with 3 red faces and 3 blue faces, where you can switch any two faces freely... Try to figure out the number of positions, and you'll soon find it is impossible using the techniques you guys are trying for the 6x6 puzzle. The correct answer is 2, but 6!/(3!^2) is 20 and there is no easy way to remove that factor of 5...

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 2:16 pm

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
qqwref wrote:
For example if you did this on a 3x3 and allowed the centers to be moved to any position, there are not 720 (6!) positions, but just 30...

Would this be a correct restatement of this exercise?
How many unique ways can you arrange 6 colors on the faces of a cube?

If that's the case, then would the solution to your 6x6x6 problem be equivalent to "apply Burnside's lemma to the centers of a 6x6x6"?

(just trying to understand what you are REALLY asking)

 Perhaps I misunderstand "Burnside's Lemma". I mean to say "Take the full possibilities of the 6x6x6 centers and then account for all symmetries"

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 3:03 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Yeah, that's what the problem asks. We want to account for all symmetries, of course, so two positions should always be considered equivalent if they're a rotation away from each other.

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 3:08 pm

Joined: Mon Jul 21, 2008 4:52 am
Location: Brighton, UK
TBTTyler wrote:
I mean to say "Take the full possibilities of the 6x6x6 centers and then account for all symmetries"
That's the way I'm taking it, too. Visually distinct permutations. It looks to me that Danny's latest calculation would be correct apart from the symmetries. My understanding is:

(24!)^4/(4!)^24 = 1.111 * 10^62 = perms of 6x6x6 centers not taking account of orientation of the cube or symmetries.

As above / 24 = 4.630 * 10^60 = perms of 6x6x6 centers taking account of orientation of the cube but not accounting for symmetries.

As above but subtracting
(perms with 2-way symmetry rotating 180 degrees around a face)
+ (3 * perms with 4-way symmetry rotating 90 degrees around a face)
+ (2 * perms with 3-way symmetry rotating 120 degrees around a vertex)
+ (perms with 2-way symmetry rotating 180 degrees around an edge)
 + similarly with other symmetry group possibilities that occurred to me after posting
= the correct answer, by preventing double-, triple-, or quadruple-counting of visually identical patterns?

Of course, even assuming this is correct, the question becomes how to calculate the above symmetries... very tricky...

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 4:35 pm

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
It's funny. I did a search on Burnside's lemma, and got qqwref's blog. Only then did I notice that he'd already posted a link to the exact page
So using the lemma ...

1 Identity: (24!)^4/(4!)^24
6 90 face twist: 24 4cycles = 24!
3 180 face twist:48 2cycles = 48! / 2^24
8 120 corner twist:32 3cycles = 0
6 180 Edge twist:48 2cycles = 48! / 2^24

So
( (24!)^4/(4!)^24 + 6*24! + 3 * 48! / 2^24 + 6* 48! / 2^24) / 24
4629580753705438444196634119585828862568331392829069859840000
4.63*10^60

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 5:29 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
TBTTyler wrote:
1 Identity: (24!)^4/(4!)^24
6 90 face twist: 24 4cycles = 24! Ah! Not so fast. There are 4 orbits each with 6 groups of 4 identical pieces... so the number here is actually (6!)^4.
3 180 face twist:48 2cycles = 48! / 2^24 Similarly, there are 4 orbits each with 6 groups of 4 identical pieces, so in each orbit you have 12 2-cycles, and the total number here is (12!/(2^6))^4.
8 120 corner twist:32 3cycles = 0
6 180 Edge twist:48 2cycles = 48! / 2^24 See my comment for the 180 face twists.

So the number I get is
(24!^4/4!^24 + 6*6!^4 + 9*12!^4/2^24)/24 = 4.62958048 x 10^60
(4629580476232802507398344607585841914426008996279100784640000)

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 5:34 pm

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
Restricting Orbits ... I *KNEW* I was forgetting something.

I did get the first 7 digits right, and I thought you never needed the whole number

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Tue Mar 03, 2009 5:42 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
For most applications, you don't. You can get a pretty good approximation by just taking the identity term (24!^4 / 4!^24 / 24), which is what Danny Devitt did - and that's good enough if you just want to get a sense of how complex a puzzle is. But if you're going to give lots of digits... well, they better all be right

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Wed Mar 04, 2009 1:44 pm

Joined: Mon Jul 21, 2008 4:52 am
Location: Brighton, UK
qqwref wrote:
For most applications, you don't. You can get a pretty good approximation by just taking the identity term (24!^4 / 4!^24 / 24), which is what Danny Devitt did - and that's good enough if you just want to get a sense of how complex a puzzle is. But if you're going to give lots of digits... well, they better all be right
Michael -- Thanks for the interesting problem and ingenious solution with built-in free math lesson! I haven't done much college-level math for many (15+) years and it was a bit painful at first scraping the rust off my brain. After an initial mental block, I finally twigged that the act of dividing by 4!^24 (counting only one arrangement of pieces within orbits/subgroups of identical-looking pieces) reduces all symmetric permutations to a single orientation. I had been mistaking the B's L identity term for a symmetry sympathizer when it was a symmetry killer all along. So when continuing on to divide (24!^4)/(4!^24) by 24, one has *undercounted* distinct perms, hence the need for the other terms as per Burnside's Lemma. Probably obvious to you and Tyler all along, but, for me, a Eureka moment. Suddenly the webpages about Burnside's Lemma started to flow and really make sense. Extremely stimulating and fun.

P.S. I'm posting a question for you in the Gelatinbrain thread that I hope you'll answer -- something I've been curious about for quite a while.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Wed Mar 04, 2009 4:41 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Oh, I don't read the gelatinbrain thread. If you want to ask me a direct question it's better to just use PMs.

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Wed Mar 04, 2009 5:05 pm

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
Julian wrote:
Probably obvious to you and Tyler all along

Had it been obvious to me, I would have gotten it right. *grumble grumble*
The only thing obvious to me was that the simple answer was incorrect (and that's half because Michael said so )
I read about Burnside's lemma sometime last year when digging through Jaap's puzzle page, and thought it sounded like the right way to do this.
Then I found his blog on Burnside's lemma and applied (almost verbatim) what he showed there. I'm just still mad at myself for not realizing that individual orbits should be taken into account separately

I've only ever taken high school math classes (ok, so I took 1 stat class in college, but there was no combinatorics), but I love math and I'm starting to spend a lot of time here:
http://ocw.mit.edu/OcwWeb/web/home/home/index.htm
Right now, I'm halfway through an algorithms class. Really cool stuff.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Wed Mar 04, 2009 7:30 pm

Joined: Mon Jul 21, 2008 4:52 am
Location: Brighton, UK
TBTTyler wrote:
I've only ever taken high school math classes (ok, so I took 1 stat class in college, but there was no combinatorics), but I love math and I'm starting to spend a lot of time here:
http://ocw.mit.edu/OcwWeb/web/home/home/index.htm
Right now, I'm halfway through an algorithms class. Really cool stuff.
Thanks for the link. What a great idea from the nice people at MIT!

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Wed Mar 11, 2009 5:14 am

Joined: Fri May 06, 2005 10:13 am
Location: Norway
Break down the effect of the different operators to see what's really possible. An inner slice turns of a 4x4x4 contains 2 4-cycles of centers, all in the same orbitals. It also contains a 4-cycle of edges. Trivially a 3-cycle is possible - so this opens up the possibility for a swap of edges -- parity!!

This is an easy example but similar analysis can be done on higher order cubes, then formalised and generalised. I have yet to see any article/paper do a complete analysis in layman's terms.

Chris hardwick has a page about it here.

Per

_________________
"Life is what happens to you while you are busy making other plans" -John Lennon, Beautiful Boy

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Wed Mar 11, 2009 6:34 am

Joined: Fri May 06, 2005 10:13 am
Location: Norway
**SLIGHTLY OFF TOPIC!!**

Every even position of a random sized regular (nxnxn) cube is reachable by executing a series of commutators. I have a quite easy proof for the 3x3x3 cube. A proof for higher order cubes is not quite so easy. I'd like to come up with a proof that is in essence non-mathematical. A constructive proof

Per

_________________
"Life is what happens to you while you are busy making other plans" -John Lennon, Beautiful Boy

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Wed Mar 11, 2009 1:49 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
What's your proof for the 3x3? I was trying to formalize the number of positions of the NxNxN cube a while back but I couldn't prove that every position was achievable.

(PS: Every even position can be achieved by *one* commutator, the trouble is to find it XD)

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Thu Mar 12, 2009 5:16 am

Joined: Fri May 06, 2005 10:13 am
Location: Norway
qqwref wrote:
What's your proof for the 3x3? I was trying to formalize the number of positions of the NxNxN cube a while back but I couldn't prove that every position was achievable.

(PS: Every even position can be achieved by *one* commutator, the trouble is to find it XD)

My proof for 3x3x3 cube can be found here.

Generalising to nxnxn cube there is an overwhelming number of move-pairs to find a commutator for.

To further prove that any even position is reachable by a single commutator it is enough to show that two consecutive commutators can be written as ONE commutator. A simple proof by induction then gives us what we are after ...

Per

_________________
"Life is what happens to you while you are busy making other plans" -John Lennon, Beautiful Boy

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Thu Mar 12, 2009 5:49 am

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
perfredlund wrote:
To further prove that any even position is reachable by a single commutator it is enough to show that two consecutive commutators can be written as ONE commutator. A simple proof by induction then gives us what we are after ...

EDIT: Wait. I'm beginning to not be sure if a product of commutators can be written as one. Let me think about this a bit more...

I just thought of a different way to think about it, although I am not sure if this is legitimate. It is known that the commutator subgroup of the symmetric group S_n is the alternating group A_n, and since we can write any 3x3 position as a permutation of the stickers (since each sticker is distinct) every 3x3 position is a subset of S_48, so the commutator subgroup ought to be every 3x3 position in A_48 (that is, the ones which are achievable in an even number of quarter turns). I'm not quite sure how to prove that every even position on the 3x3 can be achieved as a commutator of 3x3 positions, though (since all this approach seems to show is that it is a commutator of SOME two sticker permutations). Your constructive proof is quite nice but I think it would be difficult to generalize

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Thu Mar 12, 2009 6:28 am

Joined: Fri May 06, 2005 10:13 am
Location: Norway
Hmmm ...

Check here.

Per

_________________
"Life is what happens to you while you are busy making other plans" -John Lennon, Beautiful Boy

Top

 Post subject: Re: Calculating numbers of possibilitiesPosted: Thu Mar 12, 2009 5:46 pm

Joined: Sat Jan 22, 2005 12:12 pm
Location: NY, USA
Yeah, I found that. But I was really intrigued by the line that said "Indeed, Ore showed that in the symmetric groups S_infinity and S_n, every product of commutators is a commutator." I wonder if this applies to subsets of S_n as well...

_________________
My official times
Puzzle Solving Service! - a puzzle that has never been scrambled and solved has been wasted.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 46 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 15 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic