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

Problems with the Multiplication Principle (combinatorics)

  1. Feb 17, 2009 #1
    I'm having problems wrapping my head around this...so I want to post some questions out of this Introductory Combinatorics book and what I believe to be the solutions:

    1.) There are 6 rooks placed on a 6 by 6 chessboard. How many ways if there are 2 red and 4 blue?

    I got 6!*\binom{6}{4} as there are 6! places to put it and 6 choose 4 ways to pain the rooks blue.

    2.) A classroom has 2 rows of 8 seats. There are 14 students, 5 of whom always sit in the front row and 4 whom always sit in the back.

    Does this work out in roughly the same way?

    \binom{9}{3}*3!+\binom{5}{4}*4!

    there are 9 people left who won't sit up front, therefore leaving 3 spots to choose for the nine. In the back there will be 14-5 (that sit up front)-4(the ones who will always be in back). So there will be 5 choose 4*4!
     
  2. jcsd
  3. Feb 17, 2009 #2

    MathematicalPhysicist

    User Avatar
    Gold Member

    1. Is the question asks how many ways are there to paint the 6 rooks and then place them in the board?
    Then the answer would be for the colours as you wrote \binom{6}{4} but for placing the rooks you have \binom{36}{6}.

    2. What is the question? is it how many ways there are to sit the students?
    You have \binom{8}{5}*5! to choose for the upfront seats and \binom{8}{4}*4! for the backseated, and the rest who are 5 students need to be seated either upfront or back, there 7 places for 5 students i.e \binom{7}{5} and either the first is all seated which means two seats are left unmanned in the backseat or the backseat is all seated which means that two seats are left unmanned in the upfront seat.
    which roughly means: \binom{8}{5}5!*(\binom{5}{3}3!*\binom{4}{2}+\binom{5}{4}4!*3)*\binom{8}{4}4!
     
  4. Feb 17, 2009 #3
    What about #ways_for_red * #ways_for_blue ?


    What is the question?
    :smile:
     
  5. Feb 17, 2009 #4
    How many ways are there to sit the student?

    That's the question.
     
  6. Feb 17, 2009 #5
    I don't understand why its \binom{8}{5} and not \binom{9}{3}. Since 5 are guaranteed to sit in front, wouldn't that leave me 3 to choose from the 9.
     
  7. Feb 17, 2009 #6
    First put the red ones down. For the first red, you have 36 ways. For the second rook, you have 35 ways. Multiplying these gives 36*35.

    However, you've double counted, since it doesn't matter which rook you put down first, and you've counted both ways of ordering them. So divide by 2.

    Next, put the blue ones down. You have 34, 33, 32, and 31 ways to do this, respectively. Multiplying gives 34*33*32*31.

    You've overcounted again. There are 4*3*2*1 ways to number the four blue rooks, so you just need to divide by 4*3*2*1 to get the number of ways to put the blue ones down.

    Now just multiply the answer from part 1 to the answer from part 2. In other words, the answer is:

    P(36,6) / 2!4!
     
  8. Feb 17, 2009 #7
    To place the two red you have to select a subset of two elements in a set of 36.
    So you have a number of choices equal to the combinations of 36 on 2 that is
    36*35/2 = 18*35 choices.
    Then you have to place the four blue and you have a number of choices equal to the
    number of the subsets of four elements in a set of 34 elements that is
    34*33*32*31/(4*3*2)= 17*16*11*31/2 = 17*8*11*31 choices.
    So the final number is the multiplication of these two
    8*11*16*17*31*35
    it is a large number indeed so better you don't multiply them
    it is
    (2^7)*5*7*11*17*31
    factorized in primes.
     
  9. Feb 17, 2009 #8
    A classroom has 2 rows of 8 seats. There are 14 students, 5 of whom always sit in the front row and 4 whom always sit in the back.

    In the first row there are always 5 students that will seat.
    In how many ways they can sit???
    It is the number of injective functions from a set of 5 elements in a set of 8 elements.
    you have 8 choices for the first student, 7 choices for the second student 6 for the 3rd, 5 for the 4th and 4 for the 5th. In total A = 8*7*6*5*4.

    For the back row you have the same logic. You have B = 8*7*6*5 choices.
    Now how many seats are still free? 8*2 - (5+4) = 16 - 9 = 7 and how many students are left? 14 - (5+4) = 5.
    So you have C = 7*6*5*4*3 choices.

    The total choices is

    D = A*B*C

    I hope I didn't do any mistake..... these exercises are often tricky for me...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Problems with the Multiplication Principle (combinatorics)
  1. Combinatorical Problem (Replies: 1)

  2. Combinatorics problem (Replies: 14)

  3. Combinatorics problem (Replies: 2)

Loading...