Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0002-9947-1985-0773053-5
PII: S 0002-9947(1985)0773053-5
Article copyright: © Copyright 1985 American Mathematical Society