Here’s a shuffle I’ve not seen before:
- Take an ordinary deck of 52 cards and place them, face up, in the following pattern:
Going from the top of the deck to the bottom, placing cards down left-to-right, put 13 cards in the top row:
11 cards in the next row:
then 9 cards in the next row:
then 7 cards in the next row:
then 5 cards in the next row:
then 3 cards in the next row:
and finally, the remaining 4 cards in the last row:
- Now, take the left-most card in each row and move it to the right of the others (effectively, this is a cyclic shift of that row of cards to the left).
- Finally, reassemble the deck by reversing the order of the placement.
In memory of the great German mathematician Edmund Landau (1877-1938, see also this bio), I call this the Landau shuffle. As with any card shuffle, this shuffle permutes the original ordering of the cards. To restore the deck to it’s original ordering you must perform this shuffle exactly 180180 times. (By the way, this is called the order of the shuffle.) Yes, one hundred eighty thousand, one hundred and eighty times. Moreover, no other shuffle than this Landau shuffle will require more repetitions to restore the deck. So, in some sense, the Landau shuffle is the shuffle that most effectively rearranges the cards.
Now suppose we have a deck of (distictly labeled) cards, where is an integer. The collection of all possible shuffles, or permutations, of this deck is denoted and called the symmetric group. The above discussion leads naturally to the following question(s).
Question: What is the largest possible order of a shuffle of this deck (and how do you construct it)?
This requires a tiny bit of group theory. You only need to know that any permutation of symbols (such as the card deck above) can be decomposed into a composition or product) of disjoint cycles. To compute the order of an element , write that element in disjoint cycle notation. Denote the lengths of the disjoint cycles occurring in as , where are integers forming a partition of : . Then the order of is known to be given by , where LCM denotes the least common multiple.
The Landau function is the function that returns the maximum possible order of an element . Landau introduced this function in a 1903 paper where he also proved the asymptotic relation .
Example: If then note and that .
Oddly, my favorite mathematical software program SageMath does not have an implementation of the Landau function, so we end with some SageMath code.
L = Partitions(n).list()
lcms = [lcm(P) for P in L]
Here is an example (the time is included to show this took about 2 seconds on my rather old mac laptop):
sage: time landau_function(52)
CPU times: user 1.91 s, sys: 56.1 ms, total: 1.97 s
Wall time: 1.97 s