# 1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,… (partition numbers): What is the recurrence relation / recursive formula / closed formula for this?

I have already read this:

Number partition - prove recursive formula

But the formula from the above link requires a parameter k which is the required number of partitions, but I would like to partition it as far as it could. What I am finding is the partition number of a positive integer n, where partition number means the number of different "partitions" of n. A partition of n is an unordered list of positive integers less than or equals to n, which add to up n. Here are some examples:

1 = 1            # So T(1) = 1
2 = 2
= 1+1          # So T(2) = 2
3 = 3
= 2+1
= 1+1+1        # So T(3) = 3
4 = 4
= 3+1
= 2+2
= 2+1+1
= 1+1+1+1+1    # So T(4) = 5
5 = 5
= 4+1
= 3+2
= 3+1+1
= 2+2+1
= 2+1+1+1
= 1+1+1+1+1    # So T(5) = 7


I would like to find T(n) for n >= 1 in terms of T(i) where 1 <= i < n (a recurrence relation), or better, in terms of n (a closed formula). I would also like to get rid of $\sum$s and $\prod$s, if possible. (I guess it is not avoidable for a closed formula, so I ask for a recurrence one hoping to get rid of them)

Thanks in advance!

• Not quite a closed formula or a recurrence, but here is a nice generating function $\sum_{n=0}^{\infty}T(n)x^n = \Pi_{n=1}^{\infty}\frac{1}{1-x^n}$ – Nate Mar 16 '15 at 21:19
• Have you already read through the Wikipedia, Wolfram Math World, and Math Overflow articles on the subject, or tried googling phrases like exact formula partition , Euler partition , Rademacher partition , Ramanujan partition , Hardy partition , etc. ? – Lucian Mar 17 '15 at 2:10
• @Nate : My main reason for asking this question is to compute the value with a program, so it seems that infinite sum or product is not a choice for me. (And I'm not familiar with "generating function" too.) Thanks for your comment! – Siu Ching Pong -Asuka Kenji- Mar 17 '15 at 2:49
• @Lucian : Thanks for your nice articles! I have read them before, now I re-read them, and still can't find my answer. I basically need a "generating function"-free, SIGMA-free, PI-free solution, if possible. This is because I need to implement it efficiently in a program. The closest solution I found from your articles may be the 3(3k - 1) / 2 formula, but unfortunately it is an infinite sum (as far as I understand). – Siu Ching Pong -Asuka Kenji- Mar 17 '15 at 3:00
• Ramanujan gave an exact formula for the partition function using an integral, but I bet that evaluating it is non-trivial. – Lucian Mar 17 '15 at 3:06

## 2 Answers

$T(0)=1$ and, for $n\gt0,$ $$T(n)=T(n-1)+T(n-2)-T(n-2-3)-T(n-3-4)+T(n-3-4-5)+T(n-4-5-6)-T(n-4-5-6-7)-T(n-5-6-7-8)+\cdots$$ $$=T(n-1)+T(n-2)-T(n-5)-T(n-7)+T(n-12)+T(n-15)-T(n-22)-T(n-26)+T(n-35)+T(n-40)-\cdots$$ where it is understood that $T(n)=0$ when $n\lt0.$

For example: $$T(10)=T(9)+T(8)-T(5)-T(3)=30+22-7-3=42$$ $$T(11)=T(10)+T(9)-T(6)-T(4)=42+30-11-5=56$$ $$T(12)=T(11)+T(10)-T(7)-T(5)+T(0)=56+42-15-7+1=77$$

This is Euler's pentagonal numbers theorem. The sequence $$1,\ 2,\ 5,\ 7,\ 12,\ 15,\ 22,\ 26,\ 35,\ 40,\ \dots$$ is OEIS sequence A001318: Generalized pentagonal numbers; the $(2n-1)^{\text{st}}$ term is $$n+(n+1)+\cdots+(2n-1)=\frac{n(3n-1)}2$$ and the $(2n)^{\text{th}}$ term is $$(n+1)+(n+2)+\cdots+(2n)=\frac{n(3n+1)}2.$$

• Please describe more about the numbers 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, ... Are they form the same the sequence as A001318: Generalized pentagonal numbers (link)? – Siu Ching Pong -Asuka Kenji- Mar 29 '16 at 12:25
• @SiuChingPong-AsukaKenji- Thank you. I edited the OEIS reference into my answer. – bof Mar 29 '16 at 20:22

The recurrence relation you provided above is a solution to what you require. The extra $k$ parameter will need to be evaluated $n$ times.

Using this: $p(n, k) = p(n-1, k-1) + p(n-k, k)$

You need to solve : $p(n, 1) + p(n, 2) + ... + p(n, n)$

This page has a good explanation of the algorithm and also shows a table of the calculations. http://www.mathpages.com/home/kmath091.htm