The mathematics of perfect shuffles

AbstractThere are two ways to perfectly shuffle a deck of 2n cards. Both methods cut the deck in half and interlace perfectly. The out shuffle O leaves the original top card on top. The in shuffle I leaves the original top card second from the top. Applications to the design of computer networks and card tricks are reviewed. The main result is the determination of the group 〈 I, O 〉 generated by the two shuffles, for all n. If 2n is not a power of 2, and if 2n ≠ 12,24, then 〈 I, O 〉 has index 1, 2, or 4 in the Weyl group Bn (the group of all 2nn! signed n × n permutation matrices). If 2n = 2k, then 〈 I, O 〉 is isomorphic to a semi-direct product of Z2k and Zk. When 2n = 24, 〈 I, O 〉 is isomorphic to a semi-direct product of Z211 and M12, the Mathieu group of degree 12. When 2n = 12, 〈 I, O 〉 is isomorphic to a semi-direct product of Z26 and the group PGL(2,5) of all linear fractional transformations over GF(5)