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!
Best Answer
$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.$$