3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Jordan Payette Jan 6 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.