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
    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: http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function2011-12-18
  • 0
    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.2011-12-18
  • 0
    See also [Bell polynomials](http://en.wikipedia.org/wiki/Bell_polynomials).2011-12-18
  • 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