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 4 of 5: Truncate inclusion–exclusion
Previous stepNext step
In plain words

Inclusion–exclusion needs only its first two layers for a useful lower bound.

∣A∣≥∑k∣Ak∣−∑k<l∣Ak∩Al∣=2n2(2n−2)!|A|\ge\sum_k|A_k|-\sum_{k<l}|A_k\cap A_l|=2n^2(2n-2)!
Detailed analysis

The full inclusion–exclusion expression alternates with decreasing nonnegative terms, so truncating after pair intersections gives ∣A∣≥∑k∣Ak∣−∑k<l∣Ak∩Al∣|A|\ge\sum_k|A_k|-\sum_{k<l}|A_k\cap A_l|. Substituting Steps 2–3 yields ∣A∣≥2n2(2n−2)!|A|\ge2n^2(2n-2)!.