Tucker 6.3: Selected Solutions

Tucker 6.3: Selected Solutions

3. Find a generating function for the number of ways to write the integer r as a sum of positive integers in which no integer appears more than three times.

Solution. This is the same as the number of integer solutions to

1*e₁ + 2*e₂ + 3*e₃ + ... r*e_r

with the conditions 0 <= e_i <= 3 for all i.

The generating function that models this is

(1+x+x²+x³) * (1+x²+x⁴+x⁶) * (1+x³+x⁶+x⁹) * ... (1+x^k+x^2k+x^3k) * ...

7. (a) Show that the number of partitions of 10 into distinct parts (integers) is equal to the number of partitions of 10 into odd parts by listing partitions of these two types.

Solution.

Distinct: 10, 1+9, 2+8, 3+7, 4+6, 1+4+5, 1+3+6, 1+2+7, 2+3+5, 1+2+3+4.

Odd: 1+1+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+1+3, 1+1+1+1+3+3, 1+3+3+3, 1+1+3+5, 1+1+1+1+1+5, 5+5, 1+1+1+7, 3+7, 1+9.

7. (b) Show algebraically that the generating function for partitions of r into distinct parts equals the generating function for partitions of r into odd parts, and hence the numbers of these two types of partitions are equal.

Solution. (1+x) (1+x²) (1+x³) ... = ((1-x²)/(1-x)) ((1-x⁴)/(1-x²)) ((1-x⁶)/(1-x³)) ... = ((1-x²) (1-x⁴) (1-x⁶)...) / ((1-x) (1-x²) (1-x³) ...) = [after cancellation] 1 / ((1-x) (1-x³) (1-x⁵) ...)

9. (a) Prove the result in Example 3 by induction. Namely, that if g^*(x) = (1+x) (1+x²) (1+x⁴) (1+x⁸) (1+x¹⁶)... then (1-x) g^*(x) = 1.

Solution.

Let g₀(x) := 1-x² and for k > 0 let g_k(x) := g_k-1(x)(1+x^{2^k}).

First, we claim that g_k(x) = 1-x^{2^k+1} for k >= 0. This is true by definition for k = 0, and by induction for greater k:

g_k(x) := g_k-1(x) (1+x^{2^k}) = (1-x^{2^k}) (1+x^{2^k}) = 1-x^{2^k+1}

Next, we claim that for k >= 0 and any r < 2^k+1, we have [x^r] g_k(x) = [x^r] (1-x) g^*(x).

This is true, since g_k(x) is a partial product of (1-x) g^*(x), none of whose remaining terms contribute to coefficients of powers of x less than x^{2^k+1}.

We have therefore shown that the coefficient of unity in the desired power series is one, and that the coefficient of any positive power of x less than any arbitrary power of two is zero. That is, the power series is equal to 1.

9. (b) Prove the result of Example 3 directly by recursively substituting (1+x^k) = (1-x^2k)/(1-x^k) in g^*(x).

Solution. (1-x) g^*(x) = (1-x) (1+x) (1+x²) (1+x⁴) (1+x⁸) ... = (1-x) ((1+x²)/(1-x)) ((1+x⁴)/(1-x²)) ((1+x⁸)/(1-x⁴)) ... = ((1-x) (1+x²) (1+x⁴) (1+x⁸) ...) / ((1-x) (1-x²) (1-x⁴)...) = 1, after completely cancelling the numerator and denominator.

11. Let R(r,k) denote the number of partitions of the integer r into k parts.

(a) Show that R(r,k) = R(r-1,k-1) + R(r-k, k)

Solution. The partitions of r into k parts can be divided into two sets: those which include a 1, and those which do not. There are R(r-1,k-1) of the former, as every partition of r-1 into k-1 can be turned into a partition of r into k by appending a 1 and vice versa. There are R(r-k, k) of the latter, as every partition of r-k into k can be turned into a partition of r into k by increasing the size of each part by one and vice versa.

11. (b) Show that Sum(k=1..r, R(n-r,k)) = R(n,r).

Solution. R(n-r,0) + R(n-r,1) + R(n-r,2) + R(n-r,3) + ... + R(n-r,r) = R(n-r+1,1) + R(n-r,2) + R(n-r,3) + ... + R(n-r,r) = R(n-r+2,2) + R(n-r,3) + ... + R(n-r,r) = R(n-r+3,3) + ... + R(n-r,r) = ... = R(n-1,r-1) + R(n-r,r) = R(n,r) applying part (a) repeatedly with r = n-r+1, n-r+2, n-r+3, ... and k = 1, 2, 3, ....