Permutations

Our shuffling will generate a permutation of the cards. A permutation is a bijection from a set onto itself. In the case of a deck with index i = 2n + 1, the set contains the integers from 1 to 2n.

Let's look at a series of perfect shuffles for i = 15. Remember, this means that the cards that move will be card number 1 through card number 14.

14 13 11 7 14
13 11 7 14 13
12 9 3 6 12
11 7 14 13 11
10 5 10 5 10
9 3 6 12 9
8 1 2 4 8
7 14 13 11 7
6 12 9 3 6
5 10 5 10 5
4 8 1 2 4
3 6 12 9 3
2 4 8 1 2
1 2 4 8 1

The first column is the starting stack; and each subsequent column is the result of shuffling the previous stack. After four shuffles we are back where we started.

We can decompose the sequence of positions to form a number of cycles. (Just read ACROSS the columns above to see where the cards end up.)

( 1 2 4 8 )
( 3 6 12 9 )
( 5 10 )    
( 7 14 13 11 )

You will quickly observe that:

The number of shuffles required will always be the least common multiple of the length of the cycles.

 
Home
 
Shuffle Problem
Initial Ideas
Permutation
Cycle Length
Groups
 
Last modified:
 
© 2006
Peter C. Scott
 
Valid CSS!
 
Valid XHTML 1.1!