代数学、特に群論において、集合S 上の置換は S から自身への全単射(つまり写像 S → S で S の各元が像としてちょうど一つずつ現れるもの)として定義される。これは各元 s を対応する f(s) と入れ替えるという意味での S の並べ替え (rearrangement) と関連する。このような置換の全体は対称群と呼ばれる群を成す。重要なことは、置換の合成が定義できること、つまり二つの並べ替えを続けて行うと、それは全体として別の並べ替えになっているということである。S 上の置換は、S の元(あるいはそれを特定の記号によって置き換えたもの)を対象として、それらに対象の並べ替えとして作用する。
初等組合せ論において、「順列と置換」はともに n 元集合から k 個の元を取り出す方法として可能なものを数え上げる問題に関するもので、取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。k = n の場合には、k-順列は本項に言う意味での置換となるが、それ以外の場合には順列の項へ譲る。
歴史
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.[1]
群論とその周辺分野では、無限集合も含めた任意の集合上の置換を考えることができる。すなわち、集合 S 上の置換とは、S から S 自身への全単射のことを言う[2]。この場合、置換の積を定義して置換群の概念が得られる。集合 S が n 元からなる有限集合ならば、S 上の置換は n! 個存在する。
組合せ論の文脈で
組合せ論において置換とは、有限集合の各元を一つずつ、かつ唯一つずつ用いて得られる列と理解するのが普通である[3]。ここで、「列」の概念は「集合」の概念と異なり、列に現れる項は何らかの順序に従っていなければならない。つまり列は(それが空でなければ)「初項」を持ち、(長さが 2 より小さくなければ)第二項を持ち、といった具合に各項が順番に現れる。対照的に、集合の元に対しては順番の概念はなく、例えば {1, 2, 3} と {3, 2, 1} は表記が異なるだけで全く同じ集合を表す。この意味で、n 個の元からなる有限集合 S 上の置換は、各 i を列の第 j 項へ写すものとみて {1, 2, …, n} から S への全単射である。あるいは、x < y は、列の中で x の後に y が現れるという意味で定めて、S 上の一つの全順序を与えるものと見ることもできる。この意味での S 上の置換も、やはり n! 通り存在する。
置換の概念を少し弱めて「同じ元が二度は現れることがないが、与えられた集合の全ての元を使い切る必要はない」ものとした列を考えることが、初等組合せ論において頻出する。実際には、与えられた n 個の元からなる集合から、指定された長さ k の列を考えるという形で、この概念が用いられることが多い。これらの対象は、本項での置換の概念とは区別して、順列と呼ばれ、二項係数と深く関連する。
また、有限多重集合M 上の置換は、重複置換とも呼ばれ、M の各元が、自身の M における重複度とちょうど同じ数だけ現れるような列である。M の各元の重複度が、(適当な順に)m1, m2, …, ml で、それらの和(つまり M の位数)が n であるとすると、M 上の置換の総数は多項係数
群論においてある集合上の置換は、その集合からその集合自身の上への全単射を言う[2]。任意に与えられた集合の上の置換全体の成す集合は、写像の合成を積として、恒等変換を単位元とする群を成し、これを S の対称群と呼ぶ[4]。対称群は、同型を除いてその集合の濃度のみに依存して決まり、S の元の具体的な特徴がどうであるかは群構造に影響を与えない[5]。対称群は有限集合上のものを考えることがほとんどで、この場合には適当な自然数 n に対して S = {1, 2, …,n} であるとして一般性を失わない。こうして n 次の対称群 Σn が定まる。
第三の記法として置換の巡回置換表現(英語版)[10]は、置換を続けて施す効果に焦点を当てたものになっている。これは、置換を(少なくとも二つの元を持つ)軌道に対応する巡回置換の積として表す方法である。相異なる軌道は互いに素(交わりを持たない)から、感覚的には「互いに素な巡回置換に分解する」方法とも言える。このような記法を得るには、以下のようにする。まず S の元 x を σ(x) ≠ x なるようにとり、σ を繰り返し施して得られる像の列 (x σ(x) σ(σ(x)) …) を、像として x が現れるまで続ける。こうして書き下された値の集合は σ に関して x の属する軌道であり、得られた列はこの軌道に対応する σ の巡回置換成分の括弧書き記法になる。この後、既に書き下された軌道に属さない S の元 y があればそれを取って σ(y) ≠ y であるならば、同様にして対応する巡回置換成分が得られるから、以下これを繰り返して、S の任意の元が何れかの巡回置換に属するかさもなくば σ の不動点となるまで続ける。この手続きにおいて、新しい巡回置換を作るための始点とする元の取り方は一通りとは限らないから、一つの置換に対する巡回置換表示は、一般には複数存在する。例えば、やはり先と同じ例で言えば
のような表示が可能である。σ の各巡回置換成分 (x1x2 … xl) はそれ自身が置換を表しており、具体的にはこの軌道上で σ と同じく i < l のとき xi を xi+1 に写し、xl を x1) に写す一方、この軌道に属さない S の元は何れも動かさない。位数が l であるような軌道は、長さ l の巡回置換と呼ばれる。σ の相異なる軌道は定義により交わりを持たないから、それらに対応する巡回置換が可換であることは容易に分かり、σ はそれらの巡回置換の(施す順番を問わない)積に表される。従って、置換の巡回置換表現に現れる巡回置換の連結は置換の合成として解釈できるので、それを以って置換の「分解」と称する。分解に現れる巡回置換の順番を並べ替える以外に、σ を互いに疎な軌道を持つ巡回置換(σ と無関係な巡回置換も含めて)の積に書く方法はないので、そういう意味で巡回置換分解は一意的である。置換の巡回置換表現が一意的でない部分として、個々の巡回置換の表し方が一通りでないことが挙げられる。例えば上の例でも (5 1 2) は (1 2 5) と書いても同じ(だが (5 2 1) は異なる置換)である。
位数 1 の軌道(つまり σ の不動点 x ∈ S)は対応する巡回置換を持たない。なぜならそのような置換は x 同様に x 以外の S の元を不動にする、言い換えれば恒等変換になり、x とは無関係になるからである。σ が x を不動にすることを強調するために、σ の巡回置換表示に (x) を含めることは可能である(し、循環と不動点(英語版)で述べるように組合せ論ではその方が標準的でさえある)けれども、これは σ の分解における(群論的)因子には対応しない。「巡回置換」の概念に恒等置換も含めるならば、互いに素な巡回置換への置換の分解の(因子の順番を除く)一意性は失われる。恒等置換の互いに素な巡回置換への分解は空積、つまりその巡回置換表示は空となり、e などの別な記号を宛がうのが通例である。
Knuth, Donald. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.
Knuth, Donald. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.11-72.