# Sitting 10 pairs in 20 chairs and around the circled table

I have two combinatoric problems.

1. There are 20 people (10 pairs each considered of man and woman) and we need to seat them in 20 chairs (chairs are placed in a line). And there is a condition: every woman cannot sit next to her husband. How many ways there are?
2. There are same conditions, but we need to seat them at a round table that has 20 chairs.

I need explained ideas because I want to understand every single condition.

• By "near" her husband, do you mean "next to"? – 5xum Oct 5 '17 at 11:39
• Also, what is your attempt at solving this? – 5xum Oct 5 '17 at 11:40
• One way you may want to start is by trying a smaller problem of 4 people (2 M and 2 F) with same conditions, and then with 6 – mdave16 Oct 5 '17 at 11:42
• @5xum Thank you. Well, I just need to get the idea, because now I'm not sure where to start. – Karagum Oct 5 '17 at 11:42
• You can use the Inclusion-Exclusion Principle. – N. F. Taussig Oct 5 '17 at 11:52

For the first problem:

Total possibilities for $20$ people to sit in a line is $20!$ If we wanted all of them to sit as couples, that would be $10!$ possibilities multiplied by $2^{10}$, because each couple can choose, which of them sits on the left chair and it doesn't change anything in our case.

If we need $k$ couples to sit together, this is $(20-k)!$ total possibilitites, multiplied with $2^k$ possibile arrangements within the couples. We don't forget, that there is a $\binom{n}{k}$ number of ways to choose the $k$ couples from the $n$ total.

Therefore, our formula is (it involves double countings, therefore the $-$ every second case):

$$(2n)! - 2^1{n \choose 1} (2n-1)!+ 2^2{n \choose 2} (2n-2)! - \cdots 2^k{n \choose k} (2n-k)! \cdots 2^n n!$$ $$=\sum_{k=0}^n (-2)^k{n \choose k} (2n-k)!$$

You can calculate it for $n=20$ and $k=10$.

The original source of this answer is this question, but I tried to write it down for your case.

You can also check it here: http://oeis.org/A007060