Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

A bijective proof of Stanley’s shuffling theorem


Author: I. P. Goulden
Journal: Trans. Amer. Math. Soc. 288 (1985), 147-160
MSC: Primary 05A15; Secondary 05A30, 06A99
DOI: https://doi.org/10.1090/S0002-9947-1985-0773053-5
MathSciNet review: 773053
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05A15, 05A30, 06A99

Retrieve articles in all journals with MSC: 05A15, 05A30, 06A99


Additional Information

Article copyright: © Copyright 1985 American Mathematical Society