Is there a closed-form formula for the Partition Function p(n)?

[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?

 

[CRGreathouse]

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

 

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

 

[CRGreathouse]

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

 

[Izzhov]

I go by the Wikipedia definition.

 

[CRGreathouse]

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

 

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

 

[CRGreathouse]

"[A closed-form formula is] a single arithmetic formula obtained to simplify an infinite sum in a general formula." -Wikipedia

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.

 

[Izzhov]

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.

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?

 

[lrs5]

You can find the closed form at http://www.math.sfu.ca/~cbm/aands/page_825.htm.

It's sort of beautiful, in its own grotesque way.

 

[Izzhov]

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

 

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

 

[adriank]

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.

 

[Izzhov]

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

 

[flouran]

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?

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

 

[adriank]

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

 

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

 

[CRGreathouse]

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.

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)

 

[jmal]

"does anyone know if a closed form formula exists for this function?"

Yes; see

http://arxiv.org/abs/1103.1585

eqs.(10), (11) and (12).

 

[adriank]

I don't see how that's closed form, since the number of terms depends on n, and is thus unbounded.

 

[The Chaz]

I go by the Wikipedia definition.

Too bad this guy doesn't come around anymore... I was just starting to like him!

But seriously, forks.

I do NOT know of a closed-form equation.