6
$\begingroup$

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!

  • 0
    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.2011-12-19

1 Answers 1

2

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)$