Suppose that $p(n)$ is the number of partitions of a natural number $n$. Prove that there exists $c>0$ such that $P(n)\ge n^{c \cdot \log n}$. proposed by Mohammad Mansouri
Problem
Source: Iran 3rd round 2011-combinatorics exam-p3
Tags: logarithms, combinatorics proposed, combinatorics
06.09.2011 18:48
The number of partitions of integer $n$ with the largest element $k$ ($k \geq \frac{n}{2}$) is at least $p(n-k)$ Therefore $p(n) \geq p(1)+ ...+p(\frac{n}{2}) \geq \frac{n}{4} p(\frac{n}{4})$ Thus $p(n) \geq \frac{n}{4} p(\frac{n}{4})$ which beats the inequality.
06.09.2011 19:05
Also there is another approach with $P(n) \geq 2^{\sqrt{n}}$ .
06.09.2011 22:47
Can you give your solution about it? any preliminary solution? The asymptotic behavior of $p(n)$ is the same as you mentioned and has sub-exponential growth.
07.09.2011 18:53
Even better: Put $t$ large enough that $\frac{t(t+1)}{2} \leq \frac{n}{2}$ Now for every subset of $\{1,2,....,t\}$ such as $\{x_1,...,x_u\}$ we can write $n$ as $n=x_1+...+x_u+(n-x_1-...-x_u)$, therefor we have atleast $2^t$ partitions which is nearly $2^{\sqrt {n}}$
19.02.2016 19:20
I'll just add in that from this link, we have $\log p(n) \sim C\sqrt{n}$ for $C=\pi \sqrt{\frac{2}{3}}$.