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: For two permutations and on disjoint sets of integers, consider forming a permutation on the combined sets by "shuffling" and (i.e., and appear as subsequences). Stanley , by considering -partitions and a -analogue of Saalschutz's summation, obtained the generating function for shuffles of and 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 -binomial coefficients and depends only on remarkably simple parameters, namely the lengths, numbers of falls and greater indexes of and . A combinatorial proof of this result is obtained by finding bijections for lattice path representations of shuffles which reduce and to canonical permutations, for which a direct evaluation of the generating function is given.
-  George E. Andrews, Identities in combinatorics. I. On sorting two ordered sets, Discrete Math. 11 (1975), 97–106. MR 389609, https://doi.org/10.1016/0012-365X(75)90001-1
-  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
-  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
-  H. W. Gould, A new symmetrical combinatorial identity, J. Combinatorial Theory Ser. A 13 (1972), 278–286. MR 304193, https://doi.org/10.1016/0097-3165(72)90031-3
-  I. P. Goulden, A bijective proof of the -Saalschutz theorem (preprint).
-  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
-  F. H. Jackson, Transformations of -series, Messenger of Math. 39 (1910), 145-153.
-  Percy A. MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York, 1960. MR 0141605
-  Lucy Joan Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966. MR 0201688
-  Richard P. Stanley, Ordered structures and partitions, American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. MR 0332509
- G. E. Andrews, Identities in combinatorics, I: On sorting two ordered sets, Discrete Math. 11 (1975), 97-106. MR 0389609 (52:10440)
- -, The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley, Reading, Mass., 1976. MR 0557013 (58:27738)
- 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)
- H. W. Gould, A new symmetrical combinatorial identity, J. Combin. Theory 13 (1972), 278-286. MR 0304193 (46:3328)
- I. P. Goulden, A bijective proof of the -Saalschutz theorem (preprint).
- I. P. Goulden and D. M. Jackson, Combinatorial enumeration, Wiley, New York, 1983. MR 702512 (84m:05002)
- F. H. Jackson, Transformations of -series, Messenger of Math. 39 (1910), 145-153.
- P. A. MacMahon, Combinatory analysis, Vols. I and II, Chelsea, New York, 1960. MR 0141605 (25:5003)
- L. J. Slater, Generalized hypergeometric functions, Cambridge Univ. Press, Cambridge, 1966. MR 0201688 (34:1570)
- R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. No. 119 (1972), 104 pp. MR 0332509 (48:10836)