What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts? - MathOverflow

What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?

2011-08-09T01:22:48Z

For example, if $n = 10$ and $k = 3$, then the legal partitions are $$10 = 7 + 2 + 1 = 6 + 3 + 1 = 5 + 4 + 1 = 5 + 3 + 2$$ so the answer is $4$. By choosing $k$ random elements of ${1,\ldots,2n/k}$, one can easily construct about $(n/k^2)^k$ such partitions. For $k \approx \sqrt{n}$ this is not far from best possible, since the total number of partitions is (by Hardy and Ramanujan's famous theorem) asymptotically $$\frac{1}{4 \sqrt{3} n} \exp\left( \pi \sqrt{ \frac{2n}{3} } \right).$$ Can one do much better than $(n/k^2)^k$ for smaller k?

To be precise, writing $p^*_k(n)$ for the number of such partitions, is it true that, for some constant $C$, $$p^*_k(n) \leqslant \left( \frac{Cn}{k^2} \right)^k$$ for every $n,k \in \mathbb{N}$?

Answer by Igor Rivin for What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?

2011-08-09T01:44:22Z

In the 1990 paper by Charles Knessl and Joseph Keller, the authors prove the asymptotic result (for $n>>1, k=O(1)$, your number is asymptotic to:

$\dfrac{n^{k-1}}{k[{k-1]!}^2}.$

They show a number of other related asymptotic results.

EDIT for $k \ll n,$ they have the asymptotic too painful to typeset, but you can find in http://dl.dropbox.com/u/5188175/2101859.pdf, equation (2.27)

Answer by Rob for What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?

2011-08-09T17:29:42Z

On further reflection, there seems to be a very simple (and nice) solution to my question. I'll sketch a proof of the following theorem.

Theorem: There is a constant $C$ such that $$\frac{1}{Cnk} \left( \frac{e^2 n}{k^2} \right)^k \leqslant p_k^*(n) \leqslant \frac{C}{nk} \left( \frac{e^2 n}{k^2} \right)^k.$$

The upper bound follows from the recursion $$p_k^*(n) \leqslant \frac{1}{k} \sum_{a=1}^n p^*_{k-1} (n-a)$$ by a simple induction argument. To see the recursion, simply note that since the elements of the partition are distinct, we count each one exactly $k$ times.

For the lower bound, we use the probabilistic method. Motivated by the calculation above, let's choose a random sequence $A = (a_1,\ldots,a_k)$ by selecting each $a_j$ independently according to the distribution $$\mathbb{P}(a_j = a) \approx \frac{(k-1)(n-a)^{k-2}}{n^{k-1}}.$$ Discard the (few) sequences with repeated elements, and note that the expected value of $\sum a_j$ is $n$. We claim that the probability that $\sum a_j = n$ is roughly $1/(n \sqrt{k})$, and that each such sequence appears with probability at most $$\left( \frac{k-1}{en} \right)^k.$$ It follows that there are at least $$\frac{1}{Cn \sqrt{k}} \left( \frac{en}{k-1} \right)^k$$ such sequences. Dividing by $k!$ gives the desired bound on the number of sets.