置換 (数学)
n の置換 σ の ascent(上昇点)とは、次の値が現在のものよりも大きくなる、任意の位置 i (< n) を言う。つまり、σ = σ1σ2...σn のとき、i が ascent であるとは σi < σi+1 となることを言う。
例えば、置換 3452167 は 1, 2, 5, 6 番目の位置に ascent を持つ。
同様に descent(下降点)は σi > σi+1 となる位置 i (< n) を言う。従って、1 ≤ i < n なる任意の i は、σ の ascent であるか descent であるかの何れかになる。
k 個の ascent を持つ n の置換の総数は、オイラー数 (組合せ論)(英語版) ⟨ n k ⟩ {\displaystyle \textstyle \left\langle {n \atop k}\right\rangle } で与えられる。これは k 個の descent を持つ n の置換の総数にも等しい。
置換の ascending run(上昇列)とは、置換の空でない連続した増大部分列で、両端で延長できないものをいう。
[ 1 2 3 ⋯ n 1 2 3 ⋯ n ] {\displaystyle {\begin{bmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{bmatrix}}}
である。
全単射は逆写像を持つから、置換もそうで、σ の逆元 σ は再び置換になる。陽に書けば、σ(x) = y なる限り σ(y) = x が成り立つ。二行記法で逆置換を得るには、二つの行を入れ替えればよい(必要なら入れ替えた後列を並べ替えて一行目が与えられた順番になるようにする)。例えば、
[ 1 2 3 4 5 2 5 4 3 1 ] − 1 = [ 2 5 4 3 1 1 2 3 4 5 ] = [ 1 2 3 4 5 5 1 4 3 2 ] {\displaystyle {\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}^{-1}={\begin{bmatrix}2&5&4&3&1\\1&2&3&4&5\end{bmatrix}}={\begin{bmatrix}1&2&3&4&5\\5&1&4&3&2\end{bmatrix}}}
である。巡回置換表示で逆置換を得るには、現れる巡回置換において元を逆順に並べなおせば、それがそのまま逆置換の巡回置換表示になる。