Problem 6

A permutation

(x_1,x_2,\ldots,x_{2n})

\{1,2,\ldots,2n\}

has property

P

|x_i-x_{i+1}|=n

for at least one

i\in\{1,\ldots,2n-1\}

. Prove that for every positive integer

n

there are more permutations with property

P

than without it.

Step 3 of 5: Count two simultaneous adjacencies

Previous step Next step

In plain words

Two required adjacencies compress independently, so their intersection is still explicit.

|A_k\cap A_l|=4(2n-2)!\quad(k\ne l)

Detailed analysis

For distinct $k,l$ , compress both pairs into two blocks. Each block has $2$ internal orders, and the resulting $2n-2$ objects can be arranged in $(2n-2)!$ ways. Hence $|A_k\cap A_l|=4(2n-2)!$ .