 Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum  # 6.4 Card Shuffling

## PERMUTATIONS

• The symmetries of a geometric object can be expressed as permutations of elements.
• Permutations can form a group, as symmetries do.

Let’s return to the equilateral triangle group that we studied earlier. We have been saying all along that the power of group theory lies in its capacity to reveal deep connections between seemingly unrelated things. We can catch a small glimpse of this by re-examining the motions that make up the equilateral triangle group.

Remember, to keep track of the reflections and rotations that make up the equilateral triangle group, we labeled the vertices A, B, and C. We can express all of the symmetries shown earlier by using just these labels. As a convention, we’ll express each configuration of the triangle as some sequence of A, B, and C, with the first letter of each sequence corresponding to the vertex at the top of the triangle, the second letter representing the right vertex, and the third letter representing the left vertex. Basically, this is just a clockwise sequence, starting from the top. Applying this convention yields the following sequences, shown corresponding to the motions that produced them. Each of these motions has the effect of permuting the labels of the vertices. For example, a reflection over a vertical line through the top vertex of the equilateral triangle keeps A in the same (first) position in the label sequence, while switching the positions of vertices B and C. This motion takes ABC and gives us ACB.

Perhaps we don’t really even need an actual triangle to have a group. In fact, let’s forget about the triangle for a moment and simply look at the ways in which we can arrange three objects. Just for fun, let’s think of this as the ways in which we can stack three different-flavored pancakes, one apple (A), one banana (B), and one chocolate (C). We can use combinatorics to figure out how many different arrangements there are. Because these are ordered permutations of three objects, we know there will be 3! (3 × 2 × 1) or six arrangements. They are:

ABC
ACB
BAC
BCA
CAB
CBA

If we look at these sequences in terms of how such permutations are created, instead of simply enumerating the specific arrangements, we will see an interesting result. For the sake of simplicity, let’s say that each permutation action starts on ABC. Here are our actions: Let’s see if this set of permutations forms a group under the operation of "followed by." It’s clear that we have an Identity motion (P6). The easiest way to check for closure, inverses, and associativity will be to form a table, as we did with the equilateral triangle group. Note that as we perform these combined movements, the motions represented across the top row of the table are done first, followed by the motions in the left column.

For instance, P5 switches A with C and C with A while leaving B untouched. Doing this twice in succession yields the same result as doing nothing, so P5 serves as its own inverse. The same can be said for P1 and P2. What happens when we perform the P3 motion twice in succession? P3 replaces A with B, B with C, and C with A. Starting from ABC, P3 creates BCA, so applying this transformation to BCA yields CAB, the same result obtained from performing P4 once. In other words, P3 followed by P3 is equivalent to P4, which demonstrates that P3 is not its own inverse. However, a little bit further examination reveals that P4 undoes the changes that P3 creates, and, thus, serves as its inverse. As we fill in this table, we find that every combination of two permutations gives another permutation, thereby confirming that the set of permutations of three objects is closed. Furthermore, we can see that each permutation has an inverse. Finally, by using the reasoning of the previous examples, namely that we should be able to combine motions in any way we choose without affecting the result, we can convince ourselves that the elements are associative under the operation "followed by."

Having confirmed that the four requirements are met, we see that the set of permutations of three objects indeed forms a group. In other words, the possible ways in which we can stack three distinguishable pancakes forms a group. It’s interesting to note that the number of elements in this group is the same as the number of elements in the group of symmetries of the equilateral triangle—six. Furthermore, if we examine the table we obtained for the triangle with the table we obtained for the permutations, we find that they have identical structure. This suggests to us that these two situations are both manifestations of the same fundamental structure. In other words, what do equilateral triangles have to do with stacks of three pancakes? They both have the same group structure!

This is, of course, no coincidence and is merely an example of a much broader observation, first documented by Arthur Cayley, an influential British mathematician working in the late 1800s. Cayley proved that every finite group of symmetries can be represented by a group of permutations. When two groups, such as a group of symmetries and a group of permutations, have the same structure, we say that they are isomorphic to each other.

Now, to be clear, this does not mean that the group of symmetries of a square, for instance, will have the same structure as the set of all permutations of four objects. This is patently obvious from the fact that a square has eight symmetries, whereas there are twenty-four possible permutations of four objects. Cayley’s Theorem does assure us, however, that there is some group of permutations that contains a subgroup (that is, a subset of the group that does itself satisfy all the group axioms) that corresponds with the eight symmetries of a square. In this case, the group of twenty-four permutations of four objects suffices as the broader group that contains the corresponding subgroup. This connection between geometric symmetries and permutations illustrates but one example of the connecting power of group theory.

## THE PERFECT SHUFFLE

• The symmetries of permutations are evident in card shuffling.
• Eight perfect "riffle" shuffles will return a standard deck of cards to the order in which it started.

Let’s consider the connection between permutations and group theory in a little bit more detail. In the example above, we considered permutations of three objects, modeled by a stack of pancakes. Increase the number of pancakes to 52 and we can (and probably should!) shift our thinking from food to cards. We may not normally consider a deck of cards to have symmetry, but if we view symmetries as permutations, and permutations as shuffles, we see yet another fundamental connection made possible by group theory.

As it turns out, we can use group theory to determine when a deck of cards has been sufficiently shuffled. Let’s take a step back, though—generally, when we think of a group, we’re thinking of some kind of symmetry, and to have a symmetry, something must remain invariant. So, what remains invariant when a deck of cards is shuffled? Isn’t the point of shuffling to mess everything up? When we shuffle a deck of cards, what remains invariant is the deck itself. Although it will probably end up in a different order than when we started, it remains a deck of cards. While there are only six permutations of three pancakes, you might well imagine that there are a staggering number of permutations of a deck of 52 cards. A good shuffle would make each of the billions of possible deck orderings equally likely. Is there a technique that can accomplish this?

If you were able to perform a perfect shuffle, one in which the deck is cut into two stacks of 26 cards which are then riffled together one card at a time alternately from each stack, the result would be anything but random. The cards would be interleaved in some mathematically predictable way. The easiest way to analyze this is to assume that the deck you start with is in ascending order (2345678910JQKA) for each suit. After one perfect shuffle, this sequence will be messed up, but in a very particular way. To get a better idea of what happens, let’s simplify our example to just the lowest ten cards of a suit, with the ace designated as "1."

After a perfect cut, we have two stacks, 1 2 3 4 5 and 6 7 8 9 10. Riffling these together perfectly, starting with the left stack, gives 1 6 2 7 3 8 4 9 5 10. If we were to perform a second perfect riffle shuffle, the cut would give us:

1 6 2 7 3 and 8 4 9 5 10

. . . and riffling these together would give us: 1 8 6 4 2 9 7 5 3 10.

Cutting again gives us:

1 8 6 4 2 and 9 7 5 3 10

. . . which gives us 1 9 8 7 6 5 4 3 2 10 when riffled perfectly back together. Note that all of the sequences of ten cards that we have seen so far are quite predictable provided we know the starting order and perform perfect riffle shuffles every time.

Cutting once again gives us 1 9 8 7 6 and 5 4 3 2 10, which, combined, yield the sequence 1 5 9 4 8 3 7 2 6 10.

In yet another perfect shuffle: 1 5 9 4 8 and 3 7 2 6 10 come back together in the sequence 1 3 5 7 9 2 4 6 8 10.

Okay, just once more. When riffled perfectly, this last action produces the sequence 1 2 3 4 5 6 7 8 9 10, which was our original ordering! We have found that six perfect riffle shuffles return our ten-card deck to its original ordering. In addition to our previous observation that perfect riffle shuffles do not randomize a deck, we now see that if you perform six of them, the deck actually isn’t shuffled at all! You might think that a full deck of 52 cards would take many more shuffles than this to achieve the same result, but actually it only takes eight!

This means that, if we want to shuffle a deck of cards in a way that is mathematically unpredictable—in other words, truly random—then we must be imperfect shufflers. We should make a certain amount of errors, but not too many, in our shuffling process. Each of these errors will propagate through other shuffles until the deck is truly randomized. The number of shuffles required to randomize a full deck of 52 cards, depending on our measure of randomness (and that’s a whole other story!), is then either six or seven.

The unexpected connection between symmetries, permutations, and card shuffling is just a small sampling of the broad explanatory power of group theory. Symmetry and group theory not only tell us about patterns and shuffles, they can also be used to tackle some of the more abstract challenges that arise in mathematics itself. One of the classic examples of this is the story of Evariste Galois and the remarkable connections he made in an attempt to solve a problem that had vexed some of the greatest mathematical thinkers for centuries.