Extraction of Coefficients and Generating Functions

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).