Riffle shuffle permutation

In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is one of the permutations of a set of $n$ items that can be obtained by a single riffle shuffle, in which a sorted deck of $n$ cards is cut into two packets and then the two packets are interleaved (e.g. by moving cards one at a time from the bottom of one or the other of the packets to the top of the sorted deck). Beginning with an ordered set (1 rising sequence), mathematically a riffle shuffle is defined as a permutation on this set containing 1 or 2 rising sequences.^[1] The permutations with 1 rising sequence are the identity permutations.

As a special case of this, a $(p,q)$ -shuffle, for numbers $p$ and $q$ with $p+q=n$ , is a riffle in which the first packet has $p$ cards and the second packet has $q$ cards.^[2]

Combinatorial enumeration

Since a $(p,q)$ -shuffle is completely determined by how its first $p$ elements are mapped, the number of $(p,q)$ -shuffles is ${\binom {p+q}{p}}.$

However, the number of distinct riffles is not quite the sum of this formula over all choices of $p$ and $q$ adding to $n$ (which would be $2^{n}$ ), because the identity permutation can be represented in multiple ways as a $(p,q)$ -shuffle for different values of $p$ and $q$ . Instead, the number of distinct riffle shuffle permutations of a deck of $n$ cards, for $n=1,2,3,\dots$ , is

1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... (sequence A000325 in the OEIS)

More generally, the formula for this number is $2^{n}-n$ ; for instance, there are 4503599627370444 riffle shuffle permutations of a 52-card deck.

The number of permutations that are both a riffle shuffle permutation and the inverse permutation of a riffle shuffle is^[3] ${\binom {n+1}{3}}+1.$ For $n=1,2,3,\dots$ , this is

1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... (sequence A050407 in the OEIS)

and for $n=52$ there are exactly 23427 invertible shuffles.

Random distribution

The Gilbert–Shannon–Reeds model describes a random probability distribution on riffle shuffles that is a good match for observed human shuffles.^[4] In this model, the identity permutation has probability $(n+1)/2^{n}$ of being generated, and all other riffle permutations have equal probability $1/2^{n}$ of being generated. Based on their analysis of this model, mathematicians have recommended that a deck of 52 cards be given seven riffles in order to thoroughly randomize it.^[5]

Permutation patterns

A pattern in a permutation is a smaller permutation formed from a subsequence of some $k$ values in the permutation by reducing these values to the range from 1 to $k$ while preserving their order. Several important families of permutations can be characterized by a finite set of forbidden patterns, and this is true also of the riffle shuffle permutations: they are exactly the permutations that do not have 321, 2143, and 2413 as patterns.^[3] Thus, for instance, they are a subclass of the vexillary permutations, which have 2143 as their only minimal forbidden pattern.^[6]

Perfect shuffles

A perfect shuffle is a riffle in which the deck is split into two equal-sized packets, and in which the interleaving between these two packets strictly alternates between the two. There are two types of perfect shuffle, an in shuffle and an out shuffle, both of which can be performed consistently by some well-trained people. When a deck is repeatedly shuffled using these permutations, it remains much less random than with typical riffle shuffles, and it will return to its initial state after only a small number of perfect shuffles. In particular, a deck of 52 playing cards will be returned to its original ordering after 52 in shuffles or 8 out shuffles. This fact forms the basis of several magic tricks.^[7]

Algebra

Riffle shuffles may be used to define the shuffle algebra. This is a Hopf algebra where the basis is a set of words, and the product is the shuffle product denoted by the sha symbol ш, the sum of all riffle shuffles of two words.

In exterior algebra, the wedge product of a $p$ -form and a $q$ -form can be defined as a sum over $(p,q)$ -shuffles.^[2]

References

^ Aldous, David; Diaconis, Persi (1986), "Shuffling cards and stopping times" (PDF), The American Mathematical Monthly, 93 (5): 333–348, doi:10.2307/2323590, JSTOR 2323590, MR 0841111
^ ^a ^b Weibel, Charles (1994). An Introduction to Homological Algebra, p. 181. Cambridge University Press, Cambridge.
^ ^a ^b Atkinson, M. D. (1999), "Restricted permutations", Discrete Mathematics, 195 (1–3): 27–38, doi:10.1016/S0012-365X(98)00162-9, MR 1663866.
^ Diaconis, Persi (1988), Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Hayward, CA: Institute of Mathematical Statistics, ISBN 0-940600-14-5, MR 0964069.
^ Kolata, Gina (January 9, 1990), "In Shuffling Cards, 7 Is Winning Number", New York Times.
^ Claesson, Anders (2004), Permutation patterns, continued fractions, and a group determined by an ordered set, Ph.D. thesis, Department of Mathematics, Chalmers University of Technology, CiteSeerX 10.1.1.103.2001.
^ Diaconis, Persi; Graham, R. L.; Kantor, William M. (1983), "The mathematics of perfect shuffles", Advances in Applied Mathematics, 4 (2): 175–196, CiteSeerX 10.1.1.77.7769, doi:10.1016/0196-8858(83)90009-X, MR 0700845.

[1] Aldous, David; Diaconis, Persi (1986), "Shuffling cards and stopping times" (PDF), The American Mathematical Monthly, 93 (5): 333–348, doi:10.2307/2323590, JSTOR 2323590, MR 0841111

[Weibel-2] Weibel, Charles (1994). An Introduction to Homological Algebra, p. 181. Cambridge University Press, Cambridge.

[a99-3] Atkinson, M. D. (1999), "Restricted permutations", Discrete Mathematics, 195 (1–3): 27–38, doi:10.1016/S0012-365X(98)00162-9, MR 1663866.

[4] Diaconis, Persi (1988), Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Hayward, CA: Institute of Mathematical Statistics, ISBN 0-940600-14-5, MR 0964069.

[5] Kolata, Gina (January 9, 1990), "In Shuffling Cards, 7 Is Winning Number", New York Times.

[6] Claesson, Anders (2004), Permutation patterns, continued fractions, and a group determined by an ordered set, Ph.D. thesis, Department of Mathematics, Chalmers University of Technology, CiteSeerX 10.1.1.103.2001.

[7] Diaconis, Persi; Graham, R. L.; Kantor, William M. (1983), "The mathematics of perfect shuffles", Advances in Applied Mathematics, 4 (2): 175–196, CiteSeerX 10.1.1.77.7769, doi:10.1016/0196-8858(83)90009-X, MR 0700845.

[1]

[2]

[3]

[4]

[5]

[6]

[7]