Extraction of Coefficients and Generating Functions

Shapiro, Louis and Sprugnoli, Renzo and Barry, Paul and Cheon, Gi Sang and He, Tian Xiao and Merlini, Donatella and Wang, Weiping (2022) Extraction of Coefficients and Generating Functions. In: Springer Monographs in Mathematics :. Springer Monographs in Mathematics . Springer Science and Business Media Deutschland GmbH, pp. 19-46.

Full text not available from this repository. (Request a copy)

Abstract

Generating functions have emerged as one of the most popular approaches to combinatorial problems, above all to problems arising in the analysis of algorithms (see, for example, D. E. Knuth [8] and R. Sedgewick and Ph. Flajolet [11] and Ph. Flajolet and R. Sedgewick [3]). A clear exposition of this concept is given in three books, namely, those of I. P. Goulden and D. M. Jackson [5], R. Stanley [13], and H. S. Wilf [14]; further discussion of this topic can be found in L. Comtet [1] and R.L. Graham, D.E. Knuth, and O. Patashnik [6]. Greene and Knuth [7, p. 7] show that combinatorial sums can be found in closed form by means of certain transformations on generating functions and the extraction of coefficients, attributing this elegant technique, the “method of coefficients”, to G. P. Egorychev [2]. The method has been described in D. Merlini, R. Sprugnoli, and M. C. Verri [10]. The present chapter is devoted to formal power series and generating functions. For example, we will prove that the series 1 + t+ t2+ t3+ ⋯ can be conveniently abbreviated as 1 / (1 - t), and from this fact we will be able to infer that the series has a formal power series inverse, which is 1 - t+ 0 t2+ 0 t3+ ⋯, or we will prove that the coefficient of tn in the series expansion of t/ (1 - t- t2) is the nth Fibonacci number Fn satisfying Fn= Fn - 1+ Fn, F0= 0, F1= 1 while the coefficient of tn in (1-1-4t)/(2t) is the nth Catalan number (2nn)/(n+1).

Item Type:	Book Section
Additional Information:	Publisher Copyright: © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Uncontrolled Keywords:	/dk/atira/pure/subjectarea/asjc/2600
Departments or Groups:
Depositing User:	Admin SSL
Date Deposited:	19 Oct 2022 23:18
Last Modified:	12 Aug 2023 02:00
URI:	http://repository-testing.wit.ie/id/eprint/5242

Actions (login required)

View Item