Generating Functions: exercises

Practice (33)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

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

   1. \(1, 4, 6, 4, 1\)

   2. \(1,1,1,1,1,0,0,1\)

   3. \(0,0,0,1,2,3,4,5\)

   4. \(1,1,1,1,1,1,1\)

   5. \(3,0,0,1,-4,7\)

   6. \(0,0,0,0,1,2,-3,0,1\)

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

   1. \(0,1,1,1,1,1,\dots\)

   2. \(1,0,0,1,0,0,1,0,0,1,0,0,1,\dots\)

   3. \(1,2,4,8,16,32,\dots\)

   4. \(0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,\dots\)

   5. \(1,-1,1,-1,1,-1,1,-1,1,-1,\dots\)

   6. \(\displaystyle 2^8,2^7\binom{8}{1}, 2^6\binom{8}{2},\dots,\binom{8}{8},0,0,0,\dots\)

   7. \(1,1,1,0,0,1,1,1,1,1,1,1,1,1,\dots\)

   8. \(0,0,0,1,2,3,4,5,6,\dots\)

   9. \(3,2,4,1,1,1,1,1,1,\dots\)

   10. \(0,2,0,0,2,0,0,2,0,0,2,0,0,2,\dots\)

   11. \(6,0,-6,0,6,0,-6,0,6,\dots\)

   12. \(\displaystyle 1,3,6,10,15,\dots,\binom{n+2}{2},\dots\)

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

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

   2. \(\displaystyle \frac{1}{1-x^4}\)

   3. \(\displaystyle \frac{x^3}{1-x^4}\)

   4. \(\displaystyle \frac{1-x^4}{1-x}\)

   5. \(\displaystyle \frac{1+x^2-x^4}{1-x}\)

   6. \(\displaystyle \frac{1}{1-4x}\)

   7. \(\displaystyle \frac{1}{1+4x}\)

   8. \(\displaystyle \frac{x^5}{(1-x)^4}\)

   9. \(\displaystyle \frac{x^2+x+1}{1-x^7}\)

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

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

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

   2. \((1+x^3) (x^3+x^4+x^5+\cdots)(x^4+x^5+x^6+x^7+x^8+\cdots)\)

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

   4. \(\displaystyle\frac{x^5}{1-3x^5}\)

   5. \(\displaystyle\frac{1}{(1-x)^3}\)

   6. \(\displaystyle\frac{1}{1-5x^4}\)

   7. \(\displaystyle\frac{x}{1-2x^3}\)

   8. \(\displaystyle\frac{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.

7. Consider the inequality \[\begin{aligned}\end{aligned}\] 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\colon n\geq 0\}\) and use it to find a closed formula for \(c_n\).

   Хариулт

   Because of the inequality, it is easier to count here in the setting where we have \(x_{1}+x_{2}+x_{3}+x_{4}+x_{5} = n\) and \(x_{5}\geq 0\) is an integer along with all the constraints laid out in the exercise. Since there is no constraint on \(x_{1}\) or \(x_{5}\) other than that they are nonnegative integers, the generating function contains a factor of \(1/(1-x)\) for each of these variables. For \(x_{2}\), we have \(x^{2}/(1-x)\) to ensure that \(x_{2}\geq 2\). For \(x_{3}\) to be a multiple of \(4\), the generating function includes \(1/(1-x^{4})\). To have \(0\leq x_{4}\leq 3\), we end up with \(1+x+x^{2}+x^{3}\) in the generating function. Thus, the generating function is \[\begin{aligned}\end{aligned}\]. This generating function simplifies (by factoring \(1-x^{4}\)) to be \(x^{2}/(1-x)^{4}\). Noting that \(1/(1-x)^{4}\) is \(1/6\) times the third derivative of \(1/(1-x)\), we have \[\begin{aligned}\end{aligned}\] and therefore, we have \(c_{n}=\frac{n(n^{2}-1)}{6}\).

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:

    • \(0\)\(2\)
    • \(1\)
    • \(5\)
    • \(4\)
    • 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.

    Хариулт

    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 \[\begin{aligned}\end{aligned}\] 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\colon 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.)

    Хариулт

    The first constraint means we need an even number of boxes of dark chocolate truffles, so we must spend a multiple of €20 on dark chocolate truffles. This contributes a factor of \(1/(1-x^{20})\) to the generating function. Since milk chocolate truffles are €8 per box, we must spend a multiple of 8 that is at least 16 (for two boxes) on milk chocolate truffles. This contributes a factor of \(x^{16}/(1-x^{8})\) to the generating function. For nougat-filled chocolates, she will buy either 0 boxes or 4 boxes, meaning she will spend either €0 or €20. The generating function thus includes \(1+x^{20}\). For milk chocolate bars, since we buy at most 3 at €7/bar, the generating function must include \(1+x^{7}+x^{14}+x^{21}\). Finally, for the 75 \[\begin{aligned}\end{aligned}\]. Putting this into SageMath, we find that \(s_{100}= 16\), so there are \(16\) ways for her to spend €100.

13. Make up a combinatorial problem (similar to those found in this chapter) that leads to the generating function \[\begin{aligned}\end{aligned}\]

14. 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.

15. Use generating functions to find the number of ways to partition \(10\) into odd parts.

16. 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.)

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

18. 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.

    1. \(a_n = 5^n\)

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

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

    4. \(a_n = n!\)

    5. \(a_n = n\)

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

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

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

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

    3. \(\displaystyle \frac{1}{1+x}\)

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

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

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

    2. \(\displaystyle\frac{e^x-e^{-x}}{2}\)

    3. \(\displaystyle\frac{e^x+e^{-x}}{2}\)

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

    5. \(\displaystyle\frac{1}{1-2x}\)

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

21. 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.

22. 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.

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\), 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.

24. 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; and

    • each odd digit must appear an odd number of times.

25. Consider the inequality \[\begin{aligned}\end{aligned}\] 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\colon n\geq 0\}\) and use it to find a closed formula for \(c_n\).

    Хариулт

    Hint:

    Yes, this is very close to . 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 partsone for when \(n\) is even and another for when \(n\) is odd.

26. Prove about the coefficients in the product of two ordinary generating functions.

27. Suppose you wanted to make a really boring fruit basket that contains only apples. Let's also say that you have only \(6\) (identical) apples available. For aesthetic reasons, you insist that the basket contain exactly \(1\), \(3\), or \(4\) apples.

    In how many ways (the apples are identical!) can you make a single fruit basket with one apple?

28. Suppose you wanted to make a really boring fruit basket that contains only apples. Let's also say that you have only \(6\) (identical) apples available. For aesthetic reasons, you insist that the basket contain exactly \(1\), \(3\), or \(4\) apples.

    In how many ways (the apples are identical!) can you make a single fruit basket with five apples?

29. We already know that if we are making a fruit basket with 1, 3, or 4 apples and at most 6 oranges, the generating function would be \[\begin{aligned}\end{aligned}\]. Suppose we now have bananas to add and that we must place at least one banana in a fruit basket. This introduces which factor?

30. If a fruit basket generating function contains a factor that is a polynomial, you know

31. Based on the class prep, which of the following statements do you think are reasonably accurate?

32. Suppose we are making strings using the alphabet \(\{0,1,2,3,4\}\). If the number of times \(4\) appears in the string is at least one and at most four, what factor would be included in a generating function to account for this restriction?

33. Suppose we are making strings using the alphabet \(\{0,1,2,3,4\}\). If the number of times \(2\) appears in the string is a positive even number, what factor would be included in a generating function to account for this restriction?

Өөрийнхөөг турш

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Бүх зүйл Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs