1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.