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

Separate integer partitions according to whether they contain a part equal to $i$. Removing one such part is a bijection to partitions of $n-i$ whose parts are at most $i$. The alternatives are disjoint, givingUse $p(i,0)=1$, because the empty integer partition is counted once, and $p(0,n)=0$ for $n>0$, with $p(i,n)=0$ for $n<0$. This Oberon implementation avoids negative recursive arguments:The precondition is $i,n\ge 0$. Each recursive call reduces $i+n$, proving algorithm termination. Every positive part of a partition of $n$ is at most $n$, so the required one-argument count is $P(n,n)$. Counts require a sufficiently wide integer representation.