置換 (数学)
群論とその周辺分野では、無限集合も含めた任意の集合上の置換を考えることができる。すなわち、集合 S の置換とは、S から S 自身への全単射のことを言う。この場合、置換の積を定義して置換群の概念が得られる。集合 S が n 元からなる有限集合ならば、S 上の置換は n! 個存在する。
置換の概念を研究対象とする分野について挙げる。
置換 σ の転倒とは、置換の成分が逆転する、即ち i < j かつ σi > σj となる位置の対 (i, j) を言う。故に descent とは、二つの隣接する位置における転倒に他ならない。例えば、置換 σ = 23154 は三つの転倒 (1,3), (2,3), (4,5) をそれぞれ成分の対 (2,1), (3,1), (5,4) において持つ。
あるいは転倒を、順番が逆になる値の対 (σi, σj) と定める場合もある。こうしても転倒の数(転倒数)は変化しないし、この逆順にされた対(上記のσの例でいうと (1,2), (1,3), (4,5))は、逆置換 σ(上記のσの例でいうと31254)の上で述べた意味での転倒になる。転倒数は置換の成分がどれほど入れ違いになっているかの度合いを表す重要な尺度であり、σ と σ とでは転倒数は同じになる。k 個の転倒を持つ置換を正順にする(恒等置換に変換する)ために、基本互換(隣接互換)を続けて(右乗によって)適用する方法が常に可能で、そのような操作を k 個並べた列が必要になる。さらに言えば、基本互換をうまく選ぶ方法があって、それには各段階において i がその置換の descent のときに i と i + 1 を入れ替えて、i が descent でないようにすれば十分である(この操作で目当ての descent は解消する。