Abstract
The aim of the present paper is to show how the Lagrange Inversion Formula (LIF) 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 LIF 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
Egorychev, G.P.: Integral Representation and the Computation of Combinatorial Sums (trans. H. H. McFadden), volume 59. Amer. Math. Soc., Providence (1984)
Gessel, I.M.: A factorization for formal Laurent series and lattice path enumeration. J. Combin. Theory Ser. A 28, 321–337 (1980)
Gessel, I.M.: A combinatorial proof of the multivariable Lagrange inversion formula. J. Combin. Theory Ser. A 45, 178–195 (1987)
Gould, H.W.: Combinatorial Identities, A Standardized Set of Tables Listing 500 Binomial Coefficient Summations. Morgantown W. Va. (1972)
Goulden, I.P., Jackson, D.M.: Combinatorial Enumeration. Wiley, New York (1983)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, New York (1989)
Henrici, P.: Applied and Computational Complex Analysis, I. Wiley, New York (1988)
Merlini, D., Sprugnoli, R., Verri, M.C.: The method of coefficients. Amer. Math. Monthly (to appear)
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)
Raney, G.N.: Functional composition patterns and power series reversion. Trans. Amer. Math. Soc. 94, 441–451 (1960)
Riordan, J.: Combinatorial Identities. Wiley, New York (1968)
Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading, MA (1996)
Shapiro, L.W., Getu, S., Woan, W.-J., Woodson, L.: The Riordan group. Discrete Appl. Math. 34, 229–239 (1991)
Singer, D.: Q-analogues of Lagrangre inversion. Adv. Math. 115, 73–82 (1978)
Sprugnoli, R.: Riordan Array Proofs of Identities in Gould’s Book. http://www.dsi.unifi.it/∼resp
Sprugnoli, R.: Riordan arrays and combinatorial sums. Discrete Math. 132, 267–290 (1994)
Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Merlini, D., Sprugnoli, R. & Verri, M.C. Lagrange Inversion: When and How. Acta Appl Math 94, 233–249 (2006). https://doi.org/10.1007/s10440-006-9077-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10440-006-9077-7
Key words
- combinatorial sums
- generating functions
- Lagrange inversion formula
- method of coefficients
- Riordan arrays