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}$?
Best Answer
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)