= 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, giving
$$
\boxed{p(i,n)=p(i-1,n)+p(i,n-i)\quad(i\geq1,\ n\geq1).}
$$
Use $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:
``
PROCEDURE P(i, n: INTEGER): INTEGER;
VAR answer: INTEGER;
BEGIN
IF n = 0 THEN answer := 1
ELSIF i = 0 THEN answer := 0
ELSIF i > n THEN answer := P(i-1, n)
ELSE answer := P(i-1, n) + P(i, n-i)
END;
RETURN answer
END P;
PROCEDURE Partitions(n: INTEGER): INTEGER;
BEGIN
RETURN P(n, n)
END Partitions;
``
The <precondition> is $i,n\geq0$. Each <recursive call> reduces $i+n$, proving <algorithm termination>. Every positive part of a partition of $n$ is at most $n$, so \b[the required one-argument count is $P(n,n)$]. Counts require a sufficiently wide <integer> representation.
Back to article page
