8.8: Exercises

Computer algebra systems can be powerful tools for working with generating functions. However, unless an exercise specifically suggests that you use a computer algebra system, we strongly encourage you to solve the problem by hand. This will help you develop a better understanding of how generating functions can be used. You might consider editing the content of the SageMathCells in Section 8.2 to assist with solving problems here where a computer algebra system is suggested, and in some cases, we have included a SageMathCell within the exercise for you to use.

For all exercises in this section, “generating function” should be taken to mean “ordinary generating function.” Exponential generating functions are only required in exercises specifically mentioning them.

1. For each finite sequence below, give its generating function.

a. 1, 4, 6, 4, 1 b. 1,1,1,1,1,0,0,1

c. 0,0,0,1,2,3,4,5 d. 1,1,1,1,1,1,1

e. 3,0,0,1,-4,7 f. 0,0,0,0,1,2,-3,0,1

2. For each infinite sequence suggested below, give its generating function in closed form, i.e., not as an infinite sum. (Use the most obvious choice of form for the general term of each sequence.)

a. 0,1,1,1,1,1,... b. 1,0,0,1,0,0,1,0,0,1,0,0,1,...

c. 1,2,4,8,16,32 d. 0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,...

e. 1,-1,1,-1,1,-1,1,-1,1,-1,... f. \(2^8, 2^7 \dbinom{8}{1}, 2^6 \dbinom{8}{2}, ..., \dbinom{8}{8},0,0,0,...\)

g. 1,1,1,0,0,1,1,1,1,1,1,1,1,1,... h. 0,0,0,1,2,3,4,5,6,...

i. 3,2,4,1,1,1,1,1,1,... j. 0,2,0,0,2,0,0,2,0,0,2,0,0,2,...

k. 6,0,-6,0,6,0,-6,0,6,... l. \(1,3,6,10,15,..., \dbinom{n+2}{2},...\)

3. For each generating function below, give a closed form for the \(n^{th}\) term of its associated sequence.

a. \((1+x)^{10}\)

b. \(\dfrac{1}{1-x^4}\)

c. \(\dfrac{x^3}{1-x^4}\)

d. \(\dfrac{1-x^4}{1-x}\)

e. \(\dfrac{1+x^2-x^4}{1-x}\)

f. \(\dfrac{1}{1-4x}\)

g. \(\dfrac{1}{1+4x}\)

h. \(\dfrac{x^5}{(1-x)^4}\)

i. \(\dfrac{x^2+x+1}{1-x^7}\)

j. \(3x^4+7x^3-x^2+10+ \dfrac{1}{1-x^3}\)

4. Find the coefficient on \(x^{10}\) in each of the generating functions below.

a. \((x^3+x^5+x^6)(x^4+x^5+x^7)(1+x^5+x^{10}+x^{15}+ \cdot \cdot \cdot)\)

b. \((1+x^3)(x^3+x^4+x^5+ \cdot \cdot \cdot)(x^4+x^5+x^6+x^7+x^8+ \cdot \cdot \cdot)\)

c. \((1+x)^{12}\)

d. \(\dfrac{x^5}{1-3x^5}\)

e. \(\dfrac{1}{(1-x)^3}\)

f. \(\dfrac{1}{1-5x^4}\)

g. \(\dfrac{x}{1-2x^3}\)

h. \(\dfrac{1-x^{14}}{1-x}\)

5. Find the generating function for the number of ways to create a bunch of n balloons selected from white, gold, and blue balloons so that the bunch contains at least one white balloon, at least one gold balloon, and at most two blue balloons. How many ways are there to create a bunch of 10 balloons subject to these requirements?

6. A volunteer coordinator has 30 identical chocolate chip cookies to distribute to six volunteers. Use a generating function (and computer algebra system) to determine the number of ways she can distribute the cookies so that each volunteer receives at least two cookies and no more than seven cookies.

//Code

7. Consider the inequality

\(x_1+x_2+x_3+x_4 \leq n\)

where \(x_1,x_2,x_3,x_4,n \geq 0\) are all integers. Suppose also that \(x_2 \geq 2\), \(x_3\) is a multiple of 4, and \(0 \leq x_4 \leq 3\). Let \(c_n\) be the number of solutions of the inequality subject to these restrictions. Find the generating function for the sequence {\(c_n:n \geq 0\)} and use it to find a closed formula for \(c_n\).

8. Find the generating function for the number of ways to distribute blank scratch paper to Alice, Bob, Carlos, and Dave so that Alice gets at least two sheets, Bob gets at most three sheets, the number of sheets Carlos receives is a multiple of three, and Dave gets at least one sheet but no more than six sheets of scratch paper. Without finding the power series expansion for this generating function (or using a computer algebra system!), determine the coefficients on \(x^2\) and \(x^3\) in this generating function.

9. What is the generating function for the number of ways to select a group of \(n\) students from a class of \(p\) students?

10. Using generating functions, find a formula for the number of different types of fruit baskets containing of \(n\) pieces of fruit chosen from pomegranates, bananas, apples, oranges, pears, and figs that can be made subject to the following restrictions:

• there are either 0 or 2 pomegranates
• there is at least 1 banana
• the number of figs is a multiple of 5
• there are at most 4 pears
• there are no restrictions on the number of apples or oranges.

How many ways are there to form such a fruit basket with \(n=25\) pieces of fruit?

11. Using generating functions, find the number of ways to make change for a 100 dollar bill using only dollar coins and $1, $2, and $5 bills.

//Code

Hint

Find the partial fractions expansion for your generating function. Be careful here, as you want a partial fraction expansion in which all coefficients for your denominator polynomials have integer coefficients. The partial_fraction() method in SageMath should be useful here, and pretty_print will make it easier to read. Once you have the right partial fractions expansion, you may find the following identity helpful

\(\dfrac{p(x)}{1+x+x^2+ \cdot \cdot \cdot + x^k} = \dfrac{p(x)(1-x)}{1-x^{k+1}}\),

where \(p(x)\) will be a polynomial in this instance.

12. A businesswoman is traveling in Belgium and wants to buy chocolates for herself, her husband, and their two daughters. A store has dark chocolate truffles (€ 10/box), milk chocolate truffles (€ 8/box), nougat-filled chocolates (€ 5/box), milk chocolate bars (€ 7/bar), and 75% cacao chocolate bars (€ 11/bar). Her purchase is to be subject to the following:

• Only the daughters like dark chocolate truffles, and her purchase must ensure that each daughter gets an equal number of boxes of them (if they get any).
• At least two boxes of milk chocolate truffles must be purchased.
• If she buys any boxes of nougat-filled chocolates, then she buys exactly enough that each family member gets precisely one box of them.
• At most three milk chocolate bars may be purchased.
• There are no restrictions on the number of 75% cacao chocolate bars.

Let \(s_n\) be the number of ways the businesswoman can spend exactly € \(n\) (not buy \(n\) items!) at this chocolate shop. Find the generating function for the sequence \(\{s_n:n \geq 0\}\). In how many ways can she spend exactly € 100 at the chocolate shop? (A computer algebra system will be helpful for finding coefficients.)

//Code

13. Bags of candy are being prepared to distribute to the children at a school. The types of candy available are chocolate bites, peanut butter cups, peppermint candies, and fruit chews. Each bag must contain at least two chocolate bites, an even number of peanut butter cups, and at most six peppermint candies. The fruit chews are available in four different flavors—lemon, orange, strawberry, and cherry. A bag of candy may contain at most two fruit chews, which may be of the same or different flavors. Beyond the number of pieces of each type of candy included, bags of candy are distinguished by using the flavors of the fruit chews included, not just the number. For example, a bag containing two orange fruit chews is different from a bag containing a cherry fruit chew and a strawberry fruit chew, even if the number of pieces of each other type of candy is the same.

a. Let \(b_n\) be the number of different bags of candy with \(n\) pieces of candy that can be formed subject to these restrictions. Find the generating function for the sequence \(\{b_n:n \geq 0\}\).

b. Suppose the school has 400 students and the teachers would like to ensure that each student gets a different bag of candy. However, they know there will be fights if the bags do not all contain the same number of pieces of candy. What is the smallest number of pieces of candy they can include in the bags that ensures each student gets a different bag of candy containing the same number of pieces of candy?

14. Make up a combinatorial problem (similar to those found in this chapter) that leads to the generating function

\(\dfrac{(1+x^2+x^4)x^2}{(1-x)^3(1-x^3)(1-x^{10})}\).

15. Tollbooths in Illinois accept all U.S. coins, including pennies. Carlos has a very large supply of pennies, nickels, dimes, and quarters in his car as he drives on a tollway. He encounters a toll for $0.95 and wonders how many different ways he could use his supply of coins to pay the toll without getting change back. (A computer algebra system is probably the best way to get the required coefficient once you have a generating function, since you're not asked for the coefficient on \(x^n\).)

a. Use a generating function and computer algebra system to determine the number of ways Carlos could pay his $0.95 toll by dropping the coins together into the toll bin. (Assume coins of the same denomination cannot be distinguished from each other.)

b. Suppose that instead of having a bin into which motorists drop the coins to pay their toll, the coins must be inserted one-by-one into a coin slot. In this scenario, Carlos wonders how many ways he could pay the $0.95 toll when the order the coins are inserted matters. For instance, in the previous part, the use of three quarters and two dimes would be counted only one time. However, when the coins must be inserted individually into a slot, there are \(10=C(5,2)\) ways to insert this combination. Use a generating function and computer algebra system to determine the number of ways that Carlos could pay the $0.95 toll when considering the order the coins are inserted.

// Code

Hint

For part b, you really want an ordinary generating function and not an exponential generating function, despite the fact that order matters. Once you think you have a generating function that works, you might check the coefficients on \(x^5,…,x^{10}\) by hand to make sure that you're on the right track.

16. List the partitions of 9. Write a D next to each partition into distinct parts and an O next to each partition into odd parts.

17. Use generating functions to find the number of ways to partition 10 into odd parts.

18. What is the smallest integer that can be partitioned in at least 1000 ways? How many ways can it be partitioned? How many of them are into distinct parts? (A computer algebra system will be helpful for this exercise.)

19. What is the generating function for the number of partitions of an integer into even parts?

20. Find the exponential generating function (in closed form, not as an infinite sum) for each infinite sequence \(\{a_n:n \geq 0\}\) whose general term is given below.

a. \(a_n = 5^n\)

b. \(a_n = (-1)^n2^n\)

c. \(a_n = 3^{n+2}\)

d. \(a_n = n!\)

e. \(a_n = n\)

f. \(a_n = 1/(n+1)\)

21. For each exponential generating function below, give a formula in closed form for the sequence \(\{a_n:n \geq 0\}\) it represents.

a. \(e^{7x}\)

b. \(x^2e^{3x}\)

c. \(\dfrac{1}{1+x}\)

d. \(e^{x^4}\)

22. Find the coefficient on \(x^{10}/10!\) in each of the exponential generating functions below.

a. \(e^{3x}\)

b. \(\dfrac{e^x-e^{-x}}{2}\)

c. \(\dfrac{e^x+e^{-x}}{2}\)

d. \(xe^{3x}-x^2\)

e. \(\dfrac{1}{1-2x}\)

f. \(e^{x^2}\)

23. Find the exponential generating function for the number of strings of length n formed from the set \(\{a,b,c,d\}\) if there must be at least one \(a\) and the number of \(c\)'s must be even. Find a closed formula for the coefficients of this exponential generating function.

24. Find the exponential generating function for the number of strings of length n formed from the set \(\{a,b,c,d\}\) if there must be at least one \(a\) and the number of \(c\)'s must be odd. Find a closed formula for the coefficients of this exponential generating function.

25. Find the exponential generating function for the number of strings of length \(n\) formed from the set \(\{a,b,c,d\}\) if there must be at least one \(a\), the number of \(b\)'s must be odd, and the number of \(d\)'s is either 1 or 2. Find a closed formula for the coefficients of this exponential generating function.

26. Find the exponential generating function for the number of alphanumeric strings of length \(n\) formed from the 26 uppercase letters of the English alphabet and 10 decimal digits if

• each vowel must appear at least one time
• the letter \(T\) must appear at least three times
• the letter \(Z\) may appear at most three times
• each even digit must appear an even number of times
• each odd digit must appear an odd number of times

27. Consider the inequality

\(x_1+x_2+x_3+x_4 \leq n\)

where \(x_1,x_2,x_3,x_4,n \geq 0\) are all integers. Suppose also that \(x_2 \geq 2\), \(x_3\) is a multiple of 4, and \(1 \leq x_4 \leq 3\). Let \(c_n\) be the number of solutions of the inequality subject to these restrictions. Find the generating function for the sequence \(\{c_n:n \geq 0\}\) and use it to find a closed formula for \(c_n\).

Hint

Yes, this is very close to Exercise 8.8.7. However, the bounds on \(x_4\) are different here. You might try using a computer algebra system to expedite finding the partial fractions expansion, which will have several terms whose power series you can work with quickly. For the term involving \(1/(1+x^2)\), work out the series by hand. You may find that your solution to this problem has two parts—one for when \(n\) is even and another for when \(n\) is odd.

28. Prove Proposition 8.3 about the coefficients in the product of two ordinary generating functions.