1

Suppose you have 4 different types of marbles to choose from. How man unique bags can you create with 10 marbles per bag such that each bag has at least one of each type of marbles.

My approach: 'Stars and Bars' method:

**********|||

Therefore, $${13 \choose 3} = {13 \choose 10} =$$ $${13!\over 10!(3!)} = {13!\over 3!(10!)} = 286$$ different bags

However this isn't the correct answer, the answer should be $84$, but I have no idea how to get that.

Sc4r
  • 639
  • The problem with the stars and bars method is that, for example, your $********|||$ is included in the 286 combinations, yet this is not represented in the problem since you have to have at least one of each color. So as another example, $**|||**$ is a valid combination, but only two colors are represented in this combination where you need 4 partitions always. – Eleven-Eleven Dec 11 '13 at 19:22

1 Answers1

5

Hold on, let's look a little more carefully at the problem. It's asking how many different bags of $10$ marbles we can create, given that each bag must contain at least one of each marble. So we already know that we can put one of each marble into every bag, because we have to. Therefore, the problem reduces to:

How many different bags of $10-4=6$ marbles can we create, if we have $4$ different types of marbles to choose from?

Now we can use stars and bars: $$\binom{6+4-1}{4-1}=\binom{9}{3}=84$$ as desired.

ant11
  • 2,033
  • 15
  • 38