3

I have the following exercise. Please help me to solve it.

Exercise. In how many ways can 3 men and 3 women be seated at a round table if

(a) no restriction is imposed

(b) 2 particular women must not sit together

(c) each woman is to be between 2 men.

Ideas

(a) simple case, it's just $5!$, I am still hardly getting the idea of round table and the first man taking any place. We don't count him because the table is round is it correct? So the table doesn't have the beginning and end, so we can start comparing permutation from any of the guests, therefore we don't count the first man, I still don't have good understanding why it happens.

(b) I've never saw the template for "must not sit together", usually when the is a group that must sit together we take them as one guest and on addition count the permutation within the group, but here I don't know to reason about the solution.

(c) extremely hard, I even don't have ideas.

I would appreciate for any help.

user16168
  • 697
  • 1
    (a) is simple, yes. (b) is easier if you look at how many "bad" arrangements there are (you're well on your way to calculate those in your reasoning, by the way), and subtract those from the total. In (c), note that also every man needs to be between two women, otherwise there aren't enough men to fulfill the requirement. So man and woman in every other seat. Hope that helps. – Arthur Sep 10 '13 at 08:37

1 Answers1

4

Problem 1

You guessed right the answer is $5!$. The reason why we don't count the first is because the table doesn't have a beginning nor end. So let's say one combination is:

$${1,2,3,4,5,6}$$

Where men are numbered from $1-3$ and women are number from $4-6$. If we start counting from the last one we'll get a combination:

$${6,1,2,3,4,5}$$

But these combination are completely the same, so to avoid double counting we fix one as our stating point.

To make it even simpler. There are $6!$ combinations, but note there are 6 people and we can start counting from anyone so every combination will be included six times, so we divide by $6$. That's:

$$\frac{6!}{6} = 5!$$

Problem 2

It'll be much easier to count the "bad" combinations and subtract them from the total number of combinations. We could think of them two as one person, so there will be 5 people to sit down.

This means that there are $5!$ combination. But for the same reason we mentioned earlier we'll divide that number by 5. But note that when we "split" the two women the can sit in two different ways. So we'll have to multiply the number of combinations by 2. So the number of "bad" combinations is:

$$\frac{5!}{5} \cdot 2 = 4!\times2$$

And the total number of combinations that satisfy the condition is:

$$\frac{6!}{6} - 4!\times2 = 120 - 48 = 72$$

Problem 3

This is a type of stars and bars combinatorics, but because there are 3 men and 3 women, that implies that the order must be alternating, so it'll be easier to come up with our own "formula"

Let $1,3,5$ be "male places" and $2,4,6$ be "female places". For the male places there are $3!$ number of ways, so does for the female places. But note that this time we have to divide by $3$, as there are 3 persons to start counting from. So the total number of combination is:

$$\frac{3!\cdot3!}{3} = 2! \cdot3! = 12$$

user366855
  • 99
Stefan4024
  • 35,843
  • I have to make a confession, it's an extremely great answer, finally I start understanding how the things work, thank you very much for your answer. – user16168 Sep 12 '13 at 06:41
  • May be I can ask you, can advice some textbook or any other source of information with intuitive description of combinations and probability and how to solve this type of problems. What I saw so far has only enormous number of exercises without intuitive explanation. – user16168 Sep 12 '13 at 06:43
  • Maybe I'll disappoint you, but at least for me it's not easy to understand the theory in combinatiorics and probability. The routine of solving these problems comes with pracice.

    One advice, don't try to remember all those big formulas, because almost every problem in combinatorics is unique and it requires creativity to solve it, so it's enough to remember that binomial coefficients are used for combinations and factorails are used for permutations and when you're solving you just try to combine them.

     – Stefan4024 Sep 12 '13 at 09:36
  • When you are new to this field of mathematics try to exaust every case. Split the problem into easier simular sub-problems and then just think how you can get all comibnations or permutations of it and then try to make a formula and to caulcate it.

    And I'm sorry but I don't know a textbook for you, because all knowledge about combinatorics I learned at school, from the school book and from book for contests. But as I say in this book there weren't any explanation, but just given solution and then you try to understand. As I say knowledge comes with practice.

     – Stefan4024 Sep 12 '13 at 09:41
  • And my last advise to solve a combinatorics problem the most imporant thing is logic and to try to understand the question. One good advise is to go to wikipedia pages for combinations, permutations, variations... to read something about basic stuff of combinatorics then you just apply that knowledge. When you face a problem try to solve it as far as you can, but if you can't see the solution, but not try to remember the way for further uses. Instead try to understand how the author of the book came to that solution,starting from basic knowledge and just applying logic. – Stefan4024 Sep 12 '13 at 09:45
  • 3
    @Stefan4024 In problem 3, you divided by $3\times 3$ but that is too much. You should only divide by 3, and the answer is 12. –  Dec 05 '13 at 15:03