1
$\begingroup$

How many ways are there to put $22$ identical balls into $5$ boxes, with each box receiving at least $2$ balls?

The answer is $16$ choose $4$, i.e., $_{16}C_4$, but can someone explain it to me?

$\endgroup$
  • $\begingroup$ isn't it 26 choose 4? $\endgroup$ – Maesumi Dec 16 '13 at 3:55
  • $\begingroup$ Different boxes ? or identitcal boxes ? $\endgroup$ – HK Lee Dec 16 '13 at 3:55
  • $\begingroup$ @HeeKwonLee identical boxes. $\endgroup$ – SSS Dec 16 '13 at 3:57
  • $\begingroup$ It's not identical boxes if the problem is ${}_{16}C_4$. $\endgroup$ – Thomas Andrews Dec 16 '13 at 4:13
2
$\begingroup$

This is a classic stars and bars problem. The solution you have presumes that you must put at least two balls in each box. Is that correct?

$\endgroup$
  • $\begingroup$ Isn't it at least $2$ per box? $\endgroup$ – Thomas Andrews Dec 16 '13 at 4:01
  • $\begingroup$ @ThomasAndrews: looks like it. Fixed. $\endgroup$ – Ross Millikan Dec 16 '13 at 4:02
  • $\begingroup$ If the boxes are identical, the answer is the number of partitions of $22$. $\endgroup$ – Eric Thoma Dec 16 '13 at 4:06
  • $\begingroup$ yes, at least 2 per box, I forgot to mention that. $\endgroup$ – SSS Dec 16 '13 at 4:08
  • $\begingroup$ @SSS fix the question, then. $\endgroup$ – Thomas Andrews Dec 16 '13 at 4:10
1
$\begingroup$

As we have at least two balls in each box, we know where 10 of the balls will be, so the question is equivalent to asking how many ways (up to reordering) we can put 12 balls in 5 boxes. This is the same as asking how many ways we can express 12 as a sum of 5 non-negative integers. There are 45 possible ways of doing this:

  • 12 = 12+0+0+0+0
  • 12 = 11+1+0+0+0
  • 12 = 10+2+0+0+0
  • 12 = 10+1+1+0+0
  • 12 = 9+3+0+0+0
  • 12 = 9+2+1+0+0
  • 12 = 9+1+1+1+0
  • 12 = 8+4+0+0+0
  • 12 = 8+3+1+0+0
  • 12 = 8+2+1+1+0
  • 12 = 8+1+1+1+1
  • 12 = 7+5+0+0+0
  • 12 = 7+4+1+0+0
  • 12 = 7+3+2+0+0
  • 12 = 7+3+1+1+0
  • 12 = 7+2+2+1+0
  • 12 = 7+2+1+1+1
  • 12 = 6+6+0+0+0
  • 12 = 6+5+1+0+0
  • 12 = 6+4+2+0+0
  • 12 = 6+4+1+1+0
  • 12 = 6+3+3+0+0
  • 12 = 6+3+2+1+0
  • 12 = 6+3+1+1+1
  • 12 = 6+2+2+2+0
  • 12 = 6+2+2+1+1
  • 12 = 5+5+2+0+0
  • 12 = 5+5+1+1+0
  • 12 = 5+4+3+0+0
  • 12 = 5+4+2+1+0
  • 12 = 5+4+1+1+1
  • 12 = 5+3+3+1+0
  • 12 = 5+3+2+2+0
  • 12 = 5+3+2+1+1
  • 12 = 5+2+2+2+1
  • 12 = 4+4+4+0+0
  • 12 = 4+4+3+1+0
  • 12 = 4+4+2+2+2
  • 12 = 4+3+3+2+0
  • 12 = 4+3+3+1+1
  • 12 = 4+3+2+2+1
  • 12 = 4+2+2+2+2
  • 12 = 3+3+3+3+0
  • 12 = 3+3+3+2+1
  • 12 = 3+3+2+2+2

So there are 45 possible ways of placing 12 identical balls into 5 identical boxes, and hence 45 possible ways of placing 22 identical balls in 5 boxes such that every box contains at least 2 balls.

$\endgroup$
0
$\begingroup$

To add on another answer, you could do this with generating functions. Since you have five boxes, each must have at least two balls, you can find the answer via $$ [x^{22}]\left( \sum_{i=2}^{22} x^i\right)^5 = \binom{16}{4} = 1820.$$ (Read: get the 22nd coefficient of the following polynomial)

$\endgroup$

Your Answer

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

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