置換 (数学)
同様の理由で、置換は計算機科学におけるソートアルゴリズムの研究において生じる。
代数学、特に群論において、集合 S 上の置換は S から自身への全単射(つまり写像 S → S で S の各元が像としてちょうど一つずつ現れるもの)として定義される。これは各元 s を対応する f(s) と入れ替えるという意味での S の並べ替え (rearrangement) と関連する。このような置換の全体は対称群と呼ばれる群を成す。重要なことは、置換の合成が定義できること、つまり二つの並べ替えを続けて行うと、それは全体として別の並べ替えになっているということである。S 上の置換は、S の元(あるいはそれを特定の記号によって置き換えたもの)を対象として、それらに対象の並べ替えとして作用する。
初等組合せ論において、「順列と置換」はともに n 元集合から k 個の元を取り出す方法として可能なものを数え上げる問題に関するもので、取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。k = n の場合には、k-順列は本項に言う意味での置換となるが、それ以外の場合には順列の項へ譲る。
組合せ論における n 元集合 S の置換は、S の元を(各元をちょうど一回ずつ)適当な順に並べたものである。これは厳密には、集合 {1, 2, ..., n} から S への全単射を言う。S = {1, 2, ..., n} のときには、群論的な定義と一致することに注意せよ。より一般に、集合 {1, 2, ..., n} の代わりに、その元が全順序付けられた任意の集合を用いることができる。
S の全順序を用いないで定義できる置換の群論的解釈とも関係する組合せ論的性質の一つは、置換 σ の循環構造(英語版) (cycle structure) で、これは、σ の循環の長さを記述する n の分割である。ここでは、σ の任意の不動点に対して分割の "1" の部分が存在する。不動点を持たない置換は完全順列 (derangement) と呼ばれる。
しかし、他の組合せ論的性質は S の順序やそれと置換とを関連付ける方法に直接的に関係している。
数学における置換(ちかん、英: permutation)の概念は、いくつか僅かに異なった意味で用いられるが、いずれも対象や値を「並べ替える」ことに関するものである。有り体に言えば、対象からなる集合の置換というのは、それらの対象に適当な順番を与えて並べることを言う。例えば、集合 {1, 2, 3} の置換は、
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
の全部で六種類ある順序組である。単語のアナグラムは、単語を構成する文字列に対する置換として定められる。そういった意味での置換の研究は、一般には組合せ論に属する話題である。
相異なる n 個の対象の置換の総数は n×(n − 1)×(n − 2)×...×2×1 通りであり、これは "n!" と書いて n の階乗と呼ばれる。
置換の概念は、多かれ少なかれ(あるいは陰に陽に)、数学のほとんどすべての領域に現れる。たとえばある有限集合上に異なる順序付けが考えられる場合に、単にそれらの順番を無視したいとか、無視した時にどれほどの配置が同一視されるかを知る必要があるなどの理由で、置換が行われることも多い。