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

  • [1] G. E. Andrews, Identities in combinatorics, I: On sorting two ordered sets, Discrete Math. 11 (1975), 97-106. MR 0389609 (52:10440)
  • [2] -, The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley, Reading, Mass., 1976. MR 0557013 (58:27738)
  • [3] P. Cartier and D. Foata, Problèmes combinatoires de commutation et rearrangements, Lecture Notes in Math., vol. 85, Springer, Berlin, 1969. MR 0239978 (39:1332)
  • [4] H. W. Gould, A new symmetrical combinatorial identity, J. Combin. Theory 13 (1972), 278-286. MR 0304193 (46:3328)
  • [5] I. P. Goulden, A bijective proof of the $ q$-Saalschutz theorem (preprint).
  • [6] I. P. Goulden and D. M. Jackson, Combinatorial enumeration, Wiley, New York, 1983. MR 702512 (84m:05002)
  • [7] F. H. Jackson, Transformations of $ q$-series, Messenger of Math. 39 (1910), 145-153.
  • [8] P. A. MacMahon, Combinatory analysis, Vols. I and II, Chelsea, New York, 1960. MR 0141605 (25:5003)
  • [9] L. J. Slater, Generalized hypergeometric functions, Cambridge Univ. Press, Cambridge, 1966. MR 0201688 (34:1570)
  • [10] R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. No. 119 (1972), 104 pp. MR 0332509 (48:10836)

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: https://doi.org/10.1090/S0002-9947-1985-0773053-5
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society