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.

  • $\begingroup$ By "near" her husband, do you mean "next to"? $\endgroup$ – 5xum Oct 5 '17 at 11:39
  • 3
    $\begingroup$ Also, what is your attempt at solving this? $\endgroup$ – 5xum Oct 5 '17 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 '17 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 '17 at 11:42
  • $\begingroup$ You can use the Inclusion-Exclusion Principle. $\endgroup$ – 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


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.