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.

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$

share|improve this question
    
Are the boxes distinguishable? Are the bags distinguishable? –  Austin Mohr Aug 23 '11 at 16:20
    
Boxes are not distinguishable. However, bags are distinguishable as each bag contains arbitraty number of balls. –  samarasa Aug 23 '11 at 16:51
    
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? –  Austin Mohr Aug 23 '11 at 17:09
    
I apologize for the confusion. I have just updated the question. Could you please take a look at the question now. –  samarasa Aug 23 '11 at 17:16
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)? –  Austin Mohr Aug 23 '11 at 18:08

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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) –  samarasa Aug 23 '11 at 18:44
    
Alternatively, assign $S-1$ bags into each of the boxes (which uses up $P(S-1)$ bags), and use theorem 1. –  Arturo Magidin Aug 23 '11 at 18:57
    
@Byron Thank you for the correction. –  Austin Mohr Aug 23 '11 at 18:59
    
@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. –  Byron Schmuland Aug 23 '11 at 19:02
    
@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. –  Austin Mohr Aug 23 '11 at 20:00

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}}$$

share|improve this answer
    
The question is updated by Austin. Could you please take a look. Thank you. –  samarasa Aug 23 '11 at 20:39

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.