MathDB

Let

p(n)

be the number of partitions of the natural number

n

into natural summands. The diversity of a partition is by definition the number of different summands in it. Denote by

q(n)

the sum of the diversities of all the

p(n)

partitions of

n

. (For example,

p(4) = 5

, the five distinct partitions of

4

being

4, 3 + 1, 2+2, 2 + 1 + 1, 1 + 1 + 1 + 1,

and

g(4) =1 + 2+1+ 2+1 = 7

.) Prove that, for all natural numbers

n

, (a)

q(n)= 1 + P(1) + P(2) + p(3) + ...+ p(n -1)

, (b)

q(n) < \sqrt{2n} p(n)

.
(AV Zelevinskiy, Moscow)

Problem Statement