Integer Partitions asymptotic behaviour

Question

Let $ P(n) $ be the number of partitions of number $n$.

Prove that $ P(n)$, grows faster than any polynomial from $n$.

I am looking for an elementary (rather bijective) proof of the fact.

Answer 1

The number of ordered partitions of $n$ into exactly $k$ parts is, by the usual combinatorial "stars and bars" argument, $\binom{n-1}{k-1}$: imagine placing $n$ objects in a row and adding $k-1$ dividers in the $n-1$ spaces between them.

As a result, a lower bound for the number of unordered partitions of $n$ into $k$ parts is $\frac1{k!} \binom{n-1}{k-1}$, which is $\Omega(n^{k-1})$. This is also, of course, a lower bound for $P(n)$.

The argument works for any $k$, proving that $P(n)$ grows faster than a polynomial of any degree.

Answer 2

If $P(n,k)$ is the number of partitions of $n$ into at most $k$ parts, then $$\sum_{n=0}^\infty P(n,k)t^n=\frac1{(1-t)(1-t^2)\cdots(1-t^k)}.$$ (If $P(n,k)$ is the number of partitions of $n$ into at exactly $k$ parts, then the generating function is $t^k$ times this.)

This has a partial fraction expansion as a linear combination of terms of the form $1/(1-\zeta t)^m$ where $\zeta$ is a root of unity and $m$ is a positive integer. The dominant contribution to the generating function will come from the term involving $1/(1-t)^k$.

Answer 3

Look at https://en.wikipedia.org/wiki/Partition_(number_theory)#Partition_function

An asymptotic formula for $p(n)$, the number of partitions of $n$, is $p(n) \approx \dfrac1{4n\sqrt{3}}\exp\left(\pi\sqrt{\dfrac{2n}{3}}\right) $.

An elementary proof of this by Erdos is at Erdős, Pál (1942). "On an elementary proof of some asymptotic formulas in the theory of partitions". Ann. Math. (2). 43: 437–450. Zbl 0061.07905. doi:10.2307/1968802.

This implies $\ln p(n) \approx C\sqrt{n} $ where $C = \pi\sqrt{\dfrac{2}{3}} $. All that is needed for your result is that $\ln p(n) \gt k\ln(n) $ for any $k > 0$.

In G. H. Hardy's book "RAMANUJAN TWELVE LECTURES ON SUBJECTS SUGGESTED BY HIS LIFE AND WORK", chapter 8 has an elementary proof that $e^{A\sqrt{n}} \le p(n) \lt e^{B\sqrt{n}} $ for some reals $A$ and $B$. This is based on the generating function $\sum_{n=1}^{\infty} p(n)x^n =\dfrac1{\prod_{m=1}^{\infty}(1-x^m)} $.