2

A group of $n$ people is seated at a round table. The group leaves the table for a break and then returns. In how many ways can the people sit down so that no one is to the right of the same person as in the previous seating?

I have been working on this problem for a little bit but it still confuses me. I understand it should be solved through Inclusion-Exclusion, but I struggle with the concept.

The concept seems straight forward. The first person that sits down has $1$ choice, the second person has $(n-2)$ choices, but if the second person sits in the $n$th seat, the third person will have $(n-2)$ choices, but if he doesn't sit in the $n$th seat the third person has $(n-3)$ choices.

My idea was to define a set $A_i$ that contains the lists of length $n$ whose elements are chosen from $\{1,2,\ldots,n\}$ w/o repetition such that for all $1\le i \le n$ the $(i+1)$st element is not in the following spot of the $i$th spot. Then $i$ would take the total possible combinations $(n-1)!$ and subtract it from the set $A_i$ but I'm not entirely sure how to do that.

I also believe it has something to do with derangements and the formula $$n!\sum_{i=0}^n \frac{(-1)^i}{i!}$$ but I am having difficulty connecting the two.

N. F. Taussig
  • 76,571
helplessmathstudent
  • 21
  • 2

1 Answers1

1

As you say, approach this via Inclusion-Exclusion.

Start with $5$ people. There are $4!$ ways to arrange them at a circular table, but then you multiply by $5$ to anchor person $A$ at a particular chair.

Now consider a pair, AB, that must not appear. Make them a unit, there are now 4 units AB,C,D,E. They can be arranged in a circular table in $3!$ ways, but multiply by $5$ to anchor $A$ at a particular chair. There are 5 of these possible pairs - AB,BC,CD,DE,EA - so subtract $5^23!$ in the Inclusion-Exclusion method.

Now two pairs. Whether it is AB and BC, or AB and CD, there are now three units. Similar calculation as before gives $5{5\choose2}2!$ to be added back on.

With $k$ 'illegal' pairs, there are $5{5\choose k}(4-k)!=\frac{5\cdot5!(4-k)!}{k!(5-k)!}=\frac{5\cdot5!}{k!(5-k)}$ arrangements.

That must be adjusted for $k=5$, when there are $5$ arrangements.

The total is

$$5(-1)^5+\sum_{k=0}^4(-1)^k\frac5{5-k}\frac{5!}{k!}$$

This is A167760 in the Online Encyclopedia of Integer Sequences.

Empy2
  • 50,853