= Solution
For <partitions into distinct parts>, using a part $i$ prevents using it again. Hence
$$
\boxed{d(i,n)=d(i-1,n)+d(i-1,n-i)}
$$
when $1\leq i\leq n$, with $d(i,0)=1$, $d(0,n)=0$ for $n>0$, and $d(i,n)=0$ for $n<0$. When $i>n$, use $d(i,n)=d(i-1,n)$. Thus change the second call in the final branch of `P` to `D(i-1, n-i)` and rename all calls to `D`. The same split into two disjoint classes proves correctness; its second class removes its unique largest allowed part. \b[The answer is $D(n,n)$], giving $D(4,4)=2$, from $4$ and $3+1$.
Back to article page
