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.
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.)
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?
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.
\begin{equation*}
x_1+x_2+x_3+x_4\leq n
\end{equation*}
where \(x_1,x_2,x_3,x_4,n\geq 0\) are all integers. Suppose also that \(x_2\geq 2\text{,}\)\(x_3\) is a multiple of \(4\text{,}\) and \(0\leq x_4\leq 3\text{.}\) Let \(c_n\) be the number of solutions of the inequality subject to these restrictions. Find the generating function for the sequence \(\{c_n\colon n\geq 0\}\) and use it to find a closed formula for \(c_n\text{.}\)
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.
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:
Using generating functions, find the number of ways to make change for a \(100\) dollar bill using only dollar coins and $\(1\text{,}\) $\(2\text{,}\) and $\(5\) bills.
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
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).
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\colon n\geq 0\}\text{.}\) In how many ways can she spend exactly € 100 at the chocolate shop? (A computer algebra system will be helpful for finding coefficients.)
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.
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\colon n\geq 0\}\text{.}\)
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?
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\text{.}\))
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.)
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.
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,\dots,x^{10}\) by hand to make sure that you’re on the right track.
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.)
Find the exponential generating function (in closed form, not as an infinite sum) for each infinite sequence \(\{a_n\colon n\geq 0\}\) whose general term is given below.
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.
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.
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\text{,}\) the number of \(b\)’s must be odd, and the number of \(d\)’s is either \(1\) or \(2\text{.}\) Find a closed formula for the coefficients of this exponential generating function.
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
\begin{equation*}
x_1+x_2+x_3+x_4\leq n
\end{equation*}
where \(x_1,x_2,x_3,x_4,n\geq 0\) are all integers. Suppose also that \(x_2\geq 2\text{,}\)\(x_3\) is a multiple of \(4\text{,}\) and \(1\leq x_4\leq 3\text{.}\) Let \(c_n\) be the number of solutions of the inequality subject to these restrictions. Find the generating function for the sequence \(\{c_n\colon n\geq 0\}\) and use it to find a closed formula for \(c_n\text{.}\)
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)\text{,}\) 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.
