Can you find the equation (see details)?

Not long ago there was a discussion here about computing partitions of a number. In brief, the partitions for a number are the ways of finding sums that add up to it. For example, the 7 partitions of 5 are: 5, 4+1, 3+2, 2+2+1, 2+1+1+1 and 1+1+1+1+1. Therefore p(5)= 7. Note that rearrangements are considered the same partition – 2+2+1 is the same as 2+1+2.

Last year Ken Ono discovered a formula for finding p(n). The formula, however, is not particularly simple. Get back to me if you can figure this out.

There is, however, what mathematicians call a recursive equation for finding partitions, which has been known for quite some time. Recursive equation is just a fancy way of saying that the number of partitions for n can be found from partitions for smaller numbers. I just learned about this equation and wrote a 10 line computer program for generating them. The number of operations is around n^2, not very efficient but good enough for me. Running the program, I found out that the number of partitions for 99 is over 169 million and the number for 200 is over 3 trillion.

See if you can find the recursive equation. Here is what you need to know. Define f(k,n) to be the number of partitions for n where the number of summands is less than or equal to k. For example, f(3,5) = 4 for 5, 4+1, 3+2 and 2+2+1. To start things off we use the fact that f(1,n) = 1. p(n) = f(n,n).

We want to generate a formula for f(k,n) from f(i,j) where i<= k and j<=n and at least one of them is strictly less than. The idea is to break up the partitions into the number where the number of summands is less than k (pretty easy) and where the number of summands is exactly k (takes a little bit of thought). That gives the sum of two terms. If you have been able to follow what I have said so far, you know enough to solve this.