1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A counting problem (combinatorics)

  1. Sep 5, 2011 #1
    Hi everyone, I want to make sure if I solved this problem correctly. Thanks in advance.

    1. The problem statement, all variables and given/known data

    Rachel invited her friends to dinner. She has 10 friends, but only 6 places to sit them in her (circular) table.

    a) Count the ways to sit the guests if order is not important.
    b) If order is important.
    c) There is a married couple among her friends, and she want them to sit together. Count the ways to sit to sit the guests, if the order of the rest is not important.
    d) If order is important.
    e) Two of her friends are enemies, so she doesn't want them to sit together. Count the ways to sit the guests, if the order of the rest is not important.
    f) If order is important.
    g) Her friends are 4 women and 6 men. She wants to have at least 2 women sitted in the table. Count the ways to sit the guests if order is not important.
    h) Count the ways to sit the guests if there are only men sitted at the table.
    i) Count the ways to sit the guests if she chooses 3 men and 3 women and has them sitted interspersed.


    2. Relevant equations

    Combinations: C(n, k) = n!/(k! * (n-k)!)
    Permutations: P(n, k) = n!/(n-k)!
    Permutations of n objects in a circle: (n - 1)!

    3. The attempt at a solution

    a) C(10, 6) = 210
    b) C(10, 6) * (6 - 1)! = 25200
    c) 2! * C(8, 4) = 140
    d) 2! * C(8, 4) * (5 - 1)! = 3360
    e) 210 - 140 = 70 (a and d)
    f) 25200 - 3360 = 21840 (b and d)
    g) C(8, 4) = 70
    h) C(6, 6) * (6 - 1)! = 120
    i) 3! * C(6, 3) * 3! * C(4, 3) = 2880
     
  2. jcsd
  3. Sep 5, 2011 #2

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    For the questions involving the married couple and the enemies, are you supposed to assume that those pairs are always seated, or should you take into account the possibility that they're not among the six seated at the table?
     
  4. Sep 5, 2011 #3
    They are always sitted.
     
  5. Sep 6, 2011 #4

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    a-d look fine.

    e and f aren't correct. I get 210 for e and 5040 for f. I think I understand what you tried, but it doesn't work.

    g isn't correct. I get 185.

    h is correct.

    i isn't correct. I get 960.
     
  6. Sep 6, 2011 #5
    First of all, thanks for your help!

    So after giving it some more thought, I finally got to see my mistakes and how to fix them. However, I still cannot solve the e).

    My new answers:
    e) I still do not get this one.
    f) Total ways of seating everyone: C(8, 4) * (6 - 1)! = 8400. Total ways of having the enemies seated together: 2! * C(8,4) * (5 - 1)! = 3360. So we get a total of 5040 ways of the enemies not sitting together.
    g) It a case analysis. 1st case: 2 women, 4 men. 2nd: 3 women, 3 men. 3rd: 4 women, 3 men. Using the Addition Principle we have a total of C(4,2) * C(6,4) + C(4,3) * C(6,3) + C(4,4) * C(6,2) = 185 ways.
    i) There are C(4,3) ways to choose the women, and (3 - 1)! ways to sit them. Having seated the women, we can sit the men in 3! ways. So the total ways are C(4, 3) * (3 - 1)! * C(6,3) * 3! = 960 using the Mulitiplication Principle.​
     
  7. Sep 6, 2011 #6

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    For e, think about how many ways are there are to seat the two enemies.
     
  8. Sep 6, 2011 #7

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You can also get the answer to e by dividing the answer to f by 4! because you don't care how the other 4 guests are seated.
     
  9. Sep 6, 2011 #8
    Ok, using what you said in post #7 I can see where the answer comes from. However I still don't understand how to solve it as you suggest in post #6. My guess is that one can sit the enemies in 2! different ways. Can you please explain me how you did it?
     
  10. Sep 6, 2011 #9

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    If you have two people, you can seat them 5 different ways around the table, right? If they're enemies, you have to exclude the possibilities where they sit next to each other. That's the 2!. So how many are possibilities are left?
     
  11. Sep 6, 2011 #10
    Ok, so there would be 5 - 2 = 3 ways to sit them around, and that gives us 3 * C(8, 4) = 210.
    Thanks!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A counting problem (combinatorics)
  1. Combinatorics problem (Replies: 3)

  2. Combinatorics Problem (Replies: 3)

  3. Combinatorics problem (Replies: 2)

Loading...