0
$\begingroup$

Three couples are supposed to sit down at a round table such that no one sits next to his/her partner. The six seats are not numbered such that any rotation of a given configuration is regarded as the same configuration. Use the principle of inclusion and exclusion to compute how many ways are there for the six people to sit down at a table.

$\endgroup$
0
$\begingroup$

EDIT: Oops, I misread this as circular permutations, never mind.

I think it would be easier to define your properties, or sets, however you like, to be the ones you don't want to count and then remove them. Thus, define your properties as:

$p_1=$ couple 1 sits together

$p_2=$ couple 2 sits together

$p_3=$ couple 3 sits together

Where, of course, your looking at the set of all possible circular permutations of 6 people, i.e. $5!$ What you want to find is the number of circular permutations with exactly none of those properties.

If one property holds, you pair a couple together, so you really are only ordering 5 people, so there are $4!$ circular permutations possible. However, there are also 2 possible configurations on how the couple sits, namely who is on the left, so you must also include a factor of 2.

Similarly, for some set X of properties, there are $(6-|X|-1)!*2^{|X|}$ possible ways to order the couples with at least those properties.

By PIE, there are $\sum_{i=0}^{3} \binom{3}{i} * (-1)^i * (6-i-1)! * 2^i $ ways to to seat these couples with none of the stated properties. Presumably, they'll have a slice of pie.

$\endgroup$
0
$\begingroup$

At the beginning we assume we are free to choose places, and we have $6! = 720$ possibilities.

Then, in order for one of the couples to sit together, we first of all check how many siting positions we have for a couple. We see that we have $6$ positions where the first couple can sit, and we can permute the couple in $2!$ way, so we have $6*2!$ for one couple to sit together, and then we need to multiply this with $4!$ which gives the permutations for the rest of the people to sit at a table. So, in overall for one couple to sit together we have $(6* 2!)*4! = 288$.

Next, we look the permutations where two of the couples sit together. Again for the first couple we have $6*2!$, but then for the second couple we have $3$ possible sitting positions, and we can again permute the couple in $2!$ way, therefore for the second couple we will have $3*2!$, which leaves the last couple with $1*2!$ (please note that we only care that two of the couples sit together, we simply don't care for the third couple here). So, in overall for two couples sitting together we have, $(6*2!)*(3*2!)*(1*2!) = 144$.

Lastly, we at the possibilities where all the couples sit together (what I mean with together is each partner sits next to his/her partner). We again have $6*2!$ for the first couple, but now for the second couple we will have $2*2!$, we actually have $3$ sitting options for the second couple (just like in the above case), but there is one sitting options which will make the third couple's partners not sitting next to each other, so we exclude that, and therefore we have only $2$ options. Lastly, for the third couple we will have $1*2!$. Which in overall gives, $(6*2!)*(2*2!)*(1*2!) = 96$.

Because, we have three couples, we need to use the first permutation and the second permutation three times, and lastly we divide by $6$ due to symmetry in the problem definition. So, in total we have: $$\frac{720 - 288 - 288 - 288 + 144 + 144 + 144 - 96}{6} = \frac{192}{6} = 32$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy