Approximating number of partitions of $n$, denoted $p(n)$, by $p(n)\ge e^{c\sqrt n}$

62 Views Asked by At

I was to show that $p(n)$, the number of partition of a positive integer $n$, satisfy: $p(n)\ge \max_{1\le k\le n}{{n-1\choose k-1}\over k!}$, which was obvious because every unordered collection of numbers has at most $k!$ ordered forms\permutations\periods. But I am a little stuck with the required approximation. I showed, prior to that, that ${n\choose k}\le ({en\over k})^k$, and also showed it for $\sum {n\choose k}$. Here I arrive at ${{n-1\choose k-1}\over k!}={1\over n(k-1)!}\cdot {n\choose k}$, but I can't seem to get any further. I have also struggled with showing that $n!=\Theta (\sqrt{n}({n\over e})^n)$ so I don't quite see how to transform it in my favor. I could use a hand here.