MathLabs

第6题

若集合 {1,2,…,2n}\{1,2,\ldots,2n\} 的排列 (x1,x2,…,x2n)(x_1,x_2,\ldots,x_{2n}) 满足对于至少一个 i∈{1,…,2n−1}i\in\{1,\ldots,2n-1\} 有 ∣xi−xi+1∣=n|x_i-x_{i+1}|=n，就称其具有性质 PP。证明对每个正整数 nn，具有性质 PP 的排列多于不具有该性质的排列。
第 4/5 步：截断容斥公式
上一步下一步
通俗地说

容斥原理只需前两层就能给出有用下界。

∣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)!
详细分析

完整容斥式的非负项交替且递减,所以保留到二重交集有 ∣A∣≥∑k∣Ak∣−∑k<l∣Ak∩Al∣|A|\ge\sum_k|A_k|-\sum_{k<l}|A_k\cap A_l|。代入第二、三步得到 ∣A∣≥2n2(2n−2)!|A|\ge2n^2(2n-2)!.