A permutation {x_{1}, x_{2}, ... , x_{m}} of the set {1, 2, ... , 2n} where n is a positive integer is said to have property P if |x_{i} - x_{i+1}| = n for at least one i in {1, 2, ... , 2n-1}. Show that for each n there are more permutations with property P than without.

**Solution**

*from Arthur Engel, Problem-Solving Strategies, Springer 1998 [Problem books in mathematics series], ISBN 0387982191. A rather good training book.*

Let A_{k} be the set of permutations with k and k+n in neighboring positions, and let A be the set of permutations with property P, so that A is the union of the A_{k}.

Then |A| = Sum_{k} |A_{k}| - Sum_{k<l} |A_{k}ÇA_{l}| + Sum_{k<l<m} |A_{k}ÇA_{l}ÇA_{m}| - ... . But this is an alternating sequence of monotonically decreasing terms, hence |A| >= Sum_{k} |A_{k}| - Sum_{k<l} |A_{k}ÇA_{l}|.

But |A_{k}| = 2 (2n - 1)! (two orders for k, k+n and then (2n - 1)! ways of arranging the 2n - 1 items, treating k, k+n as a single item). Similarly, |A_{k}ÇA_{l}| = 4 (2n - 2)! So |A| >= (2n - 2)! [n.2(2n -1) - n(n - 1)/2 4] = 2n^{2} (2n - 2)! > (2n)!/2.

The solutions given on this site are not always complete, they are designed to be sufficient for anyone who has thought hard about the problem.

(C) John Scholes

jscholes@kalva.demon.co.uk

3 Sep 1999