Maths Olympiad Prep

Library / /112 of 136

Combinatorics Difficulty 8.4 Shortlist Prove it Hong Kong

For every positive integer nn, find (with proof) the number of ways of sitting 2n2n people A1,B1,A2,B2,,An,BnA_1, B_1, A_2, B_2, \dots, A_n, B_n around a round table so that AiA_i and BiB_i are not next to each other for i=1,2,,ni = 1, 2, \dots, n. 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 00 if n=1n = 1, and is k=0n(1)k(nk)2k(2nk1)!\sum_{k=0}^{n} (-1)^k \binom{n}{k} 2^k (2n-k-1)! if n2n \ge 2, or any equivalent expression.

The result is obvious for n=1n = 1. Consider n2n \ge 2. For each k=0,1,,nk = 0, 1, \dots, n, let NkN_k be the number of ways to arrange the 2n2n people such that Ai,BiA_i, B_i are next to each other for i=1,2,,ki = 1, 2, \dots, k (and probably for some more pairs).

For each kk, we need to arrange kk pairs and the remaining 2n2k2n-2k people. There are (k+2n2k1)!=(2nk1)!(k+2n-2k-1)! = (2n-k-1)! ways to do so. Within each pair, there are 22 ways to arrange the two people. Therefore, we have
Nk=2k(2nk1)!. N_k = 2^k (2n - k - 1)! .
Now, by the inclusion-exclusion principle, since there are (nk)\binom{n}{k} ways to choose kk pairs, the number of ways to arrange the 2n2n people such that no pair Ai,BiA_i, B_i sits next to each other is
k=0n(1)k(nk)Nk=k=0n(1)k(nk)2k(2nk1)!. \sum_{k=0}^{n} (-1)^k \binom{n}{k} N_k = \sum_{k=0}^{n} (-1)^k \binom{n}{k} 2^k (2n-k-1)! .

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.