Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A bijective proof of Stanley’s shuffling theorem
HTML articles powered by AMS MathViewer

by I. P. Goulden PDF
Trans. Amer. Math. Soc. 288 (1985), 147-160 Request permission

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
  • George E. Andrews, Identities in combinatorics. I. On sorting two ordered sets, Discrete Math. 11 (1975), 97–106. MR 389609, DOI 10.1016/0012-365X(75)90001-1
  • George E. Andrews, The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. MR 0557013
  • 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, DOI 10.1007/BFb0079468
  • H. W. Gould, A new symmetrical combinatorial identity, J. Combinatorial Theory Ser. A 13 (1972), 278–286. MR 304193, DOI 10.1016/0097-3165(72)90031-3
  • I. P. Goulden, A bijective proof of the $q$-Saalschutz theorem (preprint).
  • I. P. Goulden and D. M. Jackson, Combinatorial enumeration, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. With a foreword by Gian-Carlo Rota. MR 702512
  • F. H. Jackson, Transformations of $q$-series, Messenger of Math. 39 (1910), 145-153.
  • Percy A. MacMahon, Combinatory analysis, Chelsea Publishing Co., New York, 1960. Two volumes (bound as one). MR 0141605
  • Lucy Joan Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966. MR 0201688
  • Richard P. Stanley, Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, R.I., 1972. 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
  • © Copyright 1985 American Mathematical Society
  • 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