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

ブロック化により隣接条件が階乗の計数になる。

∣Ak∣=2(2n−1)!|A_k|=2(2n-1)!
詳しい解説

k,k+nk,k+n を1つのブロックとみなす。ブロックの順序は 22 通りで、できた 2n−12n-1 個の対象は (2n−1)!(2n-1)! 通りに並べられる。したがって ∣Ak∣=2(2n−1)!|A_k|=2(2n-1)!。