In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is a permutation of a set of n {\displaystyle n} ordered items that can be obtained by a single riffle shuffle, in which a sorted deck of n {\displaystyle 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 ) {\displaystyle (p,q)} -shuffle, for numbers p {\displaystyle p} and q {\displaystyle q} with p + q = n {\displaystyle p+q=n} , is a riffle in which the first packet has p {\displaystyle p} cards and the second packet has q {\displaystyle q} cards.
Considering a permutation as a bijective function π {\displaystyle \pi } from the set { 1 , 2 , … , n } {\displaystyle \{1,2,\ldots ,n\}} to itself, a riffle shuffle is defined as containing only 1 or 2 maximal rising sequences, meaning { 1 , 2 , … , n } {\displaystyle \{1,2,\ldots ,n\}} can be decomposed into two disjoint subsets { i 1 < ⋯ < i p } {\displaystyle \{i_{1}<\cdots <i_{p}\}} and { j 1 < ⋯ < j q } {\displaystyle \{j_{1}<\cdots <j_{q}\}} with π ( i 1 ) < π ( i 2 ) < ⋯ < π ( i p ) {\displaystyle \pi (i_{1})<\pi (i_{2})<\cdots <\pi (i_{p})} and π ( j 1 ) < π ( j 2 ) < ⋯ < π ( j q ) {\displaystyle \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 τ = π − 1 {\displaystyle \tau =\pi ^{-1}} of a riffle shuffle is known as Grassmannian permutation, defined by τ ( 1 ) < … < τ ( p ) and τ ( p + 1 ) < … < τ ( p + q ) , {\displaystyle \tau (1)<\ldots <\tau (p)\ \ \ {\text{and}}\ \ \ \tau (p+1)<\ldots <\tau (p+q),} having one descent τ ( p ) > τ ( p + 1 ) {\displaystyle \tau (p)>\tau (p+1)} , or zero descents if τ {\displaystyle \tau } is the identity. In Schubert calculus, these index Schubert varieties in a Grassmannian space. A permutation π {\displaystyle \pi } which is both a riffle shuffle and Grassmannian (i.e. both π {\displaystyle \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 ) {\displaystyle (p,q)} -shuffle is completely determined by how its first p {\displaystyle p} elements are mapped, the number of ( p , q ) {\displaystyle (p,q)} -shuffles is
( p + q p ) . {\displaystyle {\binom {p+q}{p}}.}
… excerpt ends here. Continue reading the full article.
