Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for the expressions for the number of ways in which $n$ indistinguishable balls can be placed into $k$ indistinguishable cells, with

  • No cell being empty
  • Some cells being empty

I knew I've read it (in Applied Combinatorics by Fred Roberts), but unfortunately, I don't happen to have access to it anymore. I would be grateful if someone could help me remember it!

share|improve this question
This is the number of ways to write $n=\sum_{i=1}^k a_k$ where $a_i$ are integers such that $0\leq a_1 \leq a_2... \leq a_k$, with the first bullet changing the rule to $1\leq a_1$. These are related to partition functions, but I don't see anything specific on the wikipedia page for a name for these functions: en.wikipedia.org/wiki/… –  Thomas Andrews Dec 18 '11 at 19:39
If $p_k(n)$ is the number of partitions of $n$ into $k$ parts, the first bullet is $p_k(n)$, and the second is $p_k(n+k)$. Unfortunately, there‚Äôs no nice expression for these. –  Brian M. Scott Dec 18 '11 at 20:59
See also Bell polynomials. –  Mike Spivey Dec 18 '11 at 21:11
If the balls were distinguishable and the cells are not, then what you'd get would be Stirling numbers of the second kind if you require that no cell be empty, and Bell numbers if you allow empty cells and have as many cells as balls. But in your problem they're both (balls and cells) indistinguishable. That means you're counting partitions of an integer. –  Michael Hardy Dec 19 '11 at 1:12
add comment

Your Answer


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

Browse other questions tagged or ask your own question.