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 を持つ順列の方が持たない順列より多いことを証明せよ。
ステップ 3/5: 2つの同時隣接を数える
前のステップ次のステップ
ざっくり言うと

2つの隣接条件は独立に圧縮できるので交わりも明示的に数えられる。

∣Ak∩Al∣=4(2n−2)!(k≠l)|A_k\cap A_l|=4(2n-2)!\quad(k\ne l)
詳しい解説

異なる k,lk,l について2組をそれぞれブロックにする。各ブロックは 22 通りの内部順序を持ち、得られる 2n−22n-2 個の対象は (2n−2)!(2n-2)! 通り。ゆえに ∣Ak∩Al∣=4(2n−2)!|A_k\cap A_l|=4(2n-2)!。