# Permutation decomposition

A perfect shuffle of a deck of cards can be represented by the following permutation $f\in S_{52}$: $$f(x) =\left\{ \begin{array}{ll} 2x-1 & \text{if }x\in\{1,\ldots,26\}\\ 2(x-26) &\text{if }x\in \{27,\ldots,52\} \end{array}\right.$$

I'm trying to show that if one performs 8 perfect shuffles of a deck of cards, then this returns the cards to their original position.

What I did was get some cycle decomposition:

(2 3 5 9 17 33 14 27) and (4 7 13 25 49 46 40 28) and

when I tried out starting with 6, I am getting a mess since f(31) = 10, but f(6) = 10

How many other cycle decompositions are there?

-
$f(6) = 2(6)-1 = 11$; what do you mean $f(6)=10$? You are doing well: the next cycle will be (6 11 21 41 30 8 15 29); the next card not yet dealt with is 10. – Arturo Magidin Feb 13 '12 at 2:09
OK, I will do 10, but how many Total cycle decompositions should I have? – James R. Feb 13 '12 at 2:36
the only fixed points are 1 and 52; each cycle will, hopefully, have 2, 4, or 8 elements. So anywhere between 7 and 16. Just go ahead and do it carefully. – Arturo Magidin Feb 13 '12 at 2:44

This can be proven, without having to deal with messy cycles.

Notice that the first and last elements are fixed. So we can ignore them.

Now, if you renumber so that 2 becomes 1, 3 becomes 2, etc till 51 becomes 50.

We are interested in a permutation which has the formula

$$x \to 2x \mod 51$$

Thus after $n$ steps, we have that

$$x \to 2^n x \mod 51$$

Since $2^8 = 1 \mod 51$, you are done.

-