4
$\begingroup$

I am not sure how to approach this question.

How many ways are there to seat n couples around a circular table such that no couple sits next to each other?

Since it's a part of inclusion-exclusion, I'm supposed to use that method. But I have no clue how to approach this. I know total number of people are 2n and that's about it. I've looked at other stack exchange questions on the same exact problem but none of them helped...

  • So I looked at the Menage problem, but that's seriously confusing - it's worse than other Mathexchange answers. In the solution, it mentions $d_k = (2n/2n-k) * C(2n-k,k) $. I have no clue where this guy came from.
$\endgroup$
  • 5
    $\begingroup$ A solution is posted here. $\endgroup$ – N. F. Taussig May 4 '18 at 0:08
  • $\begingroup$ unfortunately, that only confused me. @N.F.Taussig $\endgroup$ – Subin Park May 8 '18 at 2:19
  • $\begingroup$ Why don't you see the reference mentioned there? In summary, if $f(n,k)$ denotes the number of ways of selecting $k$ objects, no two consecutive, from $n$ objects arranged in a row (not a circle), then $f(n,k) = \binom{n-k+1}{k}.$ (Easy recurrence formula with $f(n,1)=n,$ $f(n,n )=0$ and $f(n,k) = f(n-1,k)+f(n-2,k-1)$. We also could show $d_k = f(2n-1,k)+f(2n-3,k-1) = \frac{2n}{2n-k}\binom{2n-k}{k}$ dividing cases. Both formulae come from dividing cases by whether the selections contain the first element or not. $\endgroup$ – Kanu Kim May 14 '18 at 7:26
  • $\begingroup$ I found someone already answered: math.stackexchange.com/questions/2772732/… $\endgroup$ – Kanu Kim May 14 '18 at 8:06
0
$\begingroup$

Here's how a straightforward application of inclusion-exclusion would go:

First you count the ways that you can seat the people with no strings attached. That's $(2n)!$ (or $(2n-1)!$ if you're discounting rotations; I'm not sure if you are or not, so I'll assume you're not, but it just affects all the answers by a factor of $2n$)

Then you exclude the ways you can seat the people with one couple together. That's $2 \cdot (2n-1)!$; $2$ ways to seat the couple once their location has been determined, and $(2n-1)!$ ways to seat $2n-2$ people and $1$ couple around the table (counting the couple as one object, since they must sit together). There are $n$ couples, so you'll subtract $n \cdot 2 \cdot (2n-1)!$

Then you re-include the ways you can seat the people with two couples together. That's $2^2 \cdot (2n-2)!$: $2^2$ ways to seat the two couples once their locations have been determined, and $(2n-2)!$ ways to seat $2n-4$ people and $2$ couples. There are $\binom n2$ couples so you'll add back $\binom n2 \cdot 2^2 \cdot (2n-2)!$

Etc.

$\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.