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 的排列多于不具有该性质的排列。
第 3/5 步：计算两个同时相邻事件
上一步下一步
通俗地说

两个相邻条件可独立压缩,所以交集仍可直接计数。

∣Ak∩Al∣=4(2n−2)!(k≠l)|A_k\cap A_l|=4(2n-2)!\quad(k\ne l)
详细分析

对不同的 k,lk,l,把两对分别压成两个块。每块有 22 种内部顺序,合并后有 2n−22n-2 个对象,可排列 (2n−2)!(2n-2)! 种。因此 ∣Ak∩Al∣=4(2n−2)!|A_k\cap A_l|=4(2n-2)!.