1
$\begingroup$

How many ways can I arrange $C$ unlabeled bags into $P$ labeled boxes such that each box receives at least $S$ bags (where C > S and C > P)? Assume that I can combine bags to fit a box. I have just learnt that there are $\binom{C-1}{P-1}$ unique ways to keep P balls into C bags. I am unable to get the answer for the above question from this explanation.

For example, if there are 2 Boxes, 3 Bags and each Box should get 1 Bag, then there are two ways: (2,1) and (1,2).

Could you please help me to get this? Thank you. $\quad\quad$

  • 0
    @Willie My confusion is partly stemming from the fact that, to me, both bags and boxes are receptacles. His ordered-tuple notation, however, suggests that he intends the receptacles (which I think he calls boxes) to be labeled and the objects placed in them (which I think he calls bags) to be unlabeled.2011-08-23

2 Answers 2

2

You already know that there are $\binom{C+P-1}{C}$ ways to arrange the $C$ bags into $P$ boxes if you ignore the requirement that each box should contain $S$ bags. (See Stars and Bars for more on that.)

To take the requirement into account, begin by first placing $S$ bags into each of the $P$ boxes, which uses $PS$ of your bags. Now, each box contains at least $S$ bags, so we are free to arrange the remaining $C - PS$ bags as we wish. That is, we wish to arrange $C - PS$ bags in $P$ boxes with no restriction on how many must be in a box (remember, we already met the requirement before we even started counting). By the previous formula, this can be done in $\binom{C - PS + P - 1}{C - PS}$ ways.

  • 0
    @Austin: Thanks. I got it. Let us consider there is only one arrangement is the best one, then is it exponential time-complexity in the worst case for searching that? Please let me know2011-08-23
0

First reduce the number of bags by subtracting the required minimum number in each bag. Using your notation: C' = C-SP. Now, you're freely place the remaining C' items into $P$ boxes. Which is (C'+P-1)!/C'!(P-1)!

Take your example: 4 Boxes, 24 Bags and each Box should get 6 Bags. C'= 24-6*24 = 0, $(0+4-1)!/0!(4-1)!=1$. There is only one way!

In the referenced link they use $S=1$, which makes C'=C-P, so the formula $\binom{C-1}{P-1}$

There is a nice visualization for this, which you don't have to remember the formula. Let's solve the case for 3 identical items to 3 bags (after reducing the required minimum), where items are not distinguishable.

Assume we are placing 2 |'s and 3 x's in 5 slots. Some cases are (do all as an exercise):

|xxx|

x|x|x

xxx||

...

Since there are 5 things (| and x) there are $5!$ ways of distributing them. However, we don't differentiate between individual |'s and individual x's so $2!3!$ will be idential to some other and won't be counted. The total number "unique ways" is $5!/(2!3!) = 10$. The \$1M visualization trick is thinking the |'s as the bag (usually states as box) boundries and the left most and right most bags are one sided. Note that the number of bags is one more than the boundaries. The formula you'll derive is $\binom{\text{bags}+\text{items}-1}{\text{items}}$

  • 0
    The question is updated by Austin. Could you please take a look. Thank you.2011-08-23