1
$\begingroup$

Usually, when counting the number of ways in which $n$ balls can be put into $k$ boxes, two cases are considered:

  1. Boxes cannot be empty
  2. Boxes can be empty

Respectively, each of the listed cases has a formula:

$$C_1={n-1\choose k-1}$$ $$C_2={n+k-1\choose n}$$

This however doesn't suffice my needs. I want the boxes to be all not empty, and be countable, just like in the first case... But I want the boxes to be indistinguishable.

That is, as long as you have 4 balls in box 1, 2 balls in box 2, and 1 ball in box 3, it doesn't matter how the boxes themselves are configured or labeled.

For example, if there are 7 balls and 3 boxes, there would be four such ways to arrange them:

  1. O|O|OOOOO
  2. O|OO|OOOO
  3. O|OOO|OOO
  4. OO|OO|OOO

I have no ideas how to construct a formula for this

$\endgroup$
  • 3
    $\begingroup$ What you are looking for is the number of partitions of $n$ into $k$ parts: whitman.edu/mathematics/cgt_online/book/section03.03.html. This is complicated to solve. I don't believe there is a nice formula for it, but there is a recurrence relation $p_k(n)=p_k(n-k)+p_{k-1}(n-1)$. $\endgroup$ – kccu Jan 26 at 4:22
  • $\begingroup$ @kccu I didn't recognize this as partitions, wow. But, didn't Ramanujan find an infinite series that converges to the solution of specific partitions? As far as I can remember, that series was very crazy and messy $\endgroup$ – KKZiomek Jan 26 at 4:28
  • $\begingroup$ I'm not familiar with that, but I wouldn't be surprised if Ramanujan had some sort of result about partitions. $\endgroup$ – kccu Jan 26 at 4:29
  • $\begingroup$ The generating function for partitions into $k$ parts goes back to Euler. Ramanujan did discover a considerable number of theorems about partitions and partition generating functions. $\endgroup$ – Peter Taylor Jan 28 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.