Algorithm for the number of partitions of $n$ into distinct parts

Question

I am looking for an algorithm to find the number of ways of writing $n$ as a sum of positive integers without regard to order with the constraint that all integers in a given partition are distinct. This is described in here and OEIS A000009. I've found an implementation in LISP for Maxima, but I don't know LISP and couldn't really figure out the algorithm.

Answer 1

Let $N(k,n)$ be the algorithm computing the numb rod ways of writing $n$ as the sum of integers greater than $k$. $N(k,n)$ is defined inductively as follow:

• $N(k,n)=0$ if $k>n$;
• $N(k,n)=1$ if $k=n$;
• $N(k,n)=N(k+1,n)+N(k+1,n-k)$

Is that helpful?