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
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