What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T07:42:42Z http://mathoverflow.net/feeds/question/72418 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72418/what-are-the-best-known-bounds-on-the-number-of-partitions-of-n-into-exactly-k What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts? Rob 2011-08-09T01:22:48Z 2011-08-09T17:36:58Z <p>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? </p> <p>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}$?</p> http://mathoverflow.net/questions/72418/what-are-the-best-known-bounds-on-the-number-of-partitions-of-n-into-exactly-k/72421#72421 Answer by Igor Rivin for What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts? Igor Rivin 2011-08-09T01:44:22Z 2011-08-09T02:43:53Z <p>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 <em>asymptotic</em> to:</p> <p>$\dfrac{n^{k-1}}{k[{k-1]!}^2}.$</p> <p>They show a number of other related asymptotic results.</p> <p><strong>EDIT</strong> for $k \ll n,$ they have the asymptotic too painful to typeset, but you can find in <a href="http://dl.dropbox.com/u/5188175/2101859.pdf" rel="nofollow">http://dl.dropbox.com/u/5188175/2101859.pdf</a>, equation (2.27)</p> http://mathoverflow.net/questions/72418/what-are-the-best-known-bounds-on-the-number-of-partitions-of-n-into-exactly-k/72491#72491 Answer by Rob for What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts? Rob 2011-08-09T17:29:42Z 2011-08-09T17:36:58Z <p>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.</p> <p>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.$$</p> <p>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. </p> <p>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. </p>