Most magic tricks rely on some kind of sleight of hand. However, some tricks are powered by maths!
A very fruitful way of analyzing card shuffles is by using the idea of “permutations". Permutations are important objects that occur in various parts of maths. We will look at them in the context of card shuffling. Many interesting patterns emerge, and we will only touch the tip of the iceberg today.
Suppose you have a set of ordered objects. A permutation of this set is a reordering of the objects. For example, a permutation of a deck of cards ordered from top to bottom is simply a shuffle of the cards. Note that in general, a permutation can be defined as a relabelling of objects, so an order is not necessary.
Let’s discuss two ways of writing permutations.
The first way is the two-line notation. Say you have the cards from top to bottom Ace, two, three. Say Ace is 1. Suppose that after a shuffle \(\sigma\), we have from top to bottom two, three, Ace. The two-line notation keeps the original positions on the first line and the new positions in the second line.
\[\sigma = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{array} \right).\]
A second way of writing permutations is the function notation. In the same situation, we could write \(\sigma(1)=3\), \(\sigma(2)=1\) and \(\sigma(3)=2\).
As a first indication of why permutations give a useful perspective, we note that permutations can be done after another and the result is still a permutation. Let \(\tau\) be the permutation on the same three cards given \(\tau(1)=2\), \(\tau(2)=3\) and \(\tau(3)=1\). Consider \(\tau\sigma\) which is performing \(\sigma\) first and then \(\tau\). To find out what the effect of this composite permutation is on \(1\), we can visualize it as follows: \[1\mapsto3=\sigma(1)\mapsto\tau(\sigma(1))=\tau(3)=1.\]
This shows that the function notation plays very nicely with composing permutations. By the way, if we work out the entire \(\tau\sigma\) in this fashion, we find that \[\tau\sigma = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \\ \end{array} \right).\]
In other words, \(\tau\) has “negated" the effect of \(\sigma\)!
We have a few more examples of how the notations are used. If you want to learn a magic trick or two - see problems 7 to 11.