Combinatorics – Number of Ways to Sit Six People at a Circular Table

combinatorics

Problem: Six people are to sit at a circular table. Two of the people are not
to sit immediately beside each other. Find the number of ways that the
six people can be seated

I'm really stuck on this question. The correct answer is $72$, but my solutions seem to be incorrect (I get $432$ ways as an answer). I've tried to solve the problem in two ways, and these are my workings so far

Method 1:

Call the two restricted people $p_1$ and $p_2$

There are 6 choices for the first person $p_1$ to be seated, so hence $6$ ways.

The second person $p_2$ cannot sit immediately beside $p_1$, so there are $5-2 = 3$ ways the second person $p_2$ can sit.

After sitting $p_1$ and $p_2$, the remaining people can be seated in $4!$ ways.

So the number of ways with $p_1$ not next to $p_2$ = $6 \cdot3\cdot4! = 432$ ways

Method 2:

With no restrictions 6 people can be seated in $6!$ ways.

Again, there are 6 choices for the first person $p_1$ to be seated, so hence $6$ ways.

There are 2 ways for $p_2$ to sit next to $p_1$.

The remaining people can be seated in $4!$ ways.

The six may be seated (with $p_1$ and $p_2$ next to each other) in $6\cdot2\cdot4! = 288$ ways.

So the number of ways with $p_1$ and $p_2$ not next to each other are $6!-288 = 432$ ways.


What am I doing wrong?

Best Answer

The original problem could be more clearly worded, I think.

When you say in Method 1 that there are 6 possible choices for person 1, this is "true", but only if you actually care about the seats as being distinct seats, as opposed to "arrangements of people" being what we care about. The key difference is that in this problem where there's a "circular table" in which a rotation of the table doesn't change the "arrangement of people".

For example, let's say that there are 6 chairs placed around a clock, just at the even numbers. So a chair at 2:00, at 4:00, ..., at 12:00. Suppose that you've placed all your people around the clock. Great! There's an arrangement! And your current solution keeps these clock numbers in mind, and this is why you get the answer you do.

But now rotate the clock so that 2:00 becomes 4:00, that 4:00 becomes 6:00, etc. The arrangement you found has now changed as long as we keep track of these hour markings. In fact, there are $6$ ways for you to "rotate" the clock around, keeping everyone in the exact same position (rotate by 2 hours, by 4 hours, by 6 hours,..., by 12 = 0 hours).

Now, in the table problem, we have no hour markings on our table, and so all of these rotations shouldn't affect what an arrangement of people looks like!

All that to say, you have overcounted by a factor of $6$. That is, once you pick a configuration of people around this clock, we remember that we aren't sitting around a clock, we're around a table without numbers to tell us "which hour" someone is sitting at. So all of the rotations we got beforehand should actually be "the same".

What we get, then, is a $6$-to-$1$ function $\{\text{clock arrangements}\} \to \{\text{table arrangements}\}$ where the function takes our clock arrangement and "forgets" the numbers on the clock. (Double check that there are always $6$ "clock" arrangements that correspond to every "table" arrangement.) We know (I hope) that if $f : A \to B$ is an $n$-to-$1$ function, then $|A| = |B|\cdot n$, or equivalently $|B| = \frac{|A|}{n}$, and so the $6$-to-$1$ function we have described just means we need to divide the current answer by $6$. Hence, $\frac{432}{6} = 72$.