Lagrange Inversion: When and How
- PDF / 378,624 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 272 Views
Lagrange Inversion: When and How D. Merlini · R. Sprugnoli · M. C. Verri
Received: 20 July 2005 / Accepted: 18 November 2006 / Published online: 12 December 2006 © Springer Science + Business Media B.V. 2006
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. Key words combinatorial sums · generating functions · Lagrange inversion formula · method of coefficients · Riordan arrays. Mathematics Subject Classifications (2000) 05A10 · 05A15 · 05A19.
1 Introduction The “method of coefficients” is an elegant technique for proving combinatorial identities, evaluating and inverting sums, essentially due to Egorychev [2] (see also [9]). It mainly consists in manipulating generating functions and their coefficients
D. Merlini (B) · R. Sprugnoli · M. C. Verri Dipartimento di Sistemi e Informatica, viale Morgagni 65, 50134 Firenze, Italy e-mail: [email protected] R. Sprugnoli e-mail: [email protected] M. C. Verri e-mail: [email protected]
234
D. Merlini, et al.
(see e.g., [6]), and we can summarize its most relevant aspects in the following three points which can overlap each other: 1. Given a sequence ( fn )n∈N of combinatorial interest, defined by a formula or by a recurrence relation, find its generating function G t ( fn )n∈N = G ( fn ) = ∞ n k=0 fn t = f (t); k n 2. Given a formal power series f (t) = ∞ k=0 fk t , extract the coefficient of t : [tn ] f (t) = fn as an explicit expression; 3. Given a combinatorial identity such as a sum: bn = nk=0 dn,k ak , find the transformation T connecting the two generating functions b(t) = G (bn ) and a(t) = G (an ) and expressing the identity as b(t) = T(a(t)). This approach can solve two important problems: (a) If the ak ’s are known, by extracting the coefficient [tn ]b(t) = [tn ]T(a(t)) we have a closed form for the sum of the right hand member; (b) If the ak ’s (and hence a(t)) are not known, by inverting the identity we have a(t) = T −1 (b(t)) and hence the solution of the identity, that is, of the infinite system it represents (see, e.g., [12]). The Lagrange Inversion Formula (LIF) assumes a central role in all these problems, and our aim is to show how its systematic use can produce very elegant and straightforward proofs. We take for granted the Lagrange formula, which we use below in the equivalent forms K6, K6 and G6. Moreover, we point out (see Theorems 2.1, 2.3 and Corollary 2.2) that many applications of the LIF can be reduced to some particular cases which correspond to the generalized binomial and generalized exponential series in [7]. In general, the LIF is
Data Loading...
