Solutions to Quiz # 10 for Dr. Z.’s Number Theory Course for Dec. 5, 2013

1. An extremely distinct partition of n is a sequence of integers (λ_{1}, λ_{2}, …, λ_{t}) ,

such that

λ_{1} + λ_{2} + … + λ_{t} = n ,

and

λ_{1} − λ_{2} ≥ 2 λ_{2} − λ_{3} ≥ 2 , …, , λ_{t−1} − λ_{t} ≥ 2

and

λ_{t} > 0 ,

Let q(n) be the number of partitions of n, and q(n, k) be the number of exteremely distinct partitions of n whose largest part is k.

(i) (5 points) Explain why

q(n, k) = ∑_{r=1}^{k−2} q(n − k, r) ,

and, of course

q(n, n) = 1 .

(ii) Use the above recurrence, and

q(n) = ∑_{k=1}^{n} q(n, k)

to compute q(n) for 1 ≤ n ≤ 5. Sol. to 1(i): If you take an extremely disctinct partion of n with largest part k, and chop its head (that equals k), what remains is another such partion, but of the smaller number n − k, and whose largest part r, can be either 1, or 2, all the way to r − 2 (it can’t be r − 1 or r). Adding up all these options explains the recurrence. Important Fact: If you have ∑_{a}^{b} and a > b then the answer is always 0.

q(1, 1) = 1

q(2, 1) = ∑_{r=1}^{−1} q(1, r) = 0 , q(2, 2) = 1 ;

q(3, 1) = ∑_{r=1}^{−1} q(2, r) = 0 , q(3, 2) = ∑_{r=1}^{0} q(1, r) = 0 , q(3, 3) = 1 ;

q(4, 1) = ∑_{r=1}^{−1} q(3, r) = 0 , q(4, 2) = ∑_{r=1}^{0} q(2, r) = 0 , q(4, 3) = ∑_{r=1}^{1} q(1, r) = q(1, 1) = 1 ,

q(4, 4) = 1 ;

q(5, 1) = ∑_{r=1}^{−1} q(4, r) = 0 , q(5, 2) = ∑_{r=1}^{0} q(3, r) = 0 , q(5, 3) = ∑_{r=1}^{1} q(2, r) = q(2, 1) = 0 ,

q(5, 4) = ∑_{r=1}^{2} q(1, r) = q(1, 1) + q(1, 2) = 1 + 0 = 1 ,

q(5, 5) = 1 .

Finally q(1) = q(1, 1) = 1 ,

q(2) = q(2, 1) + q(2, 2) = 0 + 1 = 1

q(3) = q(3, 1) + q(3, 2) + q(3, 3) = 0 + 0 + 1 = 1

q(4) = q(4, 1) + q(4, 2) + q(4, 3) + q(4, 4) = 0 + 0 + 1 = 1

q(5) = q(5, 1) + q(5, 2) + q(5, 3) + q(5, 4) + q(5, 5) = 0 + 0 + 0 + 1 + 1 = 2 .

Ans. to 1(ii): q(1) = 1, q(2) = 1, q(3) = 1, q(4) = 1, q(5) = 2.