So I have this homework problem (I know, I know) where you have to sit n couples around a table with no couple sitting together. You're supposed to use inclusion-exclusion to solve it, I have no idea how, so I found a recursion I think answers it instead.

Then, however, I Googled it to be safe and found answers on legit looking websites that come up with values different than mine for various n. For instance,

http://www.math.dartmouth.edu/~doyle/do ... enage.html (the "relaxed" one)

I looked through their thinking, which opens with "we begin with the set S of all (2n)! ways of seating the 2n individuals around the table." I can't help thinking that its actually (2n-1!) ways. Am I wrong? Is Dartmouth (and a lot of other websites) wrong? Help!

## Combinatorics Problem

**Moderators:** gmalivuk, Moderators General, Prelates

### Re: Combinatorics Problem

The inclusion-exclusion answer is as follows: start with all possible seatings, subtract the ones with at least one couple sitting together, add the ones with at least two couples sitting together, ...

Anyway, (2n)! is the number of ways to seat individuals around a table if you don't consider rotation, i.e. if you distinguish a chair. For this problem, it doesn't matter when you divide by 2n since all of the orbits under rotation are of the same size.

Anyway, (2n)! is the number of ways to seat individuals around a table if you don't consider rotation, i.e. if you distinguish a chair. For this problem, it doesn't matter when you divide by 2n since all of the orbits under rotation are of the same size.

### Who is online

Users browsing this forum: No registered users and 7 guests