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 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]**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*-*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*-*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)**

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