A bijective proof of Stanley's shuffling theorem
Author:
I. P. Goulden
Journal:
Trans. Amer. Math. Soc. 288 (1985), 147160
MSC:
Primary 05A15; Secondary 05A30, 06A99
MathSciNet review:
773053
Fulltext 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
(52 #10440)
 [2]
George
E. Andrews, The theory of partitions, AddisonWesley
Publishing Co., Reading, Mass.LondonAmsterdam, 1976. Encyclopedia of
Mathematics and its Applications, Vol. 2. MR 0557013
(58 #27738)
 [3]
P.
Cartier and D.
Foata, Problèmes combinatoires de commutation et
réarrangements, Lecture Notes in Mathematics, No. 85,
SpringerVerlag, BerlinNew York, 1969 (French). MR 0239978
(39 #1332)
 [4]
H.
W. Gould, A new symmetrical combinatorial identity, J.
Combinatorial Theory Ser. A 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, A WileyInterscience
Publication, John Wiley & Sons, Inc., New York, 1983. With a foreword
by GianCarlo Rota; WileyInterscience Series in Discrete Mathematics. MR 702512
(84m:05002)
 [7]
F. H. Jackson, Transformations of series, Messenger of Math. 39 (1910), 145153.
 [8]
Percy
A. MacMahon, Combinatory analysis, Two volumes (bound as one),
Chelsea Publishing Co., New York, 1960. MR 0141605
(25 #5003)
 [9]
Lucy
Joan Slater, Generalized hypergeometric functions, Cambridge
University Press, Cambridge, 1966. MR 0201688
(34 #1570)
 [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
(48 #10836)
 [1]
 G. E. Andrews, Identities in combinatorics, I: On sorting two ordered sets, Discrete Math. 11 (1975), 97106. MR 0389609 (52:10440)
 [2]
 , The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2, AddisonWesley, 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), 278286. 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), 145153.
 [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:
http://dx.doi.org/10.1090/S00029947198507730535
PII:
S 00029947(1985)07730535
Article copyright:
© Copyright 1985
American Mathematical Society
