# Putting items in bags

• Feb 11th 2013, 09:35 AM
battery88
Putting items in bags
Suppose there are 20 items and 12 bags. How many ways can the items be put into the bags if the items are distinct.

Could someone offer me a little direction on this problem. Thanks
• Feb 11th 2013, 10:30 AM
MathJack
Re: Putting items in bags
have a look at permutations, it is really straightforward, take a look and have an attempt I will show you the answer then
• Feb 11th 2013, 10:44 AM
Plato
Re: Putting items in bags
Quote:

Originally Posted by battery88
Suppose there are 20 items and 12 bags. How many ways can the items be put into the bags if the items are distinct.
I think the answer is C(20, 12), assuming the bags are also distinct.
Could someone offer me a little direction on this.

First, why do you assume that the bags are distinct? That is not part of the statement.

If the items are distinct and the bags are distinct, then that is simply counting the number of functions from a set of twenty to a set of twelve:
$\displaystyle 12^{20}$.
But that answer means some bags may be empty.

If you require no empty bags, then that is simply counting the number of surjections from a set of twenty to a set of twelve:
$\displaystyle \sum\limits_{k = 0}^{12} {\left( { - 1} \right)^k \binom{ 12}{k} (12 - k)^{20} }$.

BUT, I don't think it means that the bags are distinct.
• Feb 11th 2013, 10:51 AM
battery88
Re: Putting items in bags
Okay, the 1st item can be placed 12 ways,
the 2nd item can be placed 12 ways,
the 3rd item can be placed 12 ways,
and so forth, until we have 12^20 ways.
• Feb 11th 2013, 10:56 AM
battery88
Re: Putting items in bags
Quote:

Originally Posted by Plato
First, why do you assume that the bags are distinct? That is not part of the statement.

If the items are distinct and the bags are distinct, then that is simply counting the number of functions from a set of twenty to a set of twelve:
$\displaystyle 12^{20}$.
But that answer means some bags may be empty.

If you require no empty bags, then that is simply counting the number of surjections from a set of twenty to a set of twelve:
$\displaystyle \sum\limits_{k = 0}^{12} {\left( { - 1} \right)^k \binom{ 12}{k} (12 - k)^{20} }$.

BUT, I don't think it means that the bags are distinct.

I was thinking of something else: placing distinguished items in distinguished boxes.
• Feb 11th 2013, 10:58 AM
battery88
Re: Putting items in bags
So, if the items were identical would the number of ways to place the items in the bags = 12^1 = 12?
• Feb 11th 2013, 11:10 AM
battery88
Re: Putting items in bags
I'm pretty sure my previous post was incorrect, so how would I solve this problem if the items are identical. In other words:

Suppose there are 20 items and 12 bags. How many ways can the items be put into the bags if the items are identical?

Would this be a problem of placing indistinguishable items into distinguishable boxes?
• Feb 11th 2013, 12:08 PM
battery88
Re: Putting items in bags
I used this theorem from my book regarding "Indistinguishable objects and distinguishable boxes": C(n + r - 1, r).
We have 20 indistinguishable books going in 12 distinguishable bags. Let n = 12 and r = 20. We have C(12 + 20 - 1, 20) = C(31, 20) different ways place the items.

I'm not sure if this is correct or not. Suggestions?
• Feb 11th 2013, 12:19 PM
Plato
Re: Putting items in bags
Quote:

Originally Posted by battery88
I used this theorem from my book regarding "Indistinguishable objects and distinguishable boxes": C(n + r - 1, r).
We have 20 indistinguishable books going in 12 distinguishable bags. Let n = 12 and r = 20. We have C(12 + 20 - 1, 20) = C(31, 20) different ways place the items.

You have read the textbook incorrectly.
"N indistinguishable objects and K distinguishable boxes"
$\displaystyle \binom{N+K-1}{N}=\binom{N+K-1}{K-1}$.

So 20 indistinguishable books going in 12 distinguishable bags gives
$\displaystyle \binom{20+12-1}{20}$
• Feb 11th 2013, 12:31 PM
battery88
Re: Putting items in bags
Okay, thanks for the correction.
• Feb 11th 2013, 12:45 PM
battery88
Re: Putting items in bags
Now, one more question going back to Plato's post 3:

Suppose there are 20 items and 12 bags. How many ways can the items be put into the bags if the items are identical and no bag can be left empty?
• Feb 11th 2013, 12:59 PM
Plato
Re: Putting items in bags
Quote:

Originally Posted by battery88
Suppose there are 20 items and 12 bags. How many ways can the items be put into the bags if the items are identical and no bag can be left empty?

You may find this webpage useful.

If the 20 items are identical but the bags are distinct go ahead and put one item in each bag. Now none is empty. There are eight items left, so:
$\displaystyle \binom{8+12-1}{8}$.
• Feb 11th 2013, 01:07 PM
battery88
Re: Putting items in bags
Thanks for the link and the help. It seems so simple now. Just wish I could do it without help.