Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatoric question

  1. May 20, 2004 #1
    I had been thinking about this one for awhile now but somehow couldn't come up with anything

    Q: Number of ways to select nine 9 marbles from a bag of twelve, where 3 are red, 3 are green, 3 are white, 3 are blue

    This question is in the inclusion & exclusion section(but I can't figure out how it's related to I & E..)

    any suggestion?
  2. jcsd
  3. May 20, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    The way I did it was to figure out the different ways you could have your chosen combinations, e.g. three groups of 3, two groups of 3, one group of 2, and another group of 1. Each "group" has only the same coloured marbles. I found the different types of combinations you could end up with, then figured out how many ways you could assign colours to the groups in the combinations. So, for example, the combination that has three groups of three can be done in 4C3 ways ("four choose three"). If you are going to have three groups of three marbles, each marble in a group being the same colour, and you're starting out with four such groups in the bag, then it's really just like choosing 3 colours out of a set of 4, so 4C3.

    Find the different types of combinations, then find the number of ways you can choose the colours for those combinations, and add them up.
  4. May 20, 2004 #3

    Here is what I came up with

    To get 9 marbles out of 12(4 groups of 3 with diff color), the group arrangement is

    Case 1: 3 3 3 0
    Case 2: 3 3 2 1
    Case 3: 3 2 2 2

    so the answer is Case 1 + Case 2 + Case 3

    for Case 1, it's simply c(4,3) (4 chooses 3)
    for Case 2,
    The color combination is
    since there are 4 elements and 2 of them are the same.

    The marble combination is
    c(3,3)*c(3,3)*c(3,2)*c(3,1) = 9
    so Case 2 = 9 * 4!/2! = 54

    for Case 3,
    The color combination is

    The marble combination is
    c(3,2)*c(3,2)*c(3,2)*c(3,3) = 27
    so Case 3 = 4 * 27 = 108

    The answer is
    4+54+108 = 166

    makes sense?
  5. May 20, 2004 #4
    I have a simpler approach to this (which I hope is valid).

    First, if you select a group of 9 out of 12 marbles & place them on your left, there are 3 marbles on your right. So the number of ways to select the 9 marbles should be the same as the number of ways to select the 3 marbles. That's a much simpler problem, which with these numbers you can simply count. I make it out to be 20.

    As to an analytical solution: when I turn it around this way, the number of marbles I'm selecting is no more than the total number of each color that is available: 3. I want to choose 3 marbles out of 4 possible colors and there are 3 of each color available so there is no restriction on repetition.

    Think of the 4 colors as a row of 4 bins into which I will drop my marbles. There are 3 dividers separating the bins, so using | to represent the dividers and * to represent the marbles, it looks sort of like this:
    | | | ***
    Now the problem is reduced to finding the number of ways to select the positions of the 3 stars out of 6 possible positions. That's just 6C3:
    [tex]\frac{6!}{3!3!} = 20[/tex]

    PS: I have shamelessly stolen this "bins and stars" explanation from Kenneth Rosen's Discrete Mathematics and Its Applications. I hope I am applying it correctly.

  6. May 20, 2004 #5


    User Avatar
    Science Advisor
    Homework Helper

    This is right so far.
    The rest is wrong. This was my approach to case 3: start by choosing the colour that that would correspond to the "3" in "3 2 2 2". There are 4 ways you can do that. Notice that you now have 3 colours to choose from, and want to put them into three same-sized groups, so there's really only one way to choose the rest. So, for Case 3, you should get 4.

    Here's another way of thinking about it. Say you have four colour-buckets. In each bucket, you will put some number of marbles. The number of marbles will either be 3-3-3-0, 3-2-2-2, or 3-3-2-1. For 3-3-3-0, putting those four numbers in four buckets can be done in 4! ways, but since you have 3 similar elements, divide by 3!, giving 4. For the case where you have 3-2-2-2, you get the same thing, 4!/3! = 4. Finally, you have four numbers, but two of them are the same (the two 3's) so 4!/2! gives 12. This method may have been what gnome said, I only glanced at it. Whether you do it this way, the way I originally suggested, or his way, you will get 20.
  7. May 20, 2004 #6

    argg, don't know how came up with the marble combination crap. I would had the right answre if it's left out.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook