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

Postby Suffusion of Yellow » Sun May 03, 2009 3:27 am UTC

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!

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

Re: Combinatorics Problem

Postby t0rajir0u » Sun May 03, 2009 3:36 am UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests