0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ By "near" her husband, do you mean "next to"? $\endgroup$
    – 5xum
    Oct 5, 2017 at 11:39
  • 3
    $\begingroup$ Also, what is your attempt at solving this? $\endgroup$
    – 5xum
    Oct 5, 2017 at 11:40
  • $\begingroup$ 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 $\endgroup$
    – mdave16
    Oct 5, 2017 at 11:42
  • $\begingroup$ @5xum Thank you. Well, I just need to get the idea, because now I'm not sure where to start. $\endgroup$
    – Karagum
    Oct 5, 2017 at 11:42
  • $\begingroup$ You can use the Inclusion-Exclusion Principle. $\endgroup$ Oct 5, 2017 at 11:52

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .