A counting problem (combinatorics)

  • Thread starter ravenea
  • Start date
  • #1
10
0
Hi everyone, I want to make sure if I solved this problem correctly. Thanks in advance.

Homework Statement



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.


Homework 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)!

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
 

Answers and Replies

  • #2
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,790
1,377
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?
 
  • #3
10
0
They are always sitted.
 
  • #4
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,790
1,377
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.
 
  • #5
10
0
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.​
 
  • #6
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,790
1,377
For e, think about how many ways are there are to seat the two enemies.
 
  • #7
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,790
1,377
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.
 
  • #8
10
0
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?
 
  • #9
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,790
1,377
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?
 
  • #10
10
0
Ok, so there would be 5 - 2 = 3 ways to sit them around, and that gives us 3 * C(8, 4) = 210.
Thanks!
 

Related Threads on A counting problem (combinatorics)

  • Last Post
Replies
12
Views
858
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
4
Views
978
  • Last Post
Replies
2
Views
946
Top