Instructions
Answer all questions on paper or a tablet using your own handwriting. Put your name, student ID number and
page number at the top of each page. If you use paper make a photo of each page and upload your solutions to
crowdmark. If you use a tablet, export your assignment to .pdf and upload the .pdf to crowdmark.
Textbook Reading
• Sections: 9.1, 9.2,
Course Notes Reading
• Section: 4.4.2
Definitions, Concepts & Keywords
• Construct a generating function for a counting application.
• Find a formula for [x
n]A(x) where A(x) is a rational GF.
• Use Wolfram Alpha or Maple to extract a coefficient of a GF.
Exercises
A. Textbook Questions
9.1 Exercises 2ac, 3.
9.2 Exercises 1de, 2bde.
B. Instructor Questions
Questions on 9.1
1. Execute the following command in Wolfram Alpha:
Coefficient[ (x+xˆ2+xˆ3+xˆ4+xˆ5+xˆ6)ˆ6, x, 18 ]
to compute the coefficient of x
18 in the polynomial (x + x
2 + x
3 + x
4 + x
5 + x
6
)
6
.
Alternatively, if you have Maple, use the command
coeff( (x+xˆ2+xˆ3+xˆ4+xˆ5+xˆ6)ˆ6, x, 18 )
2. For each equation, express the number of integer solutions as the coefficient of a polynomial.
Then use Wolfram Alpha or Maple to calculate the coefficient.
(a) a1 + a2 + a3 = 14 where a1, a2, a3 ≥ 0.
(b) b1 + b2 + b3 = 15 where 2 ≤ b1 ≤ 6, b2 is even and b3 is odd.
3. If a fair die is rolled 5 times, how many ways can the sum of the rolls equal 15?
Use a generating function. Use Wolfram Alpha or Maple to compute the required coefficient.
4. Carol is collecting money from her cousins for a walkathon. Three cousins promise to give her
either $2, $3, or $4 and one promises to give her either $5 or $10. Let an be the number of ways
she can get $n. Give a generating function for an. How many ways can she get $15?
Questions on 9.2
5. Let A(x) = 1 − x + x
2 − x
3 + x
4 − . . . and B(x) = 0 + 1x + 2x
2 + 3x
3 + . . . .
Calculate rational GFs for A(x), B(x), A(x) + B(x) and B0
(x).
6. Let A(x) = 1 − x + x
2 − x
3 + x
4 − . . . . Let cn = [x
n]A(x)
2
. Calculate a formula for cn.
7. Let an be the number of ways to select n balls from a large bag of red, blue, and yellow balls
where the selection must include an even number of blue balls. Write down a generating function for an in closed form.8. Consider the set of six sided die where one dice has the numbers 1, 3, 4, 5, 6, 8 and the other
has the numbers 1, 2, 2, 3, 3, 4 (see figure).
If these two die are rolled at the same time we’ll investigate the possible sums and their frequencies in two ways: by direct enumeration in (a) and (b) below, and by using generating functions
in (c) and (d) below.
(a) Determine the numbers which can occur as the sum of rolling these two dice.
(b) For each number in (a) determine the number of possible ways this sum could be rolled.
From this information, write down the generating polynomial D(x) for the sum when rolling
these two die.
(c) Now, write down the generating polynomial D1(x) for the first dice, and D2(x) for the second
dice.
(d) Verify that D1(x) · D2(x) = D(x) by multiplying the two polynomials in part (c).
(e) How does the generating polynomial D(x) compare to the one for the sum when rolling two
standard six sided die?
9. Determine a formula for the coefficient of x
n for the rational GFs 1/(1 + 2x)
3 and x/(2 − x)
3
.
10. Find a rational GF for the sequence 0, 1, −2, 4, −8, 16, . . . .
Questions on Divide-and-Conquer
11. The recurrence for number of comparisons that the Mergesort algorithm does, assuming n = 2k
,
is C(n) ≤ 2 C(n/2) + n − 1 and C(1) = 0. If the input array A is already sorted, give a recurrence
for the number of comparisons Mergesort does and solve it. Hint: how many comparisons does
the merging algorithm do?
12. Consider the recurrence T(n) = aT(n/b) + h(n) for h(n) = An + B with initial value T(1) = C
where a, b are positive integers with b ≥ 2 and A, B, C are real numbers with A ≥ 0 and C ≥ 0.
Using the method in the proof of Theorem 10.1 solve for T(n). Simplify the formula for the case
a = 1 and for the case a = b, b > 1.