# No of ways in which n indistinguishable items can be placed in m indistinguishable boxes [closed]

This problem is the same as number of ways to partition n into exactly m parts.

The recurrence given in Wikipedia has

p(n,k) = the number of partitions of n using only natural numbers ≥ k

How to find no of partitions of n which has exactly k non-zero parts? Is there a recurrence relation to solve this?

• Here and here are relevant entries in the Online Encyclopedia of Integer Sequences. Recurrence relations included. Aug 4, 2013 at 14:25
• This question has nothing to do with computer science and belongs in math.stackexchange. Aug 4, 2013 at 22:00
• @Yuval: ... where it will be closed as a duplicate. Aug 4, 2013 at 22:50
• @YuvalFilmus Combinatorics are regularly used in algorithm analysis. If we close this one as offtopic, we'd have to close all the asymptotics questions around by the same token. Aug 11, 2013 at 11:53
• These comments should be on Computer Science Meta not here. Aug 12, 2013 at 23:48

The number of partitions of $n$ with exactly $k$ parts is the coefficient of $x^n y^k$ in the generating series $$\prod_{l=1}^\infty \frac{1}{1-x^ly}.$$ Asymptotically, this is probably $\Theta_k(n^{k-1})$ (i.e. the constant depends on $k$).
The number of partitions of $n$ in which each part is at least $k$ is $$\prod_{l=k}^\infty \frac{1}{1-x^l}.$$ Asymptotically, my guess is that it's $\Theta_k(p(n))$, where $p(n)$ is the number of all partitions of $n$.
We can write a recurrence relation for $p(n,k)$: $p(0,k) = 1$ and for $n > 0$, $$p(n,k) = \sum_{t \leq \lfloor n/k \rfloor} p(n-kt,k+1).$$