MathLabs

第6問

集合 {1,2,…,2n}\{1,2,\ldots,2n\} の順列 (x1,x2,…,x2n)(x_1,x_2,\ldots,x_{2n}) が性質 PP を持つとは、ある i∈{1,…,2n−1}i\in\{1,\ldots,2n-1\} について ∣xi−xi+1∣=n|x_i-x_{i+1}|=n となることである。任意の正整数 nn に対し、性質 PP を持つ順列の方が持たない順列より多いことを証明せよ。
ステップ 4/5: 包除原理を打ち切る
前のステップ次のステップ
ざっくり言うと

包除原理の最初の2層だけで有効な下界が得られる。

∣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)!
詳しい解説

完全な包除式は非負項が交互に現れ大きさが減少するので、2重交差までで打ち切れば ∣A∣≥∑k∣Ak∣−∑k<l∣Ak∩Al∣|A|\ge\sum_k|A_k|-\sum_{k<l}|A_k\cap A_l|。ステップ2,3を代入して ∣A∣≥2n2(2n−2)!|A|\ge2n^2(2n-2)! を得る。