# A perfect $(n,k)$ shuffle function

Suppose you have a deck of $n$ cards; e.g., $n{=}12$: $$(1,2,3,4,5,6,7,8,9,10,11,12) \;.$$ Cut the deck into $k$ equal-sized pieces, where $k|n$; e.g., for $k{=}4$, the $12$ cards are partitioned into $4$ piles, each of $m=n/k=3$ cards: $$\left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \\ \end{array} \right) \;.$$ Now perfectly shuffle them by selecting the top card from stack $1$, the top card from stack $2$, and so on, walking down the columns of the matrix above, resulting in this shuffled deck of cards: $$(1,4,7,10,2,5,8,11,3,6,9,12) \;.$$ Continue in this manner until the deck of cards returns to its initial sorting: $$\left( \begin{array}{cccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 1 & 4 & 7 & 10 & 2 & 5 & 8 & 11 & 3 & 6 & 9 & 12 \\ 1 & 10 & 8 & 6 & 4 & 2 & 11 & 9 & 7 & 5 & 3 & 12 \\ 1 & 6 & 11 & 5 & 10 & 4 & 9 & 3 & 8 & 2 & 7 & 12 \\ 1 & 5 & 9 & 2 & 6 & 10 & 3 & 7 & 11 & 4 & 8 & 12 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \end{array} \right) \;.$$ Here, for $n{=}12$ cards partitioned into $k{=}4$ parts, it requires $s{=}5$ perfect shuffles to cycle. Let us say that $f(n,k)=s$, i.e., $f(12,4)=5$. Similarly I can calculate that $$f(8,2)=3,\; f(18,3)=16,\; f(33,3)=8, \; f(52,2)=8,$$ etc. The last represents a perfect "outer-shuffle" of a standard $52$-card deck, which is known to take $8$ shuffles to cycle. It seems likely this function is known to combinatorialists:

Q. What is $f(n,k)$?

• Seems to be the order of $k$ mod $n-1$. (This is well known for the usual perfect outer shuffle, and seems numerically to work in your other examples.) – Lucia Nov 22 '14 at 3:08
• If you label the cards $0$ to $n-1$ then your shuffle corresponds to multiplying card $i$ by the inverse of $k$ modulo $n-1$. Thus it returns to the original configuration in the order of $k^{-1}$ mod $n-1$ steps. But this is the same as the order of $k$ mod $n-1$. – Lucia Nov 22 '14 at 3:15

This is just my comment above, which seems to answer the question. Label the cards from $0$ to $n-1$. Then, with $m=n/k$, the shuffle in the question corresponds to multiplying card $i$ by $m$ (taken mod $n-1$). Thus repeating the shuffle $r$ times amounts to multiplying by $m^r \pmod{n-1}$, which returns us to the original configuration after the order of $m \pmod{n-1}$ times. Since $mk\equiv 1\pmod{n-1}$, this is also the order of $k \pmod{n-1}$. For more information on perfect shuffles see Diaconis, Graham, Kantor.
• So for $k{=}4$ and $n{-}1=11$, $4^2 \equiv 5$, $4^3 \equiv 9$, $4^4 \equiv 3$, $4^5 \equiv 1$. So $f(12,4)=5$. Nice! – Joseph O'Rourke Nov 22 '14 at 12:12