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 \(\ap\) stands for taking an apple, \(\ap\pe\) for taking an apple and a pear, and \(\ap\ap\) for taking two apples. You can think of the plus sign as standing for the “exclusive or,” that is, \(\ap+\ba\) 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 \(\ap\ba\text{.}\) We can extend the analogy to mathematical notation by condensing our statement that we take three pieces of fruit to
In this notation \(\ap^3\) stands for taking a multiset of three apples, while \(\ap^2\ba\) 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 \(\{\ap,\pe,\ba\}\text{.}\) 1 This approach was inspired by George Pólya's paper “Picture Writing,” in the December, 1956 issue of the American Mathematical Monthly, page 689. While we are taking a somewhat more formal approach than Pólya, it is still completely in the spirit of his work.
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
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.
Substitute \(x\) for all of \(A\text{,}\) \(P\) and \(B\) (or for the corresponding pictures) in the formula you got in Problem 178 and expand the result in powers of \(x\text{.}\) Give an interpretation of the coefficient of \(x^n\text{.}\)
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 \(\{\ap,\pe,\ba\}\) in which \(\apple\) appears between 1 and three times and \(\pear\) and \(\banana\) 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.
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 2 We are really adapting language introduced by George Pólya. 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
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 the set of all multisets of fruit with between one and three apples, one and two pears, and one and two bananas.
How would you write down a polynomial in the variable \(A\) that says you should take between zero and three apples?
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?
(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^2P^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 \(P_1\) and \(P_2\) 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)\text{,}\) 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)\text{.}\) We call this the product principle for picture enumerators.
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.
Substitute something for \(A\text{,}\) \(P\) and \(B\) in your formula from Problem 181.
Suppose an apple costs 20 cents, a banana costs 25 cents, and a pear costs 30 cents. What should you substitute for \(A\text{,}\) \(P\text{,}\) 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?
For example, to get the cost of the fruit selection \(AP B\) you would want to get \(x^{20} x^{25} x^{30} = x^{75}\text{.}\)
Suppose an apple has 40 calories, a pear has 60 calories, and a banana has 80 calories. What should you substitute for \(A\text{,}\) \(P\text{,}\) 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?
We are going to choose a subset of the set \([n]=\{1,2,\ldots, n\}\text{.}\) 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\text{,}\) 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]\text{?}\) 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\text{?}\) What theorem have we just reproved (a special case of)?
Consider the example with \(n = 2\text{.}\) Then we have two variables, \(x_1\) and \(x_2\) . Forgetting about \(x_2\) , what sum says we either take \(x_1\) or we don't? Forgetting about \(x_1\) , what sum says we either take \(x_2\) or we don't? Now what product says we either take \(x_1\) or we don't and we either take \(x_2\) or we don't?
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 \(x^k\) in the expansion of \((1+x)^n\text{.}\) For this reason, we say that \((1+x)^n\) is the “generating function” for the binomial coefficients \(\binom{n}{k}\text{.}\) More generally, the generating function for a sequence \(a_i\text{,}\) defined for \(i\) with \(0\le i\le n\) is the expression \(\sum_{i=0}^n a_ix^i\text{,}\) and the generating function for the sequence \(a_i\) with \(i\ge 0\) is the expression \(\sum_{i=0}^\infty a_ix^i\text{.}\) 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 In the evolution of our current mathematical terminology, the word function evolved through several meanings, starting with very imprecise meanings and ending with our current rather precise meaning. The terminology “generating function” may be thought of as an example of one of the earlier usages of the term function. 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_{i=0}^\infty x^i\text{,}\) because in order to interpret \(\sum_{i=0}^\infty (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\text{,}\) and in fact infinitely many numbers added together for the coefficient of any \(y^i\text{.}\) (On the other hand, it would be fine to substitute \(y+y^2\) for \(x\text{.}\) Can you see why?)
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.
In the polynomial \((a_0 +a_1x+a_2x^2)(b_0+b_1x+b_2x^2+b_3x^3)\text{,}\) what is the coefficient of \(x^2\text{?}\) What is the coefficient of \(x^4\text{?}\)
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\text{?}\) What is the coefficient of \(x^4\) in
Express this coefficient in the form
where the something is an expression you need to figure out. Now suppose that \(a_3=0\text{,}\) \(a_4=0\) and \(b_4=0\text{.}\) To what is your expression equal after you substitute these values? In particular, what does this have to do with Problem 187?
For the last two questions, try multiplying out something simpler first, say \((a_0 + a_1 x + a_2 x^2 )(b_0 + b_1 x + b_2 x^2 )\) . If this problem seems difficult the part that seems to cause students the most problems is converting the expression they get for a product like this into summation notation. If you are having this kind of problem, expand the product \((a_0 + a_1 x + a_2 x^2 )(b_0 + b_1 x + b_2 x^2 )\) and then figure out what the coefficient of \(x^2\) is. Try to write that in summation notation.
The point of the Problems 187 and Problem 188 is that so long as we are willing to assume \(a_i=0\) for \(i>n\) and \(b_j =0\) for \(j>m\text{,}\) then there is a very nice formula for the coefficient of \(x^k\) in the product
Write down this formula explicitly.
Write down the formulas for the coefficients of \(x^0\text{,}\) \(x^1\text{,}\) \(x^2\) and \(x^3\) in
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
How is this problem different from Problem 189? Is this an important difference from the point of view of the coefficient of \(x^k\text{?}\)
We use the expression you obtained in Problem 190 to define the product of power series. That is, we define the product
to be the power series \(\sum_{k=0}^\infty c_k x^k\text{,}\) 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 Technically we should explicitly state these rules and prove that they are all valid for power series multiplication, but it seems like overkill at this point to do so!
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\text{.}\) After we simplify our product by collecting together all like powers of \(x\text{,}\) 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\text{,}\) 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.
Suppose that we have two sets \(S_1\) and \(S_2\text{.}\) 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)\text{.}\) Suppose further that \(\sum_{i=0}^\infty a_ix^i\) is the generating function for the number of elements \(x_1\) of \(S_1\) of value \(i\text{,}\) that is with \(v_1(x_1)=i\text{.}\) Suppose also that \(\sum_{j=0}^\infty b_j x^j\) is the generating function for the number of elements \(x_2\) of \(S_2\) of value \(j\text{,}\) that is with \(v_2(x_2) = j\text{.}\) Prove that the coefficient of \(x^k\) in
is the number of ordered pairs \((x_1,x_2)\) in \(S_1\times S_2\) with total value \(k\text{,}\) that is with \(v_1(x_1) +v_2(x_2) =k\text{.}\) This is called the product principle for generating functions.
If this problem appears difficult, the most likely reason is because the definitions are all new and symbolic. Focus on what it means for \(\sum_{k=0}^\infty c_kx^k\) to be the generating function for ordered pairs of total value \(k\text{.}\) In particular, how do we get an ordered pair with total value \(k\text{?}\) What do we need to know about the values of the components of the ordered pair?
Problem 191 may be extended by mathematical induction to prove our next theorem.
If \(S_1,S_2,\dots,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 value is \(\prod_{i=1}^n f_i(x)\text{.}\)
Suppose once again that \(i\) is an integer between 1 and \(n\text{.}\)
What is the generating function in which the coefficient of \(x^k\) is \(1\text{?}\) 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\}\text{.}\) Namely, there is only one way to choose a multiset of size \(k\) from \(\{i\}\text{:}\) choose \(i\) exactly \(k\) times.
Express the generating function in which the coefficient of \(x^k\) is the number of 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?
You might try applying the product principle for generating functions to an appropriate power of the generating function you got in the first part of this problem.
In Problem 125 you found a formula for the number of \(k\)-element multisets chosen from an \(n\)-element set. Suppose you use this formula for \(a_k\) in \(\sum_{k=0}^\infty a_kx^k\text{.}\) What do you get the generating function for?
What is the product \((1-x)\sum_{k=0}^n x^k\text{?}\) What is the product
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.
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?
While you could use calculus techniques, there is a much simpler approach. Note that \(1 + x = 1 - (-x)\text{.}\)
Can you see a way to use Problem 194?
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\text{.}\) Do so. This is called the extended binomial theorem. Write down a special case with \(n\) negative, like \(n=-3\text{,}\) to see an interesting surprise that suggests why we do not use this formula later on.
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.
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.
Intepret Problem 197 in terms of multisets.
Recall that a tree is determined by its edge set. Suppose you have a tree on \(n\) vertices, say with vertex set \([n]\text{.}\) We can use \(x_i\) as the picture of vertex \(i\) and \(x_ix_j\) as the picture of the edge \(x_ix_j\text{.}\) Then one possible picture of the tree \(T\) is the product \(P(T) = \prod_{\{i,j\}:i\text{ and }j\text{ are adjacent }}x_ix_j\text{.}\)
Explain why the picture of a tree is also \(\prod_{i=1}^nx_i^{\deg(i)}\text{.}\)
Write down the picture enumerators for trees on two, three, and four vertices. Factor them as completely as possible.
Explain why \(x_1x_2\cdots x_n\) is a factor of the picture of a tree on \(n\) vertices.
Write down the picture of a tree on five vertices with one vertex of degree four, say vertex \(i\text{.}\) 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.
Find a (relatively) simple polynomial expression for the picture enumerator \(\sum_{T \colon T\text{ is a tree on }[n]} P (T)\text{.}\) Prove it is correct.
When you factor out \(x_1 x_2\cdots x_n\) from the enumerator of trees, the result is a sum of terms of degree \(n - 2\text{.}\) (The degree of \(x_1^{i_1} x_2^{i_2} \cdots x_n^{i_n}\) is \(i_1 + i_2 + \cdots + i_n\text{.}\))
Write down the picture (using \(x\)s) of a tree on five vertices with two vertices of degree one, of one with three vertices of degree one, and with four vertices of degree 1. Factor \(x_1 x_2 x_3 x_4 x_5\) out of the picture and look at what is left. How is it related to your vertices of degree one? Now remove the vertices of degree 1 from the tree and write down the picture of the tree that remains. What is special about the vertices of degree 1 of that tree. (You can just barely learn something from this with five vertex trees, so you might want to experiment a bit with six or seven vertex trees.)
The enumerator for trees by degree sequence is the sum over all trees of \(x^{d_1}x^{d_2} \cdots x^{d_n}\text{,}\) where \(d_i\) is the degree of vertex \(i\text{.}\) What is the enumerator by degree sequence for trees on the vertex set \([n]\text{?}\)
