MathLabs

Problem 6

A permutation (x1,x2,…,x2n)(x_1,x_2,\ldots,x_{2n}) of {1,2,…,2n}\{1,2,\ldots,2n\} has property PP if ∣xi−xi+1∣=n|x_i-x_{i+1}|=n for at least one i∈{1,…,2n−1}i\in\{1,\ldots,2n-1\}. Prove that for every positive integer nn there are more permutations with property PP than without it.
Step 2 of 5: Count one adjacency event
Previous stepNext step
In plain words

Block compression turns an adjacency requirement into a factorial count.

∣Ak∣=2(2n−1)!|A_k|=2(2n-1)!
Detailed analysis

Treat k,k+nk,k+n as one block. The block can be ordered in 22 ways, and the resulting 2n−12n-1 objects can be arranged in (2n−1)!(2n-1)! ways. Thus ∣Ak∣=2(2n−1)!|A_k|=2(2n-1)!.