For every positive integer , find (with proof) the number of ways of sitting people around a round table so that and are not next to each other for . Two sitting arrangements are considered the same if one can be obtained from another by a rotation. (You may express your answer in whatever ways.)
Solution
The answer is if , and is if , or any equivalent expression.
The result is obvious for . Consider . For each , let be the number of ways to arrange the people such that are next to each other for (and probably for some more pairs).
For each , we need to arrange pairs and the remaining people. There are ways to do so. Within each pair, there are ways to arrange the two people. Therefore, we have
Now, by the inclusion-exclusion principle, since there are ways to choose pairs, the number of ways to arrange the people such that no pair sits next to each other is
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.