
4.1: The Idea of Generating Functions

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

4.1.1 Visualizing Counting with Pictures

Suppose you are going to choose three pieces of fruit from among apples, pears and bananas for a snack. We can symbolically represent all your choices as

Here we are using a picture of a piece of fruit to stand for taking a piece of that fruit. Thus stands for taking an apple, for taking an apple and a pear, and for taking two apples. You can think of the plus sign as standing for the “exclusive or,” that is, would stand for “I take an apple or a banana but not both.” To say “I take both an apple and a banana,” we would write We can extend the analogy to mathematical notation by condensing our statement that we take three pieces of fruit to

In this notation stands for taking a multiset of three apples, while stands for taking a multiset of two apples and a banana, and so on. What our notation is really doing is giving us a convenient way to list all three element multisets chosen from the set .

Suppose now that we plan to choose between one and three apples, between one and two pears, and between one and two bananas. In a somewhat clumsy way we could describe our fruit selections as

$$\bullet$$ 178. Using an A in place of the picture of an apple, a P in place of the picture of a pear, and a B in place of the picture of a banana, write out the formula similar to Formula 4.1 without any dots for left out terms. (You may use pictures instead of letters if you prefer, but it gets tedious quite quickly!) Now expand the product $$(A+A^{2}+A^{3})(P+P^{2})(B+B^{2})$$ and compare the result with your formula.

$$\bullet$$ 179. Substitute $$x$$ for all of $$A, P$$ and $$B$$ (or for the corresponding pictures) in the formula you got in Problem 178 and expand the result in powers of $$x$$. Give an interpretation of the coefficient of $$x^{n}$$. Online hint.

If we were to expand the formula

we would get Formula 4.1. Thus Formula 4.1 and Formula 4.2 each describe the number of multisets we can choose from the set in which appears between one and three times, and and each appear once or twice. We interpret Formula 4.1 as describing each individual multiset we can choose, and we interpret Formula 4.2 as saying that we first decide how many apples to take, and then decide how many pears to take, and then decide how many bananas to take. At this stage it might seem a bit magical that doing ordinary algebra with the second formula yields the first, but in fact we could define addition and multiplication with these pictures more formally so we could explain in detail why things work out. However, since the pictures are for motivation, and are actually difficult to write out on paper, it doesn’t make much sense to work out these details. We will see an explanation in another context later on.

4.1.2 Picture Functions

As you’ve seen, in our descriptions of ways of choosing fruits, we’ve treated the pictures of the fruit as if they are variables. You’ve also likely noticed that it is much easier to do algebraic manipulations with letters rather than pictures, simply because it is time consuming to draw the same picture over and over again, while we are used to writing letters quickly. In the theory of generating functions, we associate variables or polynomials or even power series with members of a set. There is no standard language describing how we associate variables with members of a set, so we shall invent some. By a picture of a member of a set we will mean a variable, or perhaps a product of powers of variables (or even a sum of products of powers of variables). A function that assigns a picture $$P(s)$$ to each member s of a set $$S$$ will be called a picture function. The picture enumerator for a picture function $$P$$ defined on a set $$S$$ will be the sum of the pictures of the elements in $$S$$. In symbols we can write this conveniently as.

$E_{p}(S) = \sum_{s:s \in S}P(s)\.] We choose this language because the picture enumerator lists, or enumerates, all the elements of $$S$$ according to their pictures. Thus Formula 4.1 is the picture enumerator of the set of all multisets of fruit with between one and three apples, one and two pears, and one and two bananas. $$\circ$$ 180. How would you write down a polynomial in the variable A that says you should take between zero and three apples? Online hint. $$\bullet$$ 181. How would you write down a picture enumerator that says we take between zero and three apples, between zero and three pears, and between zero and three bananas? Online hint. $$\cdot$$ 182. (Used in Chapter 6.) Notice that when we used $$A^{2}$$ to stand for taking two apples, and $$P^{3}$$ to stand for taking three pears, then we used the product $$A^{2}P^{3}$$ to stand for taking two apples and three pears. Thus we have chosen the picture of the ordered pair (2 apples, 3 pears) to be the product of the pictures of a multiset of two apples and a multiset of three pears. Show that if $$S_{1}$$ and $$S_{2}$$ are sets with picture functions P1 and P2 defined on them, and if we define the picture of an ordered pair $$(x_{1}, x_{2}) \in S_{1} \times S_{2}$$ to be $$P((x_{1}, x_{2})) = P_{1}(x_{1})P_{2}(x_{2})$$, then the picture enumerator of P on the set $$S_{1} \times S_{2}$$ is $$E_{P_{1}}(S_{1})E_{P_{2}}(S_{2})$$. We call this the product principle for picture enumerators. Online hint. $$\bullet$$ 183. Suppose you are going to choose a snack of between zero and three apples, between zero and three pears, and between zero and three bananas. Write down a polynomial in one variable $$x$$ such that the coefficient of $$x^{n}$$ is the number of ways to choose a snack with $$n$$ pieces of fruit. Online hint. $$\circ$$ 184. Suppose an apple costs 20 cents, a banana costs 25 cents, and a pear costs 30 cents. What should you substitute for $$A, P$$, and $$B$$ in Problem 181 in order to get a polynomial in which the coefficient of $$x^{n}$$ is the number of ways to choose a selection of fruit that costs $$n$$ cents? Online hint. $$\bullet$$ 185. Suppose an apple has 40 calories, a pear has 60 calories, and a banana has 80 calories. What should you substitute for $$A, P$$, and $$B$$ in Problem 181 in order to get a polynomial in which the coefficient of $$x^{n}$$ is the number of ways to choose a selection of fruit with a total of $$n$$ calories? $$\bullet$$ 186. We are going to choose a subset of the set $$[n] = \{1, 2, . . . , n\}$$. Suppose we use $$x_{1}$$ to be the picture of choosing 1 to be in our subset. What is the picture enumerator for either choosing 1 or not choosing 1? Suppose that for each $$i$$ between 1 and $$n$$, we use $$x_{i}$$ to be the picture of choosing $$i$$ to be in our subset. What is the picture enumerator for either choosing $$i$$ or not choosing $$i$$ to be in our subset? What is the picture enumerator for all possible choices of subsets of $$[n]$$? What should we substitute for $$x^{i}$$ in order to get a polynomial in $$x$$ such that the coefficient of $$x^{k}$$ is the number of ways to choose a $$k$$-element subset of $$n$$? What theorem have we just reproved (a special case of)? Online hint. In Problem 186 we see that we can think of the process of expanding the polynomial $$(1+x)^{n}$$ as a way of “generating” the binomial coefficients $$\binom{n}{k}$$ as the coefficients of xk in the expansion of $$(1+x)^{n}$$. For this reason, we say that $$(1+x)^{n}$$ is the “generating function” for the binomial coefficients $$\binom{n}{k}$$. More generally, the generating function for a sequence $$a_{i}$$, defined for $$i$$ with $$0 \leq i \leq n$$ is the expression $$\sum^{n}_{i=0}a_{i}x^{i}$$, and the generating function for the sequence $$a_{i}$$ with $$i \geq 0$$ is the expression $$\sum^{\inf}_{i=0}a_{i}x^{i}$$. This last expression is an example of a power series. In calculus it is important to think about whether a power series converges in order to determine whether or not it represents a function. In a nice twist of language, even though we use the phrase generating function as the name of a power series in combinatorics, we don’t require the power series to actually represent a function in the usual sense, and so we don’t have to worry about convergence.3 Instead we think of a power series as a convenient way of representing the terms of a sequence of numbers of interest to us. The only justification for saying that such a representation is convenient is because of the way algebraic properties of power series capture some of the important properties of some sequences that are of combinatorial importance. The remainder of this chapter is devoted to giving examples of how the algebra of power series reflects combinatorial ideas. Because we choose to think of power series as strings of symbols that we manipulate by using the ordinary rules of algebra and we choose to ignore issues of convergence, we have to avoid manipulating power series in a way that would require us to add infinitely many real numbers. For example, we cannot make the substitution of $$y + 1$$ for $$x$$ in the power series $$\sum^{\inf}_{i=0}x^{i}$$, because in order to interpret $$\sum^{\inf}_{i=0}(y+1)^{i}$$ as a power series we would have to apply the binomial theorem to each of the $$(y+1)^{i}$$ terms, and then collect like terms, giving us infinitely many ones added together as the coefficient of $$y^{0}$$, and in fact infinitely many numbers added together for the coefficient of any $$y^{i}$$. (On the other hand, it would be fine to substitute $$y + y^{2}$$ for $$x$$. Can you see why?) 4.1.4 Power Series For now, most of our uses of power series will involve just simple algebra. Since we use power series in a different way in combinatorics than we do in calculus, we should review a bit of the algebra of power series. $$\circ$$ 187. In the polynomial $$(a_{0} + a_{1}x + a_{2}x_{2})(b_{0} + b_{1}x + b_{2}x_{2} + b_{3}x_{3})$$, what is the coefficient of $$x^{2}$$? What is the coefficient of $$x^{4}$$? $$\circ$$ 188. In Problem 187 why is there a $$b_{0}$$ and a $$b_{1}$$ in your expression for the coefficient of $$x^{2}$$ but there is not a $$b_{0}$$ or a $$b_{1}$$ in your expression for the coefficient of $$x^{4}$$? What is the coefficient of $$x^{4}$$ in \[(a_{0} + a_{1}x + a_{2}x_{2} + a_{3}x_{3} + a_{4}x_{4})(b_{0} + b_{1}x + b_{2}x_{2} + b_{3}x_{3} + b_{4}x_{4})?$

Express this coefficient in the form

$\sum\limits^{4}_{i=0} \text{something},] where the something is an expression you need to figure out. Now suppose that $$a_{3} = 0, a_{4} = 0,$$ and $$b_{4} = 0$$. To what is your expression equal after you substitute these values? In particular, what does this have to do with Problem 187? Online hint. $$\circ$$ 189. The point of the Problems 187 and 188 is that so long as we are willing to assume $$a_{i} = 0$$ for $$i > n$$ and $$b_{j} = 0$$ for $$j > m$$, then there is a very nice formula for the coefficient of xk in the product \[\left(\sum\limits^{n}_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{m}_{j=0}b_{j}x^{j}\right).$

Write down this formula explicitly. Online hint.

$$\bullet$$ 190. Assuming that the rules you use to do arithmetic with polynomials apply to power series, write down a formula for the coefficient of $$x^{k}$$ in the product

$\left(\sum\limits^{n}_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{m}_{j=0}b_{j}x^{j}\right).$

Online hint.

We use the expression you obtained in Problem 190 to define the product of power series. That is, we define the product

$\left(\sum\limits^{n}_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{m}_{j=0}b_{j}x^{j}\right)$

to be the power series $$\sum^{inf}_{k=0}c_{k}x^{k}), where \(c_{k}$$ is the expression you found in Problem 190. Since you derived this expression by using the usual rules of algebra for polynomials, it should not be surprising that the product of
power series satisfies these rules.

4.1.5 Product Principle for Generating Functions

Each time that we converted a picture function to a generating function by substituting $$x$$ or some power of $$x$$ for each picture, the coefficient of $$x$$ had a meaning that was significant to us. For example, with the picture enumerator for selecting between zero and three each of apples, pears, and bananas, when we substituted $$x$$ for each of our pictures, the exponent $$i$$ in the power $$x^{i}$$ is the number of pieces of fruit in the fruit selection that led us to $$x^{i}$$. After we simplify our product by collecting together all like powers of $$x$$, the coefficient of $$x^{i}$$ is the number of fruit selections that use $$i$$ pieces of fruit. In the same way, if we substitute $$x^{c}$$ for a picture, where $$c$$ is the number of calories in that particular kind of fruit, then the $$i$$ in an $$x^{i}$$ term in our generating function stands for the number of calories in a fruit selection that gave rise to $$x^{i}$$, and the coefficient of $$x^{i}$$ in our generating function is the number of fruit selections with $$i$$ calories. The product principle of picture enumerators translates directly into a product principle for generating functions. However, it is possible to give a proof that does not rely on the product principle for enumerators.

$$\bullet$$ 191. Suppose that we have two sets $$S_{1}$$ and $$S_{2}$$. Let $$v_{1}$$ ($$v$$ stands for value) be a function from $$S_{1}$$ to the nonnegative integers and let $$v_{2}$$ be a function from $$S_{2}$$ to the nonnegative integers. Define a new function $$v$$ on the set $$S_{1} \times S_{2}$$ by $$v(x_{1}, x_{2}) = v_{1}(x_{1})+v_{2}(x_{2})$$. Suppose further that $$\sum^{\inf}_{i=0}a_{i}x^{i}$$ is the generating function for the number of elements $$x_{1}$$ of $$S_{1}$$ of value $$i$$, that is, with $$v_{1}(x_{1}) = i$$. Suppose also that $$\sum^{\inf}_{i=0}b_{i}x^{i}$$ is
the generating function for the number of elements $$x_{2}$$ of $$S_{2}$$ of value $$j$$, that is, with $$v_{2}(x_{2}) = j$$. Prove that the coefficient of $$x^{k}$$ in

$\left(\sum\limits^{n}_{i=0}a_{i}x^{i}\right)\left(\sum\limits^{m}_{j=0}b_{j}x^{j}\right)$

is the number of ordered pairs $$(x_{1}, x_{2})$$ in $$S_{1} \times S_{2}$$ with total value $$k$$, that is, with $$v_{1}(x_{1})+v_{2}(x_{2}) = k$$. This is called the product principle for generating functions. Online hint.

Problem 191 may be extended by mathematical induction to prove our next theorem.

Theorem 7 (Product Principle for Generating Functions) If $$S_{1}, S_{2}, . . . , S_{n}$$ are sets with a value function $$v_{i}$$ from $$S_{i}$$ to the nonnegative integers for each $$i$$, and $$f_{i}(x)$$ is the generating function for the number of elements of $$S_{i}$$ of each possible value, then the generating function for the number of $$n$$-tuples of each possible total value is $$\prod\limits^{n}_{i=1}f_{i}(x)$$.

4.1.6 The Extended Binomial Theorem and Multisets

$$\bullet$$ 192. Suppose once again that i is an integer between 1 and $$n$$.

1. What is the generating function in which the coefficient of $$x^{k}$$ is one? This series is an example of what is called an infinite geometric series. In the next part of this problem it will be useful to interpret the coefficient one as the number of multisets of size $$k$$ chosen from the singleton set $$\{i\}$$. Namely, there is only one way to chose a multiset of size $$k$$ from $$\{i\}$$: choose $$i$$ exactly $$k$$
times.
2. Express the generating function in which the coefficient of $$x^{k}$$ is the number of $$k$$-element multisets chosen from $$[n]$$ as a power of a power series. What does Problem 125 (in which your answer could be expressed as a binomial coefficient) tell you about what this generating function equals? Online hint.

$$\circ$$ 193. What is the product $$(1-x)\sum^{n}_{k=0}x^{k}$$? What is the product

$(1-x)\sum\limits^{\inf}_{k=0}x^{k}?$

$$\rightarrow \bullet$$ 194. Express the generating function for the number of multisets of size $$k$$ chosen from $$[n]$$ (where $$n$$ is fixed but $$k$$ can be any nonnegative integer) as a 1 over something relatively simple.

$$\bullet$$ 195. Find a formula for $$(1+x)−n$$ as a power series whose coefficients involve binomial coefficients. What does this formula tell you about how we should define $$\binom{-n}{k}$$ when $$n$$ is positive? Online hint.

$$\bullet$$ 196. If you define $$\binom{-n}{k}$$ in the way you described in Problem 195, you can write down a version of the binomial theorem for $$(x + y)^{n}$$ that is
valid for both nonnegative and negative values of $$n$$. Do so. This is called the extended binomial theorem. Write down a special case with $$n$$ negative, like $$n = -3$$, to see an interesting surprise that suggests why we do not use this formula later on.

$$\rightarrow \bullet$$ 197. Write down the generating function for the number of ways to distribute identical pieces of candy to three children so that no child gets more than 4 pieces. Write this generating function as a quotient of polynomials. Using both the extended binomial theorem and the original binomial theorem, find out in how many ways we can pass out exactly ten pieces. Online hint.

$$\bullet$$ 198. What is the generating function for the number of multisets chosen
from an $$n$$-element set so that each element appears at least $$j$$ times and less than $$m$$ times? Write this generating function as a quotient of polynomials, then as a product of a polynomial and a power series. Online hint.

$$\rightarrow$$ 199. Recall that a tree is determined by its edge set. Suppose you have a tree on $$n$$ vertices, say with vertex set $$[n]$$. We can use $$x_{i}$$ as the picture of vertex $$i$$ and $$x_{i}x_{j}$$ as the picture of the edge $$x_{i}x_{j}$$. Then one possible picture of the tree T is the product $$P(T) = \prod_{(i,j):i}$$ and $$j$$ are adjacent $$x_{i}x_{j}$$.

1. Explain why the picture of a tree is also $$\prod^{n}_{i=1}x_{i}^{\text{deg}(i)}$$.
2. Write down the picture enumerators for trees on two, three, and four vertices. Factor them as completely as possible.
3. Explain why $$x_{1}x_{2} · · · x_{n}$$ is a factor of the picture of a tree on $$n$$
vertices.
4. Write down the picture of a tree on five vertices with one vertex of degree four, say vertex $$i$$. If a tree on five vertices has a vertex of degree three, what are the possible degrees of the other vertices. What can you say about the picture of a tree with a vertex of degree three? If a tree on five vertices has no vertices of degree three or four, how many vertices of degree two does it have? What can you say about its picture? Write down the picture enumerator for trees on five vertices.
5. Find a (relatively) simple polynomial expression for the picture enumerator $$\sum_{T:T}$$ is a tree on $${}_{[n]}P(T)$$. Prove it is correct. Online hint.
6. The enumerator for trees by degree sequence is the sum over all
trees of $$x^{d_{1}}_{1}x^{d_{2}}_{2} \dotsc x^{d_{n}}_{n}$$, where $$d_{i}$$ is the degree of vertex $$i$$. What is the enumerator by degree sequence for trees on the vertex set $$[n]$$?
7. Find the number of trees on $$n$$ vertices and prove your formula correct.