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
    Are the boxes distinguishable? Are the bags distinguishable?2011-08-23
  • 0
    Boxes are not distinguishable. However, bags are distinguishable as each bag contains arbitraty number of balls.2011-08-23
  • 0
    I mean when are the bags distinguishable when they are *empty*? For example, if I have 1 box and 2 bags, is the arrangement where I put the box into the first bag different from where I put box into the second bag?2011-08-23
  • 0
    I apologize for the confusion. I have just updated the question. Could you please take a look at the question now.2011-08-23
  • 0
    @kkp: As with the previous problem: first put in $S$ bags into each of the $C$ boxes. That leaves $C-PS$ bags to be distributed. Then apply the stars-and-bars formula to the problem of distributing $C-PS$ bags into $P$ boxes.2011-08-23
  • 0
    Now you have balls, bags, and boxes. I apologize for being dense, but I no longer know what is being asked.2011-08-23
  • 0
    @Austin: I am trying to convert my complex problem into a simple one using balls and bags. I am sorry if the question is not clear.2011-08-23
  • 0
    @kkp The example helps, but still does not answer my original question. Suppose you have 2 boxes, 1 bag, and each box should have at least 0 bags. Do you consider the arrangement (1,0) to be different from the arrangement (0,1)?2011-08-23
  • 0
    @Austin: Please assume that there are always more bags than boxes.2011-08-23
  • 1
    @kkp Suppose you have 2 boxes, 3 bags, and each box should have a least 1 bag. Do you consider the arrangement (2,1) to be different from the arrangement (1,2)?2011-08-23
  • 0
    @Austin: Yes, I consider (1,2) and (2,1) as different arrangements.2011-08-23
  • 0
    @Austin Mohr and kkp: I partially approved the edit by Austin, but there were some disagreements of the edit with the comments posted above (which I tried to reconcile). Please look it over to see if the meaning is correct.2011-08-23
  • 0
    @Austin: the labeled/unlabelled is precisely where I am confused by about your edit. In the second comment in this thread kkp specified that boxes are not distinguishable, while bags are, in directly contradiction to your most recent edit.2011-08-23
  • 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
    Let us consider 24 bags, 3 boxes and say each box should get atleast 6 bags. Then according to the formula there are $\binom{24-18-1}{3-1}$ ways. However, it seems that there are more than 10 ways: (6,6,12) (6,12,6)(6,7,11)(6,11,7)(6,8,10)(6,10,8)(6,9,9)(12,6,6)(11,7,6)(7,11,6)(10,8,6)(8,10,6)(9,9,6)(6,6,6)2011-08-23
  • 0
    Alternatively, assign $S-1$ bags into each of the boxes (which uses up $P(S-1)$ bags), and use theorem 1.2011-08-23
  • 0
    @Byron Thank you for the correction.2011-08-23
  • 0
    @Austin Your idea is correct, but you should use theorem 2 of stars and bars, not theorem 1. When you arrange the remaining $C-PS$ bags, you allow the value *zero*.2011-08-23
  • 0
    @kkp Not all of your examples use all 24 bags. If you want to use *at most* $C$ bags, then you can use the formula I gave for *exactly$ $C$ bags and sum. For example, 2 boxes, 3 bags, and at least 1 in each box: you would add the case where you use exactly 2 bags to the case where you use exactly 3 bags.2011-08-23
  • 0
    @Austin: From the updated question, the following 13 arrangements are fine if there are 24 bags, 3 boxes and say each box should get atleast 6 bags: (6,6,12) (6,12,6)(6,7,11)(6,11,7)(6,8,10)(6,10,8)(6,9,9)(12,6,6)(11,7,6)(7,11,6)(10,8,6)(‌​8,10,6)(9,9,6).. right? As we can see 24 bags in every arrangement. Am I wrong? Please explain.2011-08-23
  • 0
    By the formula, there are $\binom{24 - 3 \cdot 6 + 3 - 1}{24 - 3 \cdot 6} = \binom{8}{6} = 28$ arrangements, so your list does not show there are too many. I think you are comparing with my old (incorrect) answer that gave 10 such arrangements.2011-08-23
  • 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