Find the total number of partitions of $12$ having unequal positive parts.

829 Views Asked by At

$P(k, n) = P(k - 1, n - 1) + P(k - n, n)$

Let $P^\star(k,n)$ denote the number of partitions of $k$ having exactly $n$ positive parts, all of which are unequal. For example, $P(8, 3)$ implies $8$ can be partitioned as $8 = 2 + 2 + 4,$ but $P^\star(8,3)$ does not.

$P^\star(k, n) = P(k - \binom n2, n)$

We need the $\sum_{i=1}^4P^\star(12,i)$ because $P(k, n)$ is not defined for $P^\star(12,n)$ where $5 \le n \le 12.$

Now,

$P^\star(12,1) = P(12, 1)$

$P^\star(12,2) = P(11, 2)$

$P^\star(12,3) = P(9, 3)$

$P^\star(12,4) = P(6, 4)$

Now we calculate the four $P(k, n)$ above.

$P(12, 1) = 1.$

$P(11, 2) \\ = P(10, 1) + P(9, 2) \\ = 1 + P(8, 1) + P(7, 2) \\ = 1 + 1 + P(6, 1) + P(5, 2) \\ = 1 + 1 + 1 + P(4, 1) + P(3, 2) \\ = 1 + 1 + 1 + 1 + P(2, 1) + P(1, 2) \\ = 1 + 1 + 1 + 1 + 1 \\ = 5.$

$P(9, 3) \\ = P(8, 2) + P(6, 3) \\ = P(7, 1) + P(6, 2) + P(5, 2) + P(3, 3) \\ = 1 + P(5, 1) + P(4, 2) + P(4, 1) + P(3, 2) + 1 \\ =1 + 1 + P(3, 1) + P(2, 2) + 1 + P(2, 1) + P(1, 2) + 1 \\ = 1 + 1 + 1 + 1 + 1 + 1 + 1 \\ = 7.$

$P(6, 4) \\ = P(5, 3) + P(2, 4) \\ = P(4, 2) + P(2, 3) \\ = P(3, 1) + P(2, 2) \\ = 1 + 1 \\ = 2.$

So, the answer to this problem is $1 + 5 + 7 + 2 = 15.$

Does the calculation above make sense to you? Thanks.

1

There are 1 best solutions below

3
On BEST ANSWER

Your answer is correct. As a check, here is a list of the $15$ partitions of $12$ into unequal positive parts: \begin{align*} 12 & = 12\\ & = 1 + 11\\ & = 2 + 10\\ & = 3 + 9\\ & = 4 + 8\\ & = 5 + 7\\ & = 1 + 2 + 9\\ & = 1 + 3 + 8\\ & = 1 + 4 + 7\\ & = 1 + 5 + 6\\ & = 2 + 3 + 7\\ & = 2 + 4 + 6\\ & = 3 + 4 + 5\\ & = 1 + 2 + 3 + 6\\ & = 1 + 2 + 4 + 5 \end{align*}