Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 2 / b / Solution

For partitions into distinct parts, using a part $i$ prevents using it again. Hencewhen $1\le i\le 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. The answer is $D(n,n)$, giving $D(4,4)=2$, from $4$ and $3+1$.