Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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:… – 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

According to the comments, it appears that what you're discussing are partitions of an integer.

There isn't a really "nice" way of explicitly computing these, but we have published a blog post that presents a somewhat simple technique using memoization; specifically, Euler's Pentagonal Formula. This was written by Paramanand Singh and may be found here.

If you want an asymptotic approximation, there is the Hardy-Ramanujan formula:

$$p(n) \sim \frac{1}{4n\sqrt 3}\exp\left(2\pi\sqrt{n/6}\right)$$

share|cite|improve this answer

Your Answer


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

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