# Partition Function p(n)

1. Nov 6, 2008

### Izzhov

I am aware that there are several generator functions for the Partition Function p(n), but does anyone know if a closed form formula exists for this function?

2. Nov 7, 2008

### CRGreathouse

http://www.research.att.com/~njas/sequences/A000041 [Broken] has a recursive formula:
$$p(n) = \frac1n\cdot\sum_{k=0}^{n-1}\sigma(n-k)\cdot p(k)$$

Last edited by a moderator: May 3, 2017
3. Nov 7, 2008

### Izzhov

Thanks, but I put the words "closed-form" in italics for a reason.

...unless I'm mistaken on the definition of "closed-form." Which is quite possible.

4. Nov 7, 2008

### CRGreathouse

So tell us what you mean by closed form. (No sigma, no recursion, only +-*/?)

5. Nov 7, 2008

6. Nov 7, 2008

### CRGreathouse

I read the page you linked to, but I didn't see a definition.

7. Nov 7, 2008

### Izzhov

"[A closed-form formula is] a single arithmetic formula obtained to simplify an infinite sum in a general formula." -Wikipedia
Basically, what you said. No infinite sums, recursion, etcetera.

8. Nov 8, 2008

### CRGreathouse

That doesn't tell me what it is at all. Further, I don't see what closed form formulas have to do with infinite sums.

9. Nov 8, 2008

### Izzhov

A closed-form formula is when you take a formula with an infinite sum, such as
$$s = \sum_{k=0}^\infty ar^k$$
and simplify it to an algebraic formula, which in this case would be
$$s = \frac{a}{1 - r}$$
(Assuming, in this case, that r < 1.)
Understand?

10. Dec 21, 2008

### lrs5

11. Dec 21, 2008

### Izzhov

Wait, but that has an infinite sum in it! That doesn't really count. :/

12. Dec 22, 2008

### lrs5

Sure it counts. Just as the closed form for, say, sin(x) = x - x^3/3! + x^5/5! - ...

Perhaps the real question is, what do you want the closed form for? If you want to calculate values exactly, use the recurrence formula. To approximate it, use the asymptotic formula. But I assume you need the closed form for some other reason.

13. Dec 22, 2008

This Wikipedia article on closed-form expressions is probably the one you're looking for, rather than the one Izzhov linked.

I wouldn't consider either of lrs5's examples to be in closed form, because both contain infinite sums.

14. Dec 25, 2008

### Izzhov

So I take it there actually is no closed-form expression then?

15. Jan 7, 2009

### flouran

In other words, you mean that the infinite series can/will converge.

16. Jan 7, 2009

Not just converge, but converge to something that can be expressed with finitely many elementary operations (whatever they may be).

17. Jan 7, 2009

### Kurret

Couldnt we define a closed formula p(n) over a set of functions (for example the elementary functions, or maybe only the functions f(x)=x, f(x)=c) combined with a certain set of operations (for example ^*/-+) as a formula whose number of terms (functions):
1) is not infinite
2) is not depending on n.

18. Jan 7, 2009

### CRGreathouse

I'd prefer to define it symbolically, perhaps with a context-free grammar:

F -> 0
F -> 1
F -> n
F -> -F
F -> F$$^{-1}$$
F -> (F)+(F)
F -> (F)*(F)
F -> (F)^(F)

19. Mar 14, 2011

### jmal

20. Mar 14, 2011