×

Riordan arrays and combinatorial sums. (English) Zbl 0814.05003

Enlarged abstract: The concept of a Riordan array, introduced under the name of renewal array in [D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22, 301-310 (1978; Zbl 0398.05007)] and generalized to its present form in [L. W. Shapiro, S. Getu, W.-J. Woan and L. C. Woodson, The Riordan group, Discrete Appl. Math. 34, No. 1-3, 229-239 (1991; Zbl 0754.05010)], is used in a constructive way to find the generating function of many combinatorial sums. The generating function can then help us to obtain the closed form of the sum or its asymptotic value. Some examples of sums involving binomial coefficients and Stirling numbers are examined, together with an application of Riordan arrays to some walk problems.

MSC:

05A15 Exact enumeration problems, generating functions
05A10 Factorials, binomial coefficients, combinatorial functions
05A19 Combinatorial identities, bijective combinatorics
11B73 Bell and Stirling numbers
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrews, G., Applications of basic hypergeometric functions, SIAM Rev., 16, 441-484 (1974) · Zbl 0299.33004
[2] Barcucci, E.; Pinzani, R.; Sprugnoli, R., The Motzkin family, Pure Math. Appl., A 2, 249-279 (1991) · Zbl 0756.05003
[3] Barcucci, E.; Pinzani, R.; Sprugnoli, R., The random generation of underdiagonal walks, 4th Congress on Formal Power Series and Algebraic Combinatorics (1992), Montreal · Zbl 0821.60079
[4] E. Barcucci, R. Pinzani and R. Sprugnoli, The random generation of directed animals, Theoret. Comput. Sci., to appear.; E. Barcucci, R. Pinzani and R. Sprugnoli, The random generation of directed animals, Theoret. Comput. Sci., to appear. · Zbl 0938.68935
[5] Bender, E. A., Asymptotic methods in enumeration, SIAM Rev., 16, 485-515 (1974) · Zbl 0294.05002
[6] Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Dordrecht
[7] Egorychev, G. P., Integral Representation and the Computation of Combinatorial Sums, (Amer. Math. Soc. Translations, Vol. 59 (1984), Amer. Math. Soc: Amer. Math. Soc Providence, RI) · Zbl 0676.05009
[8] Flajolet, Ph.; Salvy, B.; Zimmermann, P., Automatic average-case analysis of algorithms, Theoret. Comput. Sci., 79, 37-109 (1991) · Zbl 0768.68041
[9] Gosper, R. W., Decision procedure for indefinite hypergeometric summation, Proc. Nat. Acad. Sci. USA, 75, 40-42 (1978) · Zbl 0384.40001
[10] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1988), Addison-Wesley: Addison-Wesley Reading, MA
[11] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001
[12] Karr, M., Summation in finite terms, J. ACM, 28, 305-350 (1981) · Zbl 0494.68044
[13] Kemeny, J. G., Matrix representation for combinatorics, J. Combin. Theory, 36, 279-306 (1984) · Zbl 0548.05004
[14] S.G. Kettle, Families enumerated by the Schröder-Etherington sequence and a renewal array it generates, in: Combinatorial Mathematics X, Lecture Notes in Math. 1036 (Springer, Berlin) 244-274.; S.G. Kettle, Families enumerated by the Schröder-Etherington sequence and a renewal array it generates, in: Combinatorial Mathematics X, Lecture Notes in Math. 1036 (Springer, Berlin) 244-274.
[15] Knuth, D. E., The Art of Computer Programming, Vol. I-III (1968-1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903
[16] Ranjan, Roy, Binomial identities and hypergeometric series, Amer. Math. Monthly, 97, 36-46 (1987) · Zbl 0621.33005
[17] Riordan, J., Combinatorial Identities (1968), Wiley: Wiley New York · Zbl 0194.00502
[18] Rogers, D. G., Pascal triangles, Catalan numbers and renewal arrays, Discrete Math., 22, 301-310 (1978) · Zbl 0398.05007
[19] Roman, S., The Umbral Calculus (1984), Academic Press: Academic Press New York · Zbl 0536.33001
[20] Ruskey, F., On the average shape of binary trees, SIAM J. Algebraic Discrete Methods I, 1, 43-49 (1980) · Zbl 0496.68044
[21] Salvy, B., Private communication (1992)
[22] Shapiro, L. V.; Getu, S.; Woan, W.-J.; Woodson, L., The Riordan Group, Discrete Appl. Math., 34, 229-239 (1991) · Zbl 0754.05010
[23] Wilf, H. S., The “Snake Oil” method for proving combinatorial identities, (Surveys in Combinatorics (1990), Cambridge University Press: Cambridge University Press Cambridge), 208-217, 1989 · Zbl 0694.05006
[24] Wilf, H. S., Generating functionology (1990), Academic Press: Academic Press New York
[25] Wilf, H. S.; Zeilberger, D., Rational functions certify combinatorial identities, J. AMS, 3, 147-158 (1990) · Zbl 0695.05004
[26] Zeilberger, D., A fast algorithm for proving terminating hypergeometric identities, Discrete Math., 80, 207-211 (1990) · Zbl 0701.05001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.