In the Plus article, The magic of shuffling, we found out what a magician can do with a card shuffle. But what might a mathematician do when shuffling cards? To find out we asked Cheryl Praeger, from the University of Western Australia. It was Praeger who first intrigued us in card shuffling with her fascinating talk at the Isaac Newton Institute last year. (You can watch the lecture online here.) Praeger works in group theory, an area of mathematics that is motivated by symmetry. We spoke to her last year after she returned to Australia, and she revealed the fascinating insights group theory brings to understanding shuffling cards.

What could a mathematician do with a perfect shuffle?

A mathematician thinks of the cards in a pack, not in terms of their face value and suit, but in terms of their position in the original pack. So if you have a pack of 52 cards, label each card 0 to 51 by its position (the top card is labelled 0, rather than 1, as this makes the maths simpler). "I might want to know where each of these cards might lie after different combinations of the shuffles," says Praeger. "So each outcome is like a reordering, a permutation, of the cards in the pack. I want to know how many different permutations there are. And perhaps what sort of structure this whole set of reorderings, this permutation group, has."

The first things we can do is count all the possible permutations you can create by shuffling the cards. If we start with a pack of k cards, then we know there are k different positions in the shuffled pack to place the top card. Then there's only k-1 slots left for the second card, k-2 slots for the third card, and so on. The total number of possible reorderings is k x (k-1) x (k-2) x ... x 2 x 1, otherwise known as the factorial of k, written k!. The collection of all possible permutations of a pack of k cards is called the symmetric group – and the size of the symmetric group for a pack of k cards is k!. For example, for a pack consisting of 6 cards, there are 6! = 6x5x4x3x2x1 = 720 possible permutations in the symmetric group.

Praeger, however, is interested in just those permutations of the cards that you can get by using perfect shuffles, when a pack of cards is exactly split in half and the cards from each half perfectly interleaved one by one. There are two types of perfect shuffles: an out-shuffle, where the top and bottom cards are fixed, and an in-shuffle, where the top and bottom cards are moved in by one position in the shuffled pack. (You can read more about perfect shuffles here.) You could do just one in-shuffle, or, say, three in-shuffles followed by an out-shuffle, or, perhaps, eight out-shuffles, one after the other. Any combination of the two types of perfect shuffles is allowed.

The set of permutations of the pack of cards that you get from all the possible combinations of in- and out-shuffles is called the shuffle group. This doesn't include every possible permutation of the pack of cards; the shuffle group is smaller than the symmetric group. For example a pack of six cards has 720 permutations in the symmetric group, but only 24 possible permutations in the shuffle group. But both groups share an important mathematical property.

The shuffle group

Both the shuffle group and the symmetric group have what is called a group structure. In maths, a group is a collection of objects that combine in a specific way that satisfies four rules (you can read the details here). In our shuffle group , for example, the objects are shuffles generated from some combination of the two types of perfect shuffles. The shuffle group is closed: if you combine any two shuffles from the group, the resulting shuffle will then also be a combination of perfect shuffles, and so is also in the shuffle group. And every shuffle has an inverse – so that a shuffle, combined with its inverse, effectively leaves the pack of cards unchanged. For example, we saw in the previous article that, for a pack of 52 cards, a single out-shuffle, combined with 7 more out-shuffles gives you back your original pack order. So the inverse of a single out-shuffle is a combination of 7 out-shuffles. A shuffle group, for any evenly sized pack of cards, and the larger symmetric group, satisfy all the rules of being a mathematical group.

The key tool of a group theorist is to break a finite group down into its basic building blocks, called the simple groups. "Typically you can split a group up into two parts, so that each of the parts is a group, and you can continue to do this" says Praeger. "It really is just like a tree branching and branching and branching, until you reach a stage where it is not possible to split it any more, and that’s like getting to the leaves of the tree. And when you find the leaves of the tree, the groups that you've reached are what we call the simple ones, because they can’t be divided any further." (You can read more about simple groups here.)

Studying a group in this way reveals lots of useful information. For example you can tell how big the group is by multiplying together the sizes of all the simple groups on the leaves of that tree. "[Breaking a group down into its simple groups] is a very useful tool and it’s one of the first things a group theorist is going to look for."

Central symmetry

An intriguing early result about shuffle groups was proven by the mathematicians Persi Diaconis, Ronald Graham and William Kantor in the 1980s. "A very beautiful property they saw and explained is what they called central symmetry," says Praeger. "You think of the top and the bottom card in the pack as being associated. After any sequence of perfect shuffles – suppose the top card went down to the third position, and then the bottom card would come up to the third last position – there's this sort of symmetry, that whatever one of the pair does, the other mimics it." So, if after a sequence of perfect shuffles the top card ends up a certain number of cards from the top, you know that the bottom card ends up same number of cards from the bottom.

The same thing happens for every such symmetrical pair of cards in the pack: the pairs located the same distance around the centre of the pack are linked, and always get moved together by the in- and out-shuffles. "The pairs get shuffled around together, it's like they’ve got some sort of invisible bonds connecting them. Whereas a completely random shuffle, not one of these perfect ones, wouldn't have that property at all." This central symmetry property puts some real restrictions on the possible permutations of a pack of cards you can have in your shuffle group.

Diaconis, Graham and Kantor showed that the shuffle group of a pack having central symmetry implies that its simple groups are very restricted. One impact of this is on the size of the shuffle groups, which depends on the sizes of the associated simple groups. For most sizes of packs of cards the shuffle groups would be enormous (relative to the size of the pack, despite being much smaller than the full symmetric group). And typically the size of the shuffle group grows exponentially with the size of the pack.

If you have a pack of 6 cards, you have 24 possible permutations in its shuffle group. A pack of 10 cards has 1,920 permutations in its shuffle group. And a pack of 26 cards has over 25 trillion possible permutations in its shuffle group. These numbers illustrate that the size of the shuffle group grows exponentially as you increase the size of your pack of cards.

But an amazing thing happens when the size of the pack is a power of 2, something mathematicians call the power case. A 14 card pack has over 320,000 permutations in the shuffle group. But the shuffle group for a 16 card pack, and remember 16 is 2⁴, has just 64 possible permutations! A pack of 30 cards has quadrillions (10¹⁵) of possible permutations using combinations of in- and out- shuffles, but a 32 card pack, and again remember 32 is 2⁵, has just 160 possible permutations in the shuffle group. When the size of the pack is a power of 2, it gives a dramatically smaller shuffle group.

"The power case was incredible," says Praeger. "In that case the size of the shuffle group is exponentially smaller than the typical size." She explains that in the power case the only building blocks of the shuffle groups are something called cyclic groups, which are the smallest simple groups. The building blocks being so much smaller means the shuffle group is dramatically smaller too: "There's nothing big about it at all!" (You can find out more about cyclic groups here.)

Many hands make interesting work

It turns out a similar power case is true for many-handed perfect shuffles, something Praeger investigated with her colleagues Carmen Amarra and Luke Morgan in 2019. When they were visiting with her research group, Praeger remembered a piece of paper covered with data from long ago hidden at the bottom of a drawer: "It had been sitting in my drawer for decades!" Now was a perfect time to investigate.

The data was from computer experiments conducted by Kent Morrison and John Cannon in the 1980s for many-handed shuffles. Imagine that instead of dividing up the pack of cards into two equal piles, you instead divided it up into, say, three equal piles, and then perfectly interleaved those three piles. Or you divided the pack up into four piles, or seven, or 11 piles, and then perfectly shuffled the equal piles.

"But then there were a lot of questions that arose," says Praeger. "You divide your pack of cards into k equal piles – and then what?" You could pick up the cards one at a time from the top of each pile in the order that the piles were split from the deck, then that might be like an out-shuffle. But what if you decided to start with the second pile, and then go to the 7th pile, and then the 15th pile, and then the 27th pile! There were now lots of possible orders in which you picked up your cards from the piles – what counted as a perfect shuffle when you were using many piles?

Praeger and her colleagues decided to think about a many-handed shuffle in a new way: they considered not only how many piles you split the pack into, but also how to specify the allowable orderings of the piles which determined the way you were alternating the cards in your shuffle. They labelled the top pile from the pack with 0, the second pile 1, and so on to the kth pile labelled with k-1. Then they could investigate the impact of the order in which you chose cards from the piles, on the reordering of the cards in the final shuffle.

With this new approach, Praeger, Amerra and Morgan proved something that had been suspected: that in some cases, something similar to the power case happened in this many-handed shuffling (you can read their paper here). "In my work with Carmen and Luke, when we were splitting up the cards into k piles of length n, we observed that there's a similar special case when the size of the piles is a power of the number of piles. So it's like the cards in the standard case being a power of 2: again you got a very, very small shuffle group."

Mathematicians had observed this power case for a many-handed shuffle, along with some experimental evidence that the shuffle groups seemed enormously larger outside of the power case. That the shuffle groups would be gigantic in all cases except the power case, for a many-handed shuffle, was stated in a conjecture by Morrison and another mathematician, Steve Medvedoff. Praeger and her colleagues were able to use their new approach to prove this conjecture about the non-power case for a lot of the many-handed possibilities. But many open questions still remain for proving this conjecture more generally, to cover the case of dividing the pack into an arbitrary number of piles for a many-handed shuffle.

Open questions and new horizons

Also, thanks to their new approach, Praeger, Carmen and Luke were able to discover some fascinating new results. Their new approach considered the permutations of the piles of cards when shuffling your pack. In particular, they discovered that the shuffle groups preserved many properties of the permutations of the piles that you allowed. If you had what is called a transitive permutation group of the piles in your allowed shuffles (which means you could get from one pile to any other pile using the permutations you were allowing of the piles in your many-handed shuffles) then your resulting shuffle group would also be transitive. There was a combination of shuffles you could use to move any card to any other position in the pack. This transitive property was just the first of some of the group properties that they found the shuffle groups preserved. And again, many open questions remain.

The mathematics of card shuffling is a great example of how mathematicians often work. In this case they started with perfect shuffles, arising from standard card games, where the deck is split into two piles, with two types of perfect shuffles - the in and out shuffle. Then, after exploring the maths of that setting, they generalised the setup to see how far these results can be extended: splitting the pack into three, four, or indeed any number of equal piles. They may have started with a simple pack of cards, at a table, playing with friends, but, as always, their eye is inevitably drawn to the mathematical horizon.

About this article

This article is based on a talk that was part of the Groups, representations and applications programme at the Isaac Newton Institute. You can find out more about the maths behind this programme here.

Cheryl Praeger

Cheryl Praeger is an Australian mathematician with a passion for the mathematics of symmetry, as measured mathematically by groups. Her research focuses on permutation groups and the symmetrical structures they act on, along with algorithmic and computational questions about groups. She is Emeritus Professor of Mathematics at the University of Western Australia and is so far the only pure mathematician to receive the Australian Prime Minister’s Prize for Science.

Rachel Thomas is Editor of Plus.

This article is part of our collaboration with the Isaac Newton Institute for Mathematical Sciences (INI), an international research centre and our neighbour here on the University of Cambridge's maths campus. INI attracts leading mathematical scientists from all over the world, and is open to all. Visit www.newton.ac.uk to find out more.