The mathematics of perfect shuffles |
| |
| Authors: | Persi Diaconis RL Graham William M Kantor |
| |
| Institution: | 1. Stanford University, Stanford, California 94305 U.S.A.;2. Harvard University, Cambridge, Massachusetts 02138 U.S.A.;3. Bell Laboratories, Murray Hill, New Jersey 07974 U.S.A.;4. Stanford University, Stanford, California 94305 U.S.A.;5. University of Oregon, Eugene, Oregon 97403 U.S.A.;6. Bell Laboratories, Murray Hill, New Jersey 07974 U.S.A. |
| |
| Abstract: | There 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). |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
