## Combinatorics Problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Suffusion of Yellow
Posts: 42
Joined: Thu Jan 01, 2009 6:15 pm UTC

### Combinatorics Problem

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!

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

### 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.