A bijective proof of Stanley’s shuffling theorem

Abstract:

For two permutations $\sigma$ and $\omega$ on disjoint sets of integers, consider forming a permutation on the combined sets by "shuffling" $\sigma$ and $\omega$ (i.e., $\sigma$ and $\omega$ appear as subsequences). Stanley [10], by considering $P$-partitions and a $q$-analogue of Saalschutz’s $_3{F_2}$ summation, obtained the generating function for shuffles of $\sigma$ and $\omega$ with a given number of falls (an element larger than its successor) with respect to greater index (sum of positions of falls). It is a product of two $q$-binomial coefficients and depends only on remarkably simple parameters, namely the lengths, numbers of falls and greater indexes of $\sigma$ and $\omega$. A combinatorial proof of this result is obtained by finding bijections for lattice path representations of shuffles which reduce $\sigma$ and $\omega$ to canonical permutations, for which a direct evaluation of the generating function is given.