Riffle shuffle permutation

Short description: Ordering obtained by a single shuffle

In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is a permutation of a set of $n$ ordered items that can be obtained by a single riffle shuffle, in which a sorted deck of $n$ cards (increasing top-to-bottom) 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.

Considering a permutation as a bijective function

$\pi$

from the set

$\{1,2,\dots ,n\}$

to itself, a riffle shuffle is defined as containing only 1 or 2 maximal rising sequences, meaning

$\{1,2,\dots ,n\}$

can be decomposed into two disjoint subsets

$\{i_1<\cdots <i_p\}$

and

$\{j_1<\cdots <j_q\}$

with

$\pi (i_1)<\pi (i_2)<\cdots <\pi (i_p)$

and

$\pi (j_1)<\pi (j_2)<\cdots <\pi (j_q)$

.

A permutation with only 1 maximal rising sequence is the identity permutation.

The inverse permutation

$\tau ={\pi }^{-1}$

of a riffle shuffle is known as Grassmannian permutation, defined by

$\tau (1)<\dots <\tau (p)\text{and}\tau (p+1)<\dots <\tau (p+q),$

having one descent

$\tau (p)>\tau (p+1)$

, or zero descents if

$\tau$

is the identity. In Schubert calculus, these index Schubert varieties in a Grassmannian space.

A permutation $\pi$ which is both a riffle shuffle and Grassmannian (i.e. both $\pi$ and its inverse are Grassmannian, or equivalently both are riffle shuffles), is called bigrassmannian or an invertible shuffle.

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 $$(\genfrac{}{}{0ex}{}{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 bigrassmannian permutations is $$(\genfrac{}{}{0ex}{}{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 bigrassmannian 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.

Perfect shuffles

Main article: Faro shuffle

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 permutation

the basis of several magic tricks.

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.

See also

• Gilbreath permutations, the permutations formed by reversing one of the two packets of cards before riffling them