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).
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.
Since a (p,q)-shuffle is completely determined by how its first p elements are mapped, the number of (p,q)-shuffles is
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 2n), 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, ..., is
More generally, the formula for this number is 2n − 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
For n = 1, 2, 3, ..., this is
and for n = 52 there are exactly 23427 invertible shuffles.
The Gilbert–Shannon–Reeds model describes a random probability distribution on riffle shuffles that is a good match for observed human shuffles. In this model, the identity permutation has probability (n + 1)/2n of being generated, and all other riffle permutations have equal probability 1/2n 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.
...
Wikipedia