GENERATING FUNCTIONS: APPLICATIONS AND TECHNIQUES

Philip M. Tsang Charles Sturt University–Riverina, Australia

Shing S. So Central Missouri State University

Abstract. Generating functions, one of the important topics in undergraduate discrete mathematics, are useful in a wide range of disciplines in mathematics. However, most of the undergraduate students feel that it is difficult to apply them. In this paper, we first introduce the background necessary for our discussion, then we demonstrate, through examples, how generating functions can be used in certain series, probability theory, and some counting problems. A BASIC program performing some counting calculations can be obtained from the authors upon request.

1. A Brief Discussion on Formal Power Series. Let {a_{n}}_{n=0}^{∞} be a sequence of real numbers. Then

f = ∑_{n=0}^{∞} a_{n}x^{n}

is the formal power series of {a_{n}}_{n=0}^{∞}. The following remarks can be found in [1] and [2]. \underline{Remarks}. A. The sequence {a_{n}}_{n=0}^{∞} discussed above is called the sequence of coefficients and f

is called the ordinary power series generating function for {a_{n}}_{n=0}^{∞}.

B. f may not exist analytically, but can be considered merely as an algebraic object. C. f has a multiplicative inverse if and only if a_{0} ≠ 0.

D. f′ = ∑_{n=1}^{∞}[n(a_{n})]x^{n−1} is called the formal derivative of f.

2. Recurring Series. A relatively old but direct application of generating functions, found in old college algebra textbooks such as [3] and [4], is on recurring series. This can be defined as a formal power series whose coefficient sequence is recursively generated. Unfortunately, in order to avoid analytical difficulty, most of the examples on recurring series only discuss the sum of the first n terms of the series. The example below may show a different perspective on applications of recurring series and generating functions.

As an example, let a_{0} = 1, a_{1} = 1, and
a_{i} = a_{i−1} + 2a_{i−2} for i ≥ 2.

Then S_{n}, the sum of the first n + 1 terms of the sequence, can be found as follows. Let

T_{n}(x) = ∑_{i=0}^{n} a_{i}x^{i}.

It is easy to see that

(1 − x − 2x^{2})T_{n}(x) = 1 − (a_{n} + 2a_{n−1})x^{n+1} − 2a_{n}x^{n+2}

and hence

T_{n}(x) = \frac{1 − (a_{n} + 2a_{n−1})x^{n+1} − 2a_{n}x^{n+2}}{1 − x − 2x^{2}} .

Since S_{n} = T_{n}(1),

S_{n} = \frac{3a_{n} + 2a_{n−1} − 1}{2}.

Next, let us further discuss the infinite sum ∑_{i=0}^{∞} a_{i}, which is a divergent series. Let

T (x) = ∑_{i=0}^{∞} a_{i}x^{i}.

Using the remarks in Section 1,

T (x) = \frac{1}{1 − x − 2x^{2}} .

Therefore,

lim_{x→1^{−}} ∑_{i=0}^{∞} a_{i}x^{i} = lim_{x→1^{−}} T (x) = −\frac{1}{2},

which obviously cannot be the sum of this divergent series. However, it can be interpreted as the A–sum of ∑_{i=0}^{∞} a_{i} according to Hardy [5].

This example can easily be generalized to the case where the first k terms, a_{0}, a_{1}, ⋯, a_{k−1}, of the sequence of coefficents are given and

(∗)  a_{k} = ∑_{i=0}^{k−1} α_{i}a_{i}, α_{i} ∈ ℝ.

Using (∗) and the same technique in the example, we can obtain the generating function

f(x) = \frac{∑_{i=0}^{k−1} α_{i}x^{i} + ∑_{i=1}^{k} a_{i}(∑_{i=0}^{k−i−1} α_{j}x^{i+j})}{1 + ∑_{i=1}^{k} a_{i}x^{i}}

of {a_{i}}_{i=0}^{∞} and hence if lim_{x→1^{−}} f(x) exists, we have the A–sum of ∑_{i=0}^{∞} a_{i}.

3. Means and Variances of Some Probability Distributions. In mathematical statistics the usual way of finding the mean and variance of a given probability distribution function (p.d.f.) is by means of its moment generating function (m.g.f.) which is different from its corresponding power series generating function (also known as the probability generating function or p.g.f.) defined in Section 1. Rohatgi [6] indicated that the p.g.f. is extremely useful in finding the mean and variance of discrete probability distributions. In fact, if F is the p.g.f. of a given p.d.f., f, then μ and σ^{2} can be found by the simple formulas

μ = F′(1)

and

σ^{2} = F′′(1) + F′(1) − [F′(1)]^{2}

discussed in [1]. However, to obtain F (x) from f(n) may not be an easy task in general. If we assume that either the p.d.f., f(n), or the m.g.f., M(t), of a discrete probability distribution is known, then the p.g.f., F (x), can be found by simply summing f(n)x^{n} from 0 to ∞ or by replacing e^{t} by x. That is,

F (x) = ∑_{n=0}^{∞} f(n)x^{n}.

Since f(n) is a p.d.f., F (1) = 1.

As an illustration, we will compute μ and σ^{2} for the negative binomial distribution. In addition, we will display (in a table) the p.d.f. and p.g.f. of several discrete probability distributions which are familiar to students in undergraduate statistics.

It is well known that the p.d.f. of the negative binomial distribution function is given by

f(n) = \binom{r + n − 1}{n}p^{r}(1 − p)^{n}, n = 0, 1, 2, ⋯, 0 ≤ p ≤ 1.

Then its p.g.f. is given by

F (x) = ∑_{n=0}^{∞} \binom{r + n − 1}{n}p^{r}(1 − p)^{n}x^{n} = (\frac{px}{1 − (1 − p)x})^{r} .

Its first and second derivatives are

F′(x) = \frac{rp^{r}x^{r−1}}{[1 − (1 − p)x]^{r+1}} ;

F′′(x) = \frac{rp^{r}x^{r−2}[1 − (1 − p)x]^{r}((r − 1)[1 − (1 − p)x] + x[(r + 1)(1 − p)])}{[1 − (1 − p)x]^{2r+2}}.

Thus, μ = F′(1) = \frac{r}{p} and

σ^{2} = F′(1) + F′′(1) − [F′(1)]^{2} = \frac{r − rp}{p^{2}} = \frac{r(1 − p)}{p^{2}}.

Similarly, using the following table, μ and σ^{2} of each of those probability distributions in the table can be easily obtained.

113

4. Some Counting Problems. Now, let us consider a problem discussed in [3], which is due to De Moivre and was published by him in 1730. There are n dice with f faces marked from 1 to f. If they are thrown at random, what is the probability that the sum of the numbers exhibited shall be equal to p ? The number of ways of obtaining p is simply the coefficient of x^{p} in the polynomial (x + x^{2} + ⋯ + x^{f})^{n}. It is worthwhile to point out that using the generating function and the Binomial Theorem we can establish

(x + x^{2} + ⋯ + x^{f})^{n} = x^{n}[(1 − x^{f})^{n}(1 − x)^{−n}],

which is equivalent to the product

x^{n}[1+\binom{n}{1}(−1)x^{f} +⋯+\binom{n}{n}(−1)^{n}(x^{f})^{n}][1+(−1)\binom{n}{1}(−x)+(−1)^{2}\binom{n + 1}{2}(−x)^{2} +⋯].

The coefficient of x^{p} in this product is

\frac{n(n + 1) ⋯ (p − 1)}{(p − n)!} − \binom{n}{1}\frac{n(n + 1) ⋯ (p − f − 1)}{(p − n − f)!} + \binom{n}{2}\frac{n(n + 1) ⋯ (p − 2f − 1)}{(p − n − 2f)!} − ⋯,

where the series continues as long as no negative factors appear. The required probability can be obtained by dividing this series by f^{n}.

Next, we will investigate a similar but more complicated situation. Assume that there are 16 tickets in an urn which are distinctly numbered from 1 through 16. Suppose 4 tickets are drawn from the urn without replacement. How many ways can these 4 ticket numbers sum to 34? The analysis given below shows that the numbers 16, 4, and 34 are really insignificant. Other values can be easily chosen instead of these particular ones.

The above problem is equivalent to finding the number of ways 34 can be expressed as the sum of 4 distinct addends chosen from {1, 2, ⋯ 16}. As Wilf [1] suggested, the answer

is simply the coefficient of the term x^{4}t^{34} in the expansion of ∏_{i=1}^{16}(1 + xt^{i}) and it turns out

to be 86.

In what follows, we establish a recursive formula for calculating the coefficients in gen-

eral. Suppose that f(k) = ∏_{i=1}^{k}(1 + xt^{i}). Then

f(k) = ∑_{n,m} C_{n,m}^{k}x^{n}t^{m} where m = 0, 1, ⋯, \frac{k(k + 1)}{2}, n = 0, ⋯, k.

\begin{aligned}f(k + 1) & = f(k)(1 + xt^{k+1}) \\ & = ∑_{n,m} C_{n,m}^{k}x^{n}t^{m} + ∑_{n,m} C_{n,m}^{k}x^{n+1}t^{m+k+1} \\ & = ∑_{n≥0} ∑_{m≥0} C_{n,m}^{k}x^{n}t^{m} + ∑_{n≥1} ∑_{m≥k+1} C_{n−1,m−k−1}^{k} x^{n}t^{m} \\ & = ∑_{n≥0} ∑_{m≥0} C_{n,m}^{k}x^{n}t^{m} + ∑_{n≥0} ∑_{m≥0} C_{n−1,m−k−1}^{k}x^{n}t^{m} \\ & = ∑_{n,m} (C_{n,m}^{k} + C_{n−1,m−k−1}^{k}) x^{n}t^{m} \end{aligned} .

Thus C_{n,m}^{k+1} = C_{n,m}^{k} + C_{n−1,m−k−1}^{k}. Finally, for completeness, we wrote a Quick BASIC program to handle this tedious expansion.

5. Some Closing Remarks. There are a lot more materials concerning applications of generating functions than what we have discussed in this paper. Some examples of the most recent applications can be found in [1] and the papers [7], and [8] by C. Cooper and R. Kennedy.

Finally, the authors would like to thank Mr. Mike Page, Drs. C. Lee, Paul Abbot, and R. Carlson for their helpful suggestions.

\underline{References}

1. H. S. Wilf, Generatingfunctionolgy, Academic Press, New York, New York, 1990.

2. T. W. Hungerford, Algebra, Holt, Rinehart and Winston, New York, New York, 1974.

3. H. B. Fine, A College Algebra, Ginn and Company, New York, New York, 1904.

4. H. S. Hall and S. R. Knight, Higher Algebra, Macmillan, New York, New York, 1964.

5. G. H. Hardy, Divergent Series, Oxford University Press, 1967.

6. V. K. Rohatgi, An Introduction to Probability Theory and Mathematical Statistics, John Wiley and Sons, New York, New York, 1976.

7. C. N. Cooper and R. E. Kennedy, “A Generating Function For the Distribution of the Scores of All Possible Bowling Games,” Mathematics Magazine, 63 (1990), 239–243.

8. R. E. Kennedy and C. N. Cooper, “Substring Statistics,” Mathematics in College, Fall-Winter 1991, 18–25.

9. A. Leon–Garcia, Probability and Random Processes, Addison Wesley, New York, New York, 1989.