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

Observing members: 0 Composing members: 0

I don’t think that it is a good idea that you use the letter F for both functions. From now on I will use g(n,k) to represent when there are exactly n summands and f(n,k) for the way that you describe.

f(n,k)=summation a=1—>n (g(a,k))

Do you want me to find a formula that doesn’t use a summation operator?

PhiNotPi (10133 )

I don’t know what you mean by using F for both functions. p(n) is the number of partitions and f(k,n) is the number of partitions with k or fewer summands. The book I got this from used p for both functions, which I thought might be confusing.

Yes, you only need to add together two terms. One thing that I should have mentioned is that f(n,n) = f(n-1, n) + 1, since there is only one way to have n partitions of n.

@LostInParadise f(3,5) is 5. You left out 1+1+3=5.

PhiNotPi (10133 )

You are right. I should have run it through my program. :)

The number of partitions for fewer than k summands is simply f(k-1,n).
For exactly k summands, notice that each one is of size at least equal to 1. We can subtract 1 from each one, leaving k or fewer summands for n-k, or f(k, n-k). This gives f(k,n) = f(k-1,n) + f(k,n-k).

There is one slight difficulty in that k may be greater than n- k. This can be taken care of by saying that if i > j then f(i,j) = f(j,j). In my program, I used an array which I filled with only entries where k<= n and I set f(k,n) = f(k-1,n) + f(min(k,n-k), n-k).