ABSTRACT
Some kinds of combinatorial calculations are modeled by the behavior of infinite power series or even finite power series (i.e., polynomials). For instance, we considered in Chapter 2 how to determine the number of ways of selecting k items from a set of n; for simplicity, we will consider n — 4, k = 2. Suppose we wish to multiply (1 + x 1)(1 + x 2)(1 + x 3)(1 + x 4). In the product, we ask how many terms of the form xixj there will be; clearly, ( 4 2 ) = 6 https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315366890/f4bfe916-bec8-4e54-8a5a-ffef17c80cb7/content/eq273.tif"/> of them, since that is how many ways we can choose two of the factors to contribute an xi . Now, if we set x 1 = x 2 = x 3 = x 4 = x, the product is the polynomial (1 + x)4. The coefficient of x 2 in this product is ( 4 2 ) = 6 https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315366890/f4bfe916-bec8-4e54-8a5a-ffef17c80cb7/content/eq274.tif"/> (The reader will recall that this subscripting technique is how we proved Theorem 2.3, the Binomial Theorem.) In the same way, some numbers of combinatorial interest (such as a sequence of integers) have properties that become clear or easier to prove when they are used as coefficients of a polynomial or an infinite series. These considerations motivate us to define the generating function of a sequence a 0, a 1, … to be the formal power series ∑ i ≥ 0 a i x i https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315366890/f4bfe916-bec8-4e54-8a5a-ffef17c80cb7/content/eq275.tif"/> .
