Section 2.2 Generating Functions
Given a sequence \(a_n\text{,}\) \(n\geq 0\text{,}\) we say \(g(x)=\sum_{n=0}^\infty\,a_n\,x^n\) is the generating function for \(a_n\text{.}\) By manipulating polynomials and power series, especially with recurrence relations, we can compute terms of a sequence or find closed-form expressions for general terms.
Suppose you have \(35\) identical apples to distribute to \(8\) boxes marked with different destinations. Each box should receive at least two apples, and at most five apples. How many ways can this be done?
The solution is to construct the polynomial \(x^2+x^3+x^4+x^5\) to represent the possibility of one box receiving between two and five apples. Due to the \(8\) boxes, we take a product of \(8\) copies of this polynomial, so that in the expansion every product of eight monomials that equals \(x^35\) represents a distribution of identical apples to distinct boxes. So the coefficient of \(x^35\) counts the number of distributions, and is straightforward in Sage. We demonstrate constructing the sum of powers in a way that might be more convenient for a larger problem. Note too, the necessity of using .expand() to force the eighth-power.
In American football, a scoring play can result in 2, 3, 6, 7, or 8 points. How many ways can a team accumulate \(43\) points? (We are not considering the order of the different types of scores relevant.)
For each type of score we build a power series whose terms represent multiples of that score. Then in the product, sums of exponents compute a total score. Here we are interested in the coefficient of \(x^{43}\text{.}\) We can use finite polynomials, stopping once the exponent exceeds \(43\text{,}\) but instead we will convert the infinite power series into rational functions (since they are geometric series).
We create this generating function in Sage and create the power series (well, the first part) as a finite Taylor polynomial of sufficient size. We only display a short version of the polynomial for reasons of space, but you could choose to display a longer version in an electronic version of this.
Notice that since the generating function is defined as a function, rather than an expression, the coefficient is extracted as constant function. You could evaluate the function (anywhere!) to get the integer, as we do next. Another alternative is to make a expression and get the Taylor polynomial as an expression. You need to be very cognizant of your objects as you work in Sage, it is very literal sometimes.