8
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ For a fixed $k$, the number of partitions of $n$ into $k$ parts grows as a polynomial in $n$, of degree $k-1$. $\endgroup$
    – Gerry Myerson
    Commented Aug 9, 2011 at 1:35
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 9, 2011 at 4:05
  • 1
    $\begingroup$ @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. $\endgroup$
    – Gerry Myerson
    Commented Aug 9, 2011 at 5:47
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 9, 2011 at 17:49

2 Answers 2

Reset to default
6
$\begingroup$

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)

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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... $\endgroup$
    – Rob
    Commented Aug 9, 2011 at 1:57
  • $\begingroup$ To be even more specific, what can one say for $k \approx n^{1/3}$? $\endgroup$
    – Rob
    Commented Aug 9, 2011 at 1:59
  • $\begingroup$ See the edit, and enjoy. $\endgroup$
    – Igor Rivin
    Commented Aug 9, 2011 at 2:44
  • 1
    $\begingroup$ 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! =) $\endgroup$
    – Rob
    Commented Aug 9, 2011 at 4:29
  • 1
    $\begingroup$ 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! $\endgroup$
    – Rob
    Commented Aug 9, 2011 at 4:33
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Mark Wildon
    Commented Aug 10, 2011 at 12:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .