Homework 5 Solutions#

The write-ups below model the amount of explanation expected in a complete handwritten submission.

A constrained sum#

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

  1. 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. Then find the generating function for the required problem in closed form.

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

Solution.

Approach. Each variable gets its own generating function, in which the exponent records the value of that variable. Choosing , , and independently and adding their values corresponds to multiplying the three generating functions.

(A) The allowed values of are , so The allowed values of are , so The allowed values of are , so

(B) A solution of corresponds to one term from , one term from , and one term from whose product is . Therefore

(C) The answers are the coefficients , , and . The series must go past . 


var('x')
A = x^11 * (1 - x^11) / ((1 - x) * (1 - x^2)^2)
S = A.series(x, 51)
print(S.coefficient(x, 20), S.coefficient(x, 35), S.coefficient(x, 50))

Output: 


15 63 90

Therefore

Check for . Since is odd, must be odd, so . Then , and can be any odd number from to . This gives solutions.

Computing a closed formula for a sum of cubes#

Problem. 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. Write down the generating function in closed form for the sequence .

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

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

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

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

Solution.

Approach. Applying the operator to gives , so it multiplies the th coefficient by . Multiplying by replaces a sequence by its sequence of partial sums.

(A) By the geometric series,

(B) Apply to part (A):

(C) Apply twice more. First, Then

(D) Let and . Since multiplying part (C) by gives

(E) The coefficient of in counts nonnegative solutions of , so by stars and bars Each term in the numerator of shifts exponents by , so Here , which is for , so this formula is valid for all . Factor out : Therefore Check: for , .

Compositions with parts 1, 2, and 3#

Problem. 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. Write the generating function for one part, and explain why counts compositions having exactly parts.

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

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

Solution.

(A) One part has value , , or , and the exponent records its value: Expanding the product means choosing one term from the th factor for each . This choice is exactly the ordered list , and it contributes . So is the number of compositions of with exactly parts from . Different orders come from different choices of terms, so they are counted separately. For , counts the empty composition of .

(B) Every composition has exactly one number of parts . Summing over therefore counts every composition exactly once: Since has no constant term, only contains powers with . Thus each coefficient of the sum is a finite sum, and the geometric-series identity applies:

(C) 


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

Output: 


53798080
[1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927]

Therefore and Check: the compositions of are , so .

Ordered compositions versus restricted partitions#

Problem. 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. 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. Use Sage to compute , , and . Include your Sage code and output with your work. Make sure your Taylor expansion includes the coefficient of .

Solution.

(A) Since order is irrelevant, a choice of parts is determined by the numbers of parts of each size. Its total is The parts of size contribute to the total, so the factor for size is Choosing one term from each factor is choosing , so In Exercise 3, the factors of correspond to the first part, second part, and so on, so and come from different choices of terms and are counted twice. Here each factor corresponds to a part size, not a position, so and both correspond to the single choice , , and are counted once.

(B) 


var('x')
P = 1 / ((1 - x) * (1 - x^3) * (1 - x^4) * (1 - x^6))
T = P.taylor(x, 0, 100)
print(T.coefficient(x, 25), T.coefficient(x, 50), T.coefficient(x, 100))

Output: 


75 425 2835

Therefore