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

1 Answer 1

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 plan to have a blog post published relatively soon that presents a somewhat simple technique using memoization; specifically, Euler's Pentagonal Formula. A "pre-print" of the blog post can be found here. (I will update this link when the entry is published.)

share|improve this answer

Your Answer

 
discard

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.