×

Lagrange inversion: when and how. (English) Zbl 1108.05008

Summary: The aim of the paper is to show how the Lagrange inversion formula can be applied in a straight-forward way (i) to find the generating function of many combinatorial sequences, (ii) to extract the coefficients of a formal power series, (iii) to compute combinatorial sums, and (iv) to perform the inversion of combinatorial identities. Particular forms of the Lagrange inversion formula are studied, in order to simplify the computation steps. Some examples are taken from the literature, but their proof is different from the usual, and others are new.

MSC:

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

References:

[1] de Lagrange, L.: Nouvelle méthode pour résoudre des équations littérales par le moyen des séries. Mém. Acad. Roy. Sci. Belles-Lettres de Berlin 24 (1770)
[2] Egorychev, G.P.: Integral Representation and the Computation of Combinatorial Sums (trans. H. H. McFadden), volume 59. Amer. Math. Soc., Providence (1984) · Zbl 0524.05001
[3] Gessel, I.M.: A factorization for formal Laurent series and lattice path enumeration. J. Combin. Theory Ser. A 28, 321–337 (1980) · doi:10.1016/0097-3165(80)90074-6
[4] Gessel, I.M.: A combinatorial proof of the multivariable Lagrange inversion formula. J. Combin. Theory Ser. A 45, 178–195 (1987) · Zbl 0651.05009 · doi:10.1016/0097-3165(87)90013-6
[5] Gould, H.W.: Combinatorial Identities, A Standardized Set of Tables Listing 500 Binomial Coefficient Summations. Morgantown W. Va. (1972) · Zbl 0241.05011
[6] Goulden, I.P., Jackson, D.M.: Combinatorial Enumeration. Wiley, New York (1983)
[7] Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, New York (1989) · Zbl 0668.00003
[8] Henrici, P.: Applied and Computational Complex Analysis, I. Wiley, New York (1988) · Zbl 0635.30001
[9] Merlini, D., Sprugnoli, R., Verri, M.C.: The method of coefficients. Amer. Math. Monthly (to appear) · Zbl 1191.05006
[10] Merlini, D., Sprugnoli, R., Verri, M.C.: Human and constructive proof of combinatorial identities: an example from Romik. Discrete Math. Theor. Comput. Sci. AD, 383–392 (2005) · Zbl 1100.05003
[11] Raney, G.N.: Functional composition patterns and power series reversion. Trans. Amer. Math. Soc. 94, 441–451 (1960) · Zbl 0131.01402 · doi:10.1090/S0002-9947-1960-0114765-9
[12] Riordan, J.: Combinatorial Identities. Wiley, New York (1968)
[13] Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading, MA (1996) · Zbl 0841.68059
[14] Shapiro, L.W., Getu, S., Woan, W.-J., Woodson, L.: The Riordan group. Discrete Appl. Math. 34, 229–239 (1991) · Zbl 0754.05010 · doi:10.1016/0166-218X(91)90088-E
[15] Singer, D.: Q-analogues of Lagrangre inversion. Adv. Math. 115, 73–82 (1978)
[16] Sprugnoli, R.: Riordan Array Proofs of Identities in Gould’s Book. http://www.dsi.unifi.it/esp
[17] Sprugnoli, R.: Riordan arrays and combinatorial sums. Discrete Math. 132, 267–290 (1994) · Zbl 0814.05003 · doi:10.1016/0012-365X(92)00570-H
[18] Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999) · Zbl 0928.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.