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 and on disjoint sets of integers, consider forming a permutation on the combined sets by "shuffling" and (i.e., and appear as subsequences). Stanley [**10**], 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.

**[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*-*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*-*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**

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