4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – Nate Mar 16 '15 at 21:19
  • $\begingroup$ 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. ? $\endgroup$ – Lucian Mar 17 '15 at 2:10
  • $\begingroup$ @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! $\endgroup$ – Siu Ching Pong -Asuka Kenji- Mar 17 '15 at 2:49
  • $\begingroup$ @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). $\endgroup$ – Siu Ching Pong -Asuka Kenji- Mar 17 '15 at 3:00
  • $\begingroup$ Ramanujan gave an exact formula for the partition function using an integral, but I bet that evaluating it is non-trivial. $\endgroup$ – Lucian Mar 17 '15 at 3:06
4
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.