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.
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.