From charlesreid1

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, 11 edges determine the 12th = 2^11
  • 8 different corner pieces to be distributed to 8 locations = 8!
  • 12 different edge pieces to be distributed to 12 locations = 12!

Furthermore, some of these possibilities are not possible. Only even parity cases can occur on the 3x3 cube, cutting the number of ways of distributing the corners and edges in half.

Total number of permutations of a 3x3 cube:


N = 3^{7} \times 2^{11} \times \dfrac{ 8! \times 12! }{ 2 } = 43,252,003,274,489,856,000 \sim 10^{19}

or about 43 quintillion permutations.

Number of permutations of 4x4

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 eight edge pieces, and four corners. Counting:

  • Placement: 8 corners being placed, for total of 8!
  • Placement: 12 left-double-edge pieces that can go in 24 possible double-edge locations, for a total of \dfrac{24!}{12!}
  • Placement: 12 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
  • 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 double-edge piece uniquely determines its orientation. If a left-double-edge piece is placed in a left-double-edge position, it will be oriented "right-side up". If a left-double-edge piece is placed in a right-double-edge position, it will be oriented "upside-down". And likewise for right-double-edge positions. That means that if a double edge cubie is made part of a double edge, it has only two possible positions on that double edge. Therefore, there are 0 degrees of freedom due to orientation of double edge pieces.
  • 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 = 147947189226886589978930309391974400000 \sim 10^{38}

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