Integer Partitions asymptotic behaviour 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.
 A: 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.
A: 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$.
A: 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)}
$.
