3
$\begingroup$

I am kind of stuck in a problem with possible combinations. The problem is:

Four couples, each consisting of a man and a woman are sitting at a round table. How many possible combinations are there so that none of the couples (the man and a woman in the relationship) are sitting next to each other

I tried some things that got nowhere and now this is where I am at: Every possible combination that has nothing with them being a couple is $ 7! $. Then I wanted to count how many combinations are for the first couple to be sitting next to each other (which I think is $ 2\cdot6! $). It should be the same for every other of the three couples. But before I subtract it from the whole $ 7! $ combinations, I thought there are some possibilities I counted twice. For example, when I counted the combinations of the first couple to be sitting next to each other, I also count some of them when I count the combinations of the second couple etc. So I am kind of stuck on how to find those.

I don't know if it's a correct or the optimal way, but any comments on how to find what I am missing? Or I guess another way to approach this?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ You are correct that when you subtract $2\cdot 6!$ from $7!$ for each of your couples, you will have subtracted too much due to overcounting (note: $4\cdot 2\cdot 6!=8\cdot 6!>7\cdot 6!=7!$). This is not a problem however because it is just a reminder that you are not yet done applying inclusion-exclusion principle. Go back and count if two known couples are sitting together, and then three, and then all four as well and use those in your calculations too. $\endgroup$ – JMoravitz Mar 12 '18 at 21:16
  • $\begingroup$ So if I did this right, every possible combination is $7!$, every combination for one of the couples to sit together is $ 2\cdot6! $, for two of the couples to sit together is $ 2^2\cdot5! $, for three of the couples to sit together $ 2^3\cdot4! $ and $ 2^4\cdot3! $ for every couple to be sitting together. So we have $ 7! - 2\cdot6! - 2^2\cdot5! - 2^3\cdot4! + 2^4\cdot3! $ $\endgroup$ – eva Mar 12 '18 at 21:58
  • $\begingroup$ Maybe $ 7! - 4\cdot2\cdot6! + 6\cdot2^2\cdot5! + 4\cdot2^3\cdot4! - 2^4\cdot3! $ ? $\endgroup$ – eva Mar 12 '18 at 22:06
  • 1
    $\begingroup$ Almost. The signs should alternate. $\endgroup$ – N. F. Taussig Mar 12 '18 at 22:11
  • $\begingroup$ Oh yeah, I messed that up completely. Thank you $\endgroup$ – eva Mar 12 '18 at 22:14
2
$\begingroup$

Let our couples be Adam and Amanda, Bob and Betsy, Charles and Cathy, and Doug and Dorothy.

Let $A$ be the event that Adam and Amanda are sitting together, $B$ the event that Bob and Betsy are sitting together, etc...

Let $\Omega$ be the set of ways in which the eight can sit in the circle without regards to whether any couples are sitting or not sitting together.

In the comments above, you correctly calculated $|\Omega|=7!,~ |A|=2\cdot 6!,~|A\cap B|=2^2\cdot 5!,\dots$

We are interested in calculating $|\Omega\setminus (A\cup B\cup C\cup D)|$. This expands via inclusion-exclusion as:

$$|\Omega|-|A|-|B|-|C|-|D|+|A\cap B|+|A\cap C|+|A\cap D|+|B\cap C|+\dots - |A\cap B\cap C|-|A\cap B\cap D|-\dots + |A\cap B\cap C\cap D|$$

Plugging in the numbers and combining like terms, this becomes

$$7!-\binom{4}{1}2\cdot 6!+\binom{4}{2}2^2\cdot 5!-\binom{4}{3}2^3\cdot 4!+\binom{4}{4}2^4\cdot 3!$$

which can be evaluated or simplified further if desired.

|cite|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.