Homework 5#

Due: Thursday, October 1, 2026 23:59 Submit: Gradescope, through Blackboard’s assignment area.

Please write your homework by hand. Start each exercise on a new page, scan your work to a legible PDF, and clearly mark the pages associated with every exercise. For the computational parts, you may include a printout or screenshot of your Sage code and output.

1. (A constrained sum)#

Points: 14

Let be the number of ordered triples of integers satisfying where is nonnegative and even, is positive and odd, and .

  1. 6 points. Let , , and be the generating functions for the allowed choices of , , and , respectively. Write each generating function both as a series and in closed form.

  2. 2 points. Then find the generating function for the required problem in closed form.

  3. 6 points. Use Sage to find the number of solutions for , , and . Include your Sage code and output with your work (screenshot is fine)

Need a free hint?#

For part (C), begin with var('x'), define using the closed form from part (A) and (B), and use A.series(variable, order) before extracting the three coefficients. Extract coefficients with A.series(variable,order).coefficient(variable,power)

2. (Computing a closed formula for a sum of cubes)#

Points: 16

In this exercise we use generating functions to compute a closed formula for the sum of the cubes of numbers from to .

Follow the steps below and show the computations used in each step.

  1. 2 points. Write down the generating function in closed form for the sequence

  2. 2 points. Find the generating function in closed form for the sequence

  3. 2 points. Find the generating function in closed form for the sequence

  4. 3 points. Find the generating function in closed form for the sum for cubes up to .

  5. 6 points. Find and use that to extract the coefficient of from .

3. (Compositions with parts 1, 2, and 3)#

Points: 12

Let be the number of ordered compositions of whose parts all belong to . Include one empty composition when . For example, and are different compositions of .

  1. 3 points. Write the generating function for one part, and explain why counts compositions having exactly parts.

  2. 4 points. Sum over all possible numbers of parts to prove that

  3. 5 points. Use Sage to find . Also report the list . Include your Sage code and output with your work.

You may use https://sagecell.sagemath.org/. The following sample shows how to extract coefficients from a power series; adapt it to this problem.


var('x')
F = 1 / (1 - x - x^2)
T = F.taylor(x, 0, 30)
print(T.coefficient(x, 20))
print([T.coefficient(x, k) for k in range(11)])

Need a free hint?#

For one part, the exponent records its value. A composition has a unique number of parts, so summing the powers neither misses nor repeats any composition.

4. (Ordered compositions versus restricted partitions)#

Points: 10

Let be the number of ways to write as a sum of parts chosen from where each part size may be used any number of times and order is irrelevant. Thus and represent the same choice of parts.

  1. 5 points. Model with an ordinary generating function . Write and explain one factor for each allowed part size. In particular, explain why this model is a product of factors rather than the sequence construction used in Exercise 3.

  2. 5 points. Use Sage to compute , , and . Include your Sage code and output with your work. Make sure your Taylor expansion includes the coefficient of .