prove that there exist a constant $C>0$ such that $p(n) :=$ number of unorders sets of positive integers whose sum is $n \geq e ^ {(c{\sqrt n})}$

Question

$p(n)$ - the number of unordered sets of positive integers whose sum is n.

I proved that $$p(n) \ge {\max_{1\le k\le n}} {\frac {\binom{n-1}{k-1}} {k!} }$$

now i need to deduce that there is an absolute constant c > 0 for which $$p(n) ≥ e ^ {(c{\sqrt n})} $$

would appreciate your help with that.

Answer 1

Your $p(n)$ is the number of partitions of $n$. There is a famous asymptotic formula by Hardy and Ramanujan precising your claim. Maybe you find a simpler proof of your estimate in a combinatorics textbook under the heading "partitions".

Answer 2

In "RAMANUJAN TWELVE LECTURES ON SUBJECTS SUGGESTED BY HIS LIFE AND WORK" by G. H. Hardy, on pages 113-115, there is a reasonably elementary proof that there are real positive $a$ and $b$ such that $e^{a\sqrt{n}} \lt p(n) \lt e^{b\sqrt{n}} $.

The proof is based on Euler's partition generating function $F(x) =\sum_{n=0}^{\infty} p(n)x^n =\dfrac1{\prod_{k=1}^{\infty}(1-x^k)} $.

Using a Tauberian theorem, it is then shown that $\log p(n) \sim c\sqrt{n} $ where $c = \pi\sqrt{\frac23}$.

More precise results follow. First, using Cauchy's theorem in the form $p(n) = \dfrac1{2\pi i} \int_C \dfrac{F(x)}{x^{n+1}}dx $, where $C$ is a contour around the origin, and the functional equation $F(x) =\dfrac{x^{1/24}}{\sqrt{2\pi}}\ln(1/x)\exp(\dfrac{\pi^2}{6\ln(1/x)}F(x_1) $ where $\ln(1/x)\ln(1/x_1) = 1$, it is shown that $p(n) =\dfrac1{2\pi\sqrt{2}}\dfrac{d}{dn}\left(\dfrac{e^{c\sqrt{n\lambda_n}}}{\lambda_n}\right) +O(e^{h\sqrt{n}}) $ where $\lambda_n =\sqrt{n-\frac1{24}} $ and $h < c$. This implies that, and is more precise than, that $p(n) \sim \dfrac1{4n\sqrt{3}}e^{c\sqrt{n}} $.

The remainder of the chapter derives the famous Hardy-Ramanujan asymptotic series for $p(n)$.