# Combinatorial Proof that $p(n)/(1+\epsilon)^n \to 0$

I was thinking this morning about the identity $$\prod_{n=1}^{\infty} \left( \frac{1}{1-q^n} \right) = \sum_{n=0}^{\infty} p(n) q^n$$. The product on the left converges for $$|q|<1$$, which implies the convergence of the series for $$|q|<1$$. Given $$\epsilon >0$$, let $$q = \frac{1}{1+\epsilon} <1$$. Then, the series must converge at $$q$$, implying that the $$n^{th}$$ term converges to $$0$$, which tells us that $$\frac{p(n)}{(1+e)^n} \to 0$$ as $$n \to \infty$$.

I want a combinatorial proof that this is true. Note this means that something that relies on this generating function proof (i.e. using the asymptotic formula for $$p(n)$$) is not allowed.

Probability sort of counts as combinatorics. Let $$r > 1$$, and consider the experiment where we generate a multiset by choosing $$K_i$$ copies of $$i$$ independently for each $$i \ge 1$$, where $$K_i$$ is the geometric distribution with parameter $$1 - r^{-i}$$ (that is, $$\Pr[K_i = k] = r^{-ik}(1 - r^{-i})$$).

Any particular partition of $$n$$, say with $$k_i$$ copies of $$i$$ for each $$i$$, is generated by the experiment with probability

$$\prod_{i = 1}^\infty r^{-ik_i}(1 - r^{-i}) = r^{-n} \prod_{i = 1}^\infty (1 - r^{-i}),$$

which is the same for each partition of $$n$$, so it can’t be more than $$\frac{1}{p(n)}$$. Thus

\begin{align*} p(n) &\le r^n \prod_{i = 1}^\infty \frac{1}{1 - r^{-i}} \\ &= r^n \exp \sum_{i=1}^\infty -\ln (1 - r^{-i}) \\ &= r^n \exp \sum_{i=1}^\infty \sum_{k=1}^\infty \frac{r^{-ik}}{k} \\ &= r^n \exp \sum_{k=1}^\infty \frac{1}{k(r^k - 1)} \\ &< r^n \exp \sum_{k=1}^\infty \frac{1}{k^2(r - 1)} \\ &= r^n \exp \frac{\pi^2}{6(r - 1)}. \\ \end{align*}

We already get the desired result from $$p(n) = O(r^n)$$ for all $$r > 1$$. The tightest bound we can prove this way is at $$r = 1 + \frac{\pi}{\sqrt{6n}}$$, where

$$\ln p(n) < n \ln r + \frac{\pi^2}{6(r - 1)} < n(r - 1) + \frac{\pi^2}{6(r - 1)} = \pi\sqrt{\frac23 n}, \\ p(n) < \exp\left(\pi\sqrt{\frac23 n}\right),$$

nearly matching the known asymptotic formula $$p(n) \sim \frac{1}{4n\sqrt 3} \exp\left(\pi\sqrt{\frac23 n}\right)$$.

• First, thanks for having pointed out the mistakes in my answer; I was coming back to delete it as I realized overnight how erroneous it was! Secondly, nice proof! – Jordan Payette Jan 6 at 14:39