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

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

  • [1] George E. Andrews, Identities in combinatorics. I. On sorting two ordered sets, Discrete Math. 11 (1975), 97–106. MR 0389609,
  • [2] George E. Andrews, The theory of partitions, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. Encyclopedia of Mathematics and its Applications, Vol. 2. MR 0557013
  • [3] P. Cartier and D. Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, No. 85, Springer-Verlag, Berlin-New York, 1969 (French). MR 0239978
  • [4] H. W. Gould, A new symmetrical combinatorial identity, J. Combinatorial Theory Ser. A 13 (1972), 278–286. MR 0304193
  • [5] I. P. Goulden, A bijective proof of the $ q$-Saalschutz theorem (preprint).
  • [6] I. P. Goulden and D. M. Jackson, Combinatorial enumeration, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1983. With a foreword by Gian-Carlo Rota; Wiley-Interscience Series in Discrete Mathematics. MR 702512
  • [7] F. H. Jackson, Transformations of $ q$-series, Messenger of Math. 39 (1910), 145-153.
  • [8] Percy A. MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York, 1960. MR 0141605
  • [9] Lucy Joan Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966. MR 0201688
  • [10] Richard P. Stanley, Ordered structures and partitions, American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. MR 0332509

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

American Mathematical Society