×

Binomial identities – combinatorial and algorithmic aspects. (English) Zbl 0823.33003

The problem of proving a particular binomial identity is taken as an opportunity to discuss various aspects of this field and to discuss various proof techniques in an exemplary way. In particular, the unifying role of the hypergeometric nature of binomial identities is underlined. This aspect is also basic for combinatorial models and techniques, developed during the last decade, and for the recent algorithmic proof procedures.
Much of mathematics comes from looking at very simple examples from a more general perspective. Hypergeometric functions are a good example of this.
Reviewer: R. Askey (Madison)

MSC:

33C20 Generalized hypergeometric series, \({}_pF_q\)
05A19 Combinatorial identities, bijective combinatorics
11B65 Binomial coefficients; factorials; \(q\)-identities
05A15 Exact enumeration problems, generating functions

Software:

gfun
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Andrews, G.E., Applications of basic hypergeometric functions, SIAM rev., 16, 441-484, (1974) · Zbl 0299.33004
[2] Andrews, G.E., Identities in combinatorics, I: on sorting two ordered sets, Discrete math., 11, 97-106, (1975) · Zbl 0301.05006
[3] Bailey, W.N., Generalized hypergeometric series, (1935), Cambridge Univ. Press London · Zbl 0011.02303
[4] Bailey, W.N., The generating function for Jacobi polynomials, J. London math. soc., 13, 243-246, (1938) · Zbl 0018.12202
[5] Carlitz, L., Multiple binomial and power sums, Houston J. math, 6, 331-354, (1980) · Zbl 0457.05006
[6] Cartier, P., Démonstration ‘automatique’ d’identités et fonctions hypergéometriques (d’après D. Zeilberger), Séminare bourbaki, 746, (1991) · Zbl 0796.33014
[7] Cartier, P.; Foata, D., Problèmes combinatoires de commutation et de réarrangements, Lecture notes in mathematics, 85, (1969), Springer Berlin · Zbl 0186.30101
[8] Chu, W., Inversion techniques and combinatorial identities, Lehrstuhl II für Mathematik, (1992), Universität Bayreuth, preprint
[9] Constantineau, I., A generalization of the Pfaff-Saalschütz theorem, Stud. appl. math., 85, 243-248, (1991) · Zbl 0742.05007
[10] Cusick, T., Recurrences for sums of powers of binomial coefficients, J. combin. theory ser. A, 52, 77-83, (1989) · Zbl 0682.05006
[11] Egorychev, G.P., Integral representation and computation of combinatorial sums, Transl. math. monographs, 59, (1984), Amer. Mathematical Soc Providence, RI · Zbl 0524.05001
[12] Ekhad, S.B., Short proofs of two hypergeometric summation formulas of karlsson, Proc. amer. math. soc., 107, 1143-1144, (1989) · Zbl 0688.33001
[13] Ekhad, S.B., A very short proof of Dixon’s theorem, J. combin. theory ser. A, 54, 141-142, (1990) · Zbl 0707.05007
[14] Ekhad, S.B., A one-line proof of the habsieger-Zeilberger G2 constant term identity, J. comput. appl. math., 90, 133-134, (1991) · Zbl 0737.33010
[15] Ekhad, S.B., Short proof of a strange combinatorial identity conjectured by Gosper, Discrete math., 90, 319-320, (1991) · Zbl 0741.05004
[16] Ekhad, S.B.; Zeilberger, D., A 21st century proof of Dougall’s hypergeometric sum identity, J. math. anal. appl., 147, 610-611, (1990) · Zbl 0714.33002
[17] Erdélyi, A., Higher transcendental functions, (1953), McGraw-Hill New York, (The Bateman Manuscript Project, 3 vols.)
[18] Foata, D., (), 186
[19] Foata, D., A combinatorial proof of the mehler formula, J. combin. theory ser. A, 24, 367-376, (1978) · Zbl 0401.33008
[20] Foata, D., Some Hermite polynomial identities and their combinatorics, Adv. appl. math., 2, 250-259, (1981) · Zbl 0475.33006
[21] Foata, D., Une démonstration combinatoire de l’identité de Pfaff-Saalschütz, C.R. acad. sci. Paris, 297, 221-224, (1983) · Zbl 0534.33001
[22] Foata, D., Combinatoire des identités sur LES polynômes orthogonaux, (), 1541-1553
[23] Foata, D.; Garsia, A., A combinatorial approach of the mehler formulas for Hermite polynomials, (), 163-179, 1979
[24] Foata, D.; Leroux, P., Polynômes de Jacobi, interprétation combinatoire et fonction génératrice, Proc. amer. math. soc., 87, 47-53, (1983) · Zbl 0522.33004
[25] Foata, D.; Strehl, V., Combinatorics of Laguerre polynomials, (), 123-140
[26] Franel, J.; Franel, J., L’intermédiaire des mathématiciens, L’intermédiaire des mathématiciens, 2, 33-35, (1895), notes published in
[27] Gessel, I., A combinatorial proof of the multivariable Lagrange inversion formula, J. combin. theory ser. A, 45, 178-195, (1987) · Zbl 0651.05009
[28] Gessel, I.; Santon, D., Short proofs of Saalschütz’s and Dixon’s theorems, J. combin. theory ser. A, 38, 87-90, (1985) · Zbl 0559.05008
[29] Gessel, I.; Sturtevant, D., A combinatorial proof of Saalschütz theorem, (1989), preprint
[30] Gosper, R.W., Decision procedure for indefinite hypergeometric summation, Proc. nat. acad. sci. USA, 75, 40-42, (1978) · Zbl 0384.40001
[31] Gould, H.W., Combinatorial identities: A standard set of tables listing 500 binomial coefficient identities, (1972), Morgantown VA, (rev. ed.) · Zbl 0241.05011
[32] Goulden, I.P., A bijective proof of the q-Saalschütz identity, Discrete math., 57, 39-44, (1985) · Zbl 0592.05005
[33] Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, (1989), Addison-Wesley Reading, MA
[34] Greene, D.H.; Knuth, D.E., Mathematics for the analysis of algorithms, (1981), Birkhäuser Basel · Zbl 0481.68042
[35] Hornegger, J., Hypergeometrische summation and polynomiale rekursion, Diplomarbeit, (1992), IMMD-I Erlangen
[36] Knuth, D.E., The art of computer programming, Fundamental algorithms, 1, (1969), Addison-Wesley Reading, MA · Zbl 0191.17903
[37] Koornwinder, T.H., On Zeilberger’s algorithm and its q-analogue: a rigorous description, (1992), Centre for Mathematics and Computer Science Amsterdam, Tech. Report AM-R9207 · Zbl 0770.33012
[38] MacMahon, P.A., Combinatory analysis, (1915), Cambridge Univ. Press Cambridge, (Reprinted by Chelsea, New York, 1955) · JFM 45.1271.01
[39] Parnes, S.; Ekhad, S.B., A WZ-style proof of Jacobi Polynomial’s generating function, Discrete math., 110, 263-264, (1992) · Zbl 0784.33005
[40] Perlstadt, M.A., Some recurrences for sums of powers of binomial coefficients, J. number theory, 27, 304-309, (1987) · Zbl 0626.10010
[41] Rainville, E., Special functions, (1971), Chelsea Bronx, NY · Zbl 0231.33001
[42] Riordan, J., Combinatorial identities, (1968), Wiley New York · Zbl 0194.00502
[43] Roy, R., Binomial identities and hypergeometric functions, Amer. math. monthly, 94, 1, 36-46, (1987) · Zbl 0621.33005
[44] Salvy, B.; Zimmerman, P., GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, (October 1992), preprint
[45] Schmidt, A.L., Generalized Legendre polynomials, J. reine angew. math., 404, 192-202, (1990) · Zbl 0684.33005
[46] Schmidt, A.L., Generalized Legendre and q-Legendre polynomials, VII simposium sobre polinomios oriogonales y applicaciones, Granada, (1991), J. Comp. Appl. Math., to appear
[47] Schmidt, A.L., Legendre transforms and apéry’s sequences, (August 1992), Matematisk Institut, University of Copenhagen, preprint series 14
[48] Srivastava, H.M.; Manocha, H.L., A treatise on generating functions, (1984), Ellis Horwood Chichester · Zbl 0535.33001
[49] Stanton, D., A short proof of a generating function for the Jacobi polynomials, Proc. amer. math. soc., 80, 398-400, (1980) · Zbl 0446.33016
[50] Strehl, V., Zykel-enumeration bei lokal-strukturierten funktionen, habilitationsschrift. erlangen, (1990)
[51] Strehl, V., Combinatorics of special functions: facets of Brock’s identity, (), 363-378
[52] Strehl, V., Recurrences and Legendre transform, (), 81-100, 1993/033
[53] Székely, L.A., Common origin of cubic binomial identities; a generalization of surányi’s proof of le jen Shoo’s formula, J. combin theory ser. A, 40, 171-174, (1985) · Zbl 0573.05005
[54] Takács, L., On an identity of shih-chieh Chu, Acta sci. math. (Szeged), 34, 383-391, (1973) · Zbl 0264.05004
[55] van der Poorten, A.J., A proof that Euler missed … apérys proof of the irrationality of ζ(3), Math. intelligencer, 1, 195-203, (1978) · Zbl 0409.10028
[56] Verbaeten, P., The automatic construction of pure recurrence relations, Proc. EUROSAM ’74; ACM-SIGSAM bull., 8, 96-98, (1974)
[57] Verbaeten, P., Rekursiebetrekkingen voor lineaire hypergeometrische funkties, proefschrift voor het doctoraat in de toegepaste wetenschappen, (1976), Katholieke Universiteit Leuven Belgium
[58] Viennot, G., Heaps of pieces I: basic definitions and combinatorial lemmas, (), 210-245
[59] Wilf, H.S.; Zeilberger, D., An algorithmic proof theory for hypergeometric (ordinary and ‘q’) multisum/integral identities, Invent. math., 108, 575-633, (1992) · Zbl 0739.05007
[60] Wilf, H.S.; Zeilberger, D., Rational function certification of multisum/integral/‘q’ identities, Bull. amer. math. soc. (new series), 27, 148-153, (1992) · Zbl 0759.05007
[61] Zeilberger, D., A q-foata proof of the q-Saalschütz identity, European J. combin., 8, 461-463, (1987) · Zbl 0643.05003
[62] Zeilberger, D., A fast algorithm for proving terminating hypergeometric identities, Discrete math., 80, 207-211, (1990) · Zbl 0701.05001
[63] Zeilberger, D., A holonomic systems approach to special function identities, J. comput. appl. math., 32, 321-368, (1990) · Zbl 0738.33001
[64] Zeilberger, D., A Maple program for proving hypergeometric identities, SIGSAM bull., 25, 3, 4-13, (1991)
[65] Zeilberger, D., The method of creative telescoping, J. symbolic comput., 11, 195-205, (1991) · Zbl 0738.33002
[66] Zeng, J., Pfaff-Saalschütz, J. combin. theory ser. A, 51, 141-143, (1989), revisited · Zbl 0676.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.