置換 (数学)
↑ N. L. Biggs, The roots of combinatorics, Historia Math. 6 (1979) 109−136
1 2 鈴木 1977, p. 53, 定義 7.1.
↑ Bóna 2012, p. 1, Definition 0.1.
↑ 鈴木 1977, p. 54.
↑ 鈴木 1977, p. 54, (7.2).
↑ 鈴木 1977, p. 55, 定義 7.3.
↑ 鈴木 1977, p. 55, (7.4).
↑ Kleiner 1986, p. 202.
↑ 成嶋 2003, p. 88.
↑ 成嶋 2003, p. 145.
↑ 鈴木 1977, pp. 284–285, 定義 2.5.
1 2 鈴木 1977, p. 285, (2.6).
↑ Humphreys 1996, p. 84.
↑ Bóna 2004, p. 3.
↑ Bóna 2012, pp. 4f.
↑ Bóna 2012, p. 53, Definition 2.1.
↑ Bóna 2004, pp. 43ff.
別のところに descent ができるかもしれないが)。この操作によって転倒数は 1 減少する。転倒数が 0 でないならば、恒等置換でなく、したがって少なくとも一つの descent が存在する。バブルソートおよび挿入ソートはこの方法で列を正順にする特定の実例と解釈することができる。ついでながら、この方法で任意の置換 σ が基本互換の積に表せることが示せる。これにより、置換 σ は、それを表す互換の列を単に逆転させることで、恒等置換にすることができる。実は、σ を恒等置換にする基本互換の列を全て数え上げることにより(それを逆順にして)、σ の基本互換の積として表す長さ最短の表示を全て見つけることができる。
転倒数 k を持つ n の置換の総数はメイホン数によって表される。それは(X を q に置き換えて)q 階乗 [n]q! と呼ばれる積
∏ m = 1 n ∑ i = 0 m − 1 X i = 1 ( 1 + X ) ( 1 + X + X 2 ) ⋯ ( 1 + X + X 2 + ⋯ + X n − 1 ) {\displaystyle \textstyle \prod \limits _{m=1}^{n}\sum \limits _{i=0}^{m-1}X^{i}=1(1+X)(1+X+X^{2})\cdots (1+X+X^{2}+\cdots +X^{n-1})}
の展開における X の係数である。
n 個の要素の置換の総数を決定する規則は少なくとも1150年ごろにはヒンズー文化において知られていた。インドの数学者バースカラ2世による著書に
The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.
と訳せる一節が含まれる。
一見関係なさそうな数学の問いが置換を通じて研究された最初の事例は、1770年ごろにラグランジュが代数方程式の研究において、方程式の根の置換と方程式の可解性との関係を観察したことである。 この方向性をルフィニが引き継いで進めた結果、5次以上の代数方程式には解の公式が無い事が示された。しかし、置換は文字の順列として表されており、まだ読みにくいものだった。ルフィニの成果に感動したコーシーは置換の記号の簡略化や理論の一般化を行い1815年に『置換論』としてまとめ上げた。アーベルはルフィニの論文を直接には知らなかったがコーシーの『置換論』を読み、ルフィニの論文に欠けていた代数的可解性の原則も証明した上で独自に5次以上の代数方程式には解の公式が無い事を示した(アーベル–ルフィニの定理)。さらに代数的可解性を分析したガロアは、何が(一変数)多項式方程式の可解と不可解とを根本的に決めているのかを完全に記述するガロア理論に到達した。現代数学において、同様に問題の理解に際して関連するある種の置換を調べることになるという状況は多く存在している。