Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$?

share|improve this question
    
For a fixed $k$, the number of partitions of $n$ into $k$ parts grows as a polynomial in $n$, of degree $k-1$. –  Gerry Myerson Aug 9 '11 at 1:35
    
Gerry, does this mean that there is a polynomial p(n) such that (for a specified k) the number of partitions of n into exactly k parts is p(n)? I suspect you mean the latter, which is that there are polynomials p(n) and q(n) which serve as upper and lower bounds (when n is sufficiently large) to the desired function. Some clarity would be appreciated. Gerhard "Ask Me About System Design" Paseman, 2011.08.08 –  Gerhard Paseman Aug 9 '11 at 4:05
    
@Gerhard, I mean the number of partitions is $C_kn^{k-1}+O(n^{k-2})$. See also Igor Rivin's answer. What actually happens is that for each $k$ there's an $m=m(k)$ such that there are $m$ polynomials $P_i(x)$ such that if $n\equiv i\pmod m$ then the number of partitions is $P_i(n)$; each $P_i$ has as its leading term the term given in Igor's answer. –  Gerry Myerson Aug 9 '11 at 5:47
    
Cool! I suspected something like that, but it helps a lot to see your phrasing of it. Thanks, Gerry! Gerhard "Ask Me About System Design" Paseman, 2011.08.09 –  Gerhard Paseman Aug 9 '11 at 17:49
add comment

2 Answers 2

up vote 4 down vote accepted

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)

share|improve this answer
    
Thanks! However, I'm really interested in the case $k = k(n) \to \infty$ as $n \to \infty$. An asymptotic result would be great, but I'd be happy even with something much weaker, like the bound I suggested... –  Rob Aug 9 '11 at 1:57
    
To be even more specific, what can one say for $k \approx n^{1/3}$? –  Rob Aug 9 '11 at 1:59
    
See the edit, and enjoy. –  Igor Rivin Aug 9 '11 at 2:44
    
Great, thanks again! At the top of page 327 they state that $p_k(n)$, the number of partitions of $n$ into $k$ (not necessarily distinct) parts, is asymptotically $$\frac{1}{2\pi n} \left( \frac{e^2 n}{k^2} \right)^k,$$ which answers my question in the affirmative! =) –  Rob Aug 9 '11 at 4:29
1  
One slight problem; as George Andrews points out in the AMS review, the authors make the following (slightly cryptic) comment in the Introduction: ``Finally we note that all our calculations are formal since we have not proved that they are asymptotic...it should be possible to prove that our results are asymptotic also." This seems to imply that the authors have not proved the claimed bounds. Do you know whether this is the case? If not then I'll email the authors and ask... Thanks again! –  Rob Aug 9 '11 at 4:33
add comment

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.

share|improve this answer
    
I like the argument for the lower bound, but I suspect that some restriction on $k$ is needed. For instance, if $k$ is of the order $\sqrt{n}$ then, by the Birthday Paradox, it will be likely that two of the $a_j$ are equal. Then the error introduced by discarding sequences with repeated elements will be appreciable. –  Mark Wildon Aug 10 '11 at 12:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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