From charlesreid1

(Redirected from Rubiks Revenge/Numbers)

Counting Permutations

Number of permutations of 3x3

To count number of permutations of 3x3, count permutations due to both the placement and orientation of each type of piece (corners and edges; centers are fixed):

  • 3 possible rotations of 8 corners, 7 corners determine the 8th = 3^7
  • 2 possible rotations of 12 edges = 2^{12}
  • 8 different corner pieces to be distributed to 8 locations = 8!
  • 12 different edge pieces to be distributed to 12 locations = 12!
  • Half of the cube permutations (those requiring center faces to be swapped) cannot be reached without disassembling the cube = \frac{1}{2}

Total number of permutations of a 3x3 cube:


N = 3^{7} \times 8! \times 2^{12} \times 12! \times \frac{1}{2} = 86504006548979712000 \sim 8.65040 \times 10^{19}

or about 86 quintillion permutations.

Number of permutations of 4x4

Note: dedge = double edge

On a 4x4 cube, we use the same technique as the 3x3, counting permutations due to both placement and orientation of each type of piece. Now each face has four corner pieces, four double edges for a total of eight edge pieces, and four corner pieces. Counting:

Placing cubies:

  • Placement: 8 corners being placed, for total of 8!
  • Placement: 12 dedge left wing pieces that can go in 24 possible double-edge locations, for a total of \dfrac{24!}{12!}
  • Placement: 12 dedge right-double-edge pieces that can go in 24 possible double-edge locations, for a total of \dfrac{24!}{12!}
  • Placement: 24 center squares, which can be arranged in any configuration, for a total of 24!

Orienting cubies:

  • Orientation: 3 orientations are possible on the 8 corners, placement of 7 determines the last, for total of 3^7
  • Orientation: interestingly, the position of a dedge piece uniquely determines its orientation. If a dedge left wing piece is placed in a left dedge position, it will be oriented "correctly". If a dedge left wing piece is placed in a right dedge position, it will be oriented "backwards". And likewise for dedge right wing pieces being "correct" if placed in a right dedge spot and "backwards" if placed in a left dedge spot. Thus, there are 0 degrees of freedom due to orientation of double edge pieces. It's orientation is determined by the type of wing piece and the position being occupied.
  • Orientation: Like the double-edge pieces, the center squares get 0 degrees of freedom due to orientation. Distributing 24 center squares among 24 center square positions uniquely determines the state of those center squares.

The grand total, then, is:


T = 3^7 \times 8! \times \left( \dfrac{24!}{12!} \right)^2 \times 24! = 91793597096746925044380089227138852984017051539472384000000000 \sim 9.17935 \times 10^{61}

Number of permutations of 5x5

On a 5x5 cube, we apply the above techniques. We have fixed centers, so we don't consider those a type. The other cubie types are face cubies, corner cubies, and tredges, composed of tredge centers (the middle piece of the three pieces that make up a tredge) and tredge wings (the two end pieces of the three pieces that make up a tredge). There are 8 corner cubies, 9 face cubies on each face (and since 1 is fixed, actually 8 per face) for a total of 48 face cubies that can move, and 12 triple edges, for a total of 12 tredge centers, 12 tredge left wing pieces, and 12 tredge right wing pieces.

We run through enumeration of all the ways of placing each piece at a location on the cube, then multiply by the possible orientations, and reduce by the number of cube states that can't be reached.

Placing cubies:

  • Placement: 8 corners being placed, for a total of 8!
  • Placement: 48 face cubies being placed into 48 slots, any configuration, for a total of 48!
  • Placement: 12 tredge left wings that can go into 24 possible double-edge locations for a total of \dfrac{24!}{12!}
  • Placement: 12 tredge right wings that can go into 24 possible double-edge locations for a total of \dfrac{24!}{12!}
  • Placement: 12 tredge centers that can go into 12 possible tredge center locations for a total of 12!

Orienting cubies:

  • Orientation: 3 possible orientations of the 8 corners, but the placement of 7 of the corners determines the last, for a total of 3^7
  • Orientation: the 48 face cubies have zero degrees of freedom because they have only one face and therefore no orientation.
  • Orientation: the 24 triple edge wing cubies, like on the 4x4 cube, have no degrees of freedom due to orientation. This is because the position of the cubie and whether it is left or right wing piece determine its orientation.
  • Orientation: the 12 triple edge (tredge) center cubies can be oriented in 2 ways each, 2^{12} (note this is different from the case of 12 edges on the 3x3, where one single edge piece cannot be inverted by itself, so 11 edge cubies fix the state of the 12th cubie; on a 5x5, a single tredge center cubie can be inverted by itself.)

(Side note: how/why did we know to treat the tredge wings separately, instead of just tossing them all in a mix of 24 wing pieces that go into 24 locations? Because we know that in the solved state, solved tredges always consist of a left wing piece and a right wing piece.)

This makes the grand total:


T = 3^7 \times 8! \times 48! \times \left( \dfrac{24!}{12!} \right)^2 \times 12! \times 2^{12}

This is equal to a number that is even larger than a googol (10^{100}):


3603399540205611914283185376146349701872354441978576086385485789093464996018186389353459508838400000000000000000

This is approximately


\sim 3.6033995402 \times 10^{111}

Counting Cycles

Length of Cycles on 3x3

One of the interesting features of a Rubik's Cube is that, starting from a solved cube, if any sequence of moves is repeated long enough on the cube, will eventually result in the cube returning to the solved state.

The simplest example is a single move (like U): after executing U four times, the cube is returned to the solved state.

It is a little less trivial with a sequence of moves like U'R'UR or LU, but these also eventually result in returning the cube to its solved state after 6 repetitions of the sequence U'R'UR or 105 repetitions of the LU sequence.


Flags