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.
[Math] Algorithm for the number of partitions of $n$ into distinct parts
algorithmscomputational mathematicsinteger-partitionsnumber theorysequences-and-series
Related Solutions
I'll give a sketch of the bijective proof; ask me if there's some part you don't understand and need fleshed out (or maybe someone else will post a detailed version).
The important idea is that every number can be expressed uniquely as a power of 2 multiplied by an odd number. (Divide the number repeatedly by 2 till you get an odd number.) For instance, $120 = 2^3 \times 15$ and $68 = 2^2 \times 17$ and $81 = 2^0 \times 81$.
Odd parts -> Distinct parts
Suppose you are given a partition of n into odd parts. Count the number of times each odd number occurs: suppose $1$ occurs $a_1$ times, similarly $3$ occurs $a_3$ times, etc. So $n = a_11 + a_33 + a_55 + \cdots$.
Now write each $a_i$ "in binary", i.e., as a sum of distinct powers of two. So you have $n = (2^{b_{11}}+2^{b_{12}}+\cdots)1 + (2^{b_{31}}+2^{b_{32}}+\cdots)3 + \cdots$.
Now just get rid of the brackets, and note that all terms are distinct. (Why?)
E.g. for $20 = 5+3+3+3+1+1+1+1+1+1$, which is a partition of $20$ into odd parts, we do
$20 = (1)5 + (3)3 + (6)1$
$20 = (1)5 + (2+1)3 + (4+2)1$, so you get the partition
$20 = 5 + 6 + 3 + 4 + 2$ in which all parts are distinct.
Distinct parts -> Odd parts
Given a partition into distinct parts, we can write each part as a power of 2 multiplied by an odd number, and collect the coefficients of each odd number, and write the odd number those many times, to get a partition into odd parts.
So for example with $20 = 5+6+3+4+2$ which is a partition of $20$ into distinct parts, we write
$20 = 5 + (2)3 + 3 + (4)1 + (2)1$, and then collect coefficients of the odd numbers $5$, $3$ and $1$:
$20 = 5 + (2+1)3 + (4+2)1$
$20 = 5+3+3+3+1+1+1+1+1+1$, which was our original odd partition.
Aside: you asked about the bijective proof, but I cannot resist mentioning that when Euler proved this theorem about partitions, it was with a proof that used generating functions. (When you understand both, maybe you can think about whether this proof is related to the bijective proof.)
Sketch: Let $D(n)$ denote the number of partitions into distinct parts, and $O(n)$ denote the number of partitions into odd parts. Then we have:
$$ \begin{align} \sum_{n\ge0}D(n)x^n &= (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)\cdots \\ &= \frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}\frac{1-x^8}{1-x^4}\frac{1-x^{10}}{1-x^5}\cdots \\ &= \frac{1}{(1-x)(1-x^3)(1-x^5)\cdots} \\ &= (1+x+x^{1+1}+\cdots)(1+x^3+x^{3+3}+\cdots)(1+x^5+x^{5+5}+\cdots) \\ &= \sum_{n\ge0}O(n)x^n \end{align} $$ which proves the theorem.
The last number is either a $1$, a $2$, or a $3$. If it's a $1$, there are $\lambda(n-1)$ ways to fill in the preceding numbers; if it's a $2$, there are $\lambda(n-2)$ ways; if it's a $3$, $\lambda(n-3)$.
This gives us the recursive equation $$ \lambda(n)=\lambda(n-1)+\lambda(n-2)+\lambda(n-3) $$ which, along with the initial values $\lambda(1)=1$, $\lambda(2)=2$, $\lambda(3)=4$ you've computed, is enough to compute $\lambda(n)$ for any $n$: $$ \lambda(4)=1+2+4=7\\ \lambda(5)=2+4+7=13\\ \lambda(6)=4+7+13=24 $$ and so on.
This is a homogeneous linear difference equation. You could work out an formula for $\lambda(n)$ using the method given in the link, but it would involve the roots of an irreducible cubic polynomial. So for most practical purposes it's probably better to just use the recursion.
Best Answer
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:
Is that helpful?