How to find the asymptotic behavior ($n \to +\infty$) of the number $q(n, k)$ of partitions of $n$ into addends from $\{1, 2, \dots, k\}$?

I proved that $q(n, k)$ satisfies the recurrent relation $q(n, k) = q(n - k, k) + q(n, k - 1)$ for $n \geq k$. How can I find asymptotic then? Any help would be appreciated.


See this wikipedia article. for all you wanted to know.

Edit I misread the question as restricting both the size and the number of components, but you are only restricting one of them (it does not matter which, you get the same result). The question has a nice discussion (with a discussion of asymptotics) in this paper by Rodney Canfield.

  • $\begingroup$ Thanks, I read this article. There is written that If $A$ is a set of natural numbers which possesses positive natural density $\alpha$ and $p_A(n)$ denote the number of partitions of $n$ into elements of $A$, then $p_A(n) \sim C\sqrt{\alpha n}$ for $C = \pi\sqrt{\dfrac{2}{3}}$. However, in this case the natural density of $\{1, 2, \dots, k\}$ is 0, so it doesn't work, does it? $\endgroup$ – Victor Mar 7 '16 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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