順列を互換で整列するときの最小の回数

この記事のなかでは,互換,すなわち2つの位置だけを入れ替えるような置換のことをswapと呼ぶことにする.*1

長さnの順列\sigmaについて、swap列\sigma_1,\dots,\sigma_m\sigmaを整列するとは、
\sigma_m \dots \sigma_1 \sigma = \mathrm{id}となることであるとする.

命題1: 長さn\ge 3のサイクル\sigmaに対して,swap\tauを一回適用したときにできる順列\tau\sigmaをサイクル分解したときのサイクルの長さの和は少なくともn-1であり,またn-1にするような\tauは存在する.

命題1を証明する.
a\neq bについて,(場合1)(\tau\sigma)(a)\neq aかつ(\tau\sigma)(b)\neq bか,
(場合2)(\tau\sigma)(a) = aだが(\tau\sigma)(b)\neq bのどちらかが成り立つ.

場合1を考える.a\lt bと仮定して一般性を失なわない.
このとき,\tau\sigmaのサイクル分解を考えると,
1\to 2\to \dots \to a-1 \to b\to b+1\to \dots \to n \to 1というサイクルと,
a\to a+1\to \dots \to b-1 \to aというサイクルとに分解される.
ここで,場合1の仮定よりどちらの長さもきちんと2以上になっていることに注意する.
よって,サイクルの長さの和はnとなり,これはn-1以上である.

場合2を考える.\tau(1)=n,\tau(n)=1と仮定して一般性を失なわない.
このとき,1\to 2\to \dots \to n-1 \to 1という長さn-1のサイクルだけができる.
よって,サイクルの長さの和はn-1となる.これは,サイクルの長さの和をn-1にするような\tauの存在も示している.
命題1の証明おわり.

命題2: 長さn(>1)のサイクル\sigmaの整列に必要なswap列の長さの最小はn-1である.

命題2を証明する.その順列が整列されていることと,そのサイクル分解のサイクルの長さの和が0であることとは等価である.
n=2のときは明らか.n>3を考える.
命題1は,1回のswapではサイクル分解のサイクルの長さの和は高々1しか減らないこと,またそれを1減らすswapがあることを主張しているので,そこから分かる.命題2の証明おわり.

命題3: 順列\sigmaを整列するには,そのサイクル分解毎に整列するのが最短である.

命題3を証明する.順列\sigmaに対するswapのうち,2つのサイクル分解をまぜるようなもの\tauを考える.
\sigmaの分解には,(1,\dots,a)(a+1,\dots,b)とその他のサイクル\sigma_1,\dots,\sigma_mがあり,\tauaa+1を入れ替えるとして一般性を失なわない.このとき,\tau\sigmaのサイクル分解は,
1\to 2\to \dots \to a-1 \to b \to a+1 \to \dots \to b-1 \to a \to 1\sigma_1,\dots,\sigma_m
となり,サイクル分解のサイクルの長さの和は減少しない.
よって,サイクル分解毎に整列し,サイクルの長さの和を1ずつ減少させるのが最適である.
命題3の証明おわり.

*1:どっちがどっちかよく分からなくなるので.