置換 (数学)

この項目では、置換について説明しています。初等組合せ論における partial permutationについては「順列」をご覧ください。

数学における置換（ちかん、英: 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 の階乗と呼ばれる。

置換の概念は、多かれ少なかれ（あるいは陰に陽に）、数学のほとんどすべての領域に現れる。たとえばある有限集合上に異なる順序付けが考えられる場合に、単にそれらの順番を無視したいとか、無視した時にどれほどの配置が同一視されるかを知る必要があるなどの理由で、置換が行われることも多い。同様の理由で、置換は計算機科学におけるソートアルゴリズムの研究において生じる。

代数学、特に群論において、集合 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]

と訳せる一節が含まれる。

一見関係なさそうな数学の問いが置換を通じて研究された最初の事例は、1770年ごろにラグランジュが代数方程式の研究において、方程式の根の置換と方程式の可解性との関係を観察したことである。 この方向性をルフィニが引き継いで進めた結果、5次以上の代数方程式には解の公式が無い事が示された。しかし、置換は文字の順列として表されており、まだ読みにくいものだった。ルフィニの成果に感動したコーシーは置換の記号の簡略化や理論の一般化を行い1815年^{[要検証 – ノート]}に『置換論』としてまとめ上げた。アーベルはルフィニの論文を直接には知らなかったがコーシーの『置換論』を読み、ルフィニの論文に欠けていた代数的可解性の原則も証明した上で独自に5次以上の代数方程式には解の公式が無い事を示した(アーベル–ルフィニの定理)。さらに代数的可解性を分析したガロアは、何が（一変数）多項式方程式の可解と不可解とを根本的に決めているのかを完全に記述するガロア理論に到達した。現代数学において、同様に問題の理解に際して関連するある種の置換を調べることになるという状況は多く存在している。

一般性[編集]

置換の概念を研究対象とする分野について挙げる。

群論の文脈で[編集]

群論とその周辺分野では、無限集合も含めた任意の集合上の置換を考えることができる。すなわち、集合 S の置換とは、S から S 自身への全単射のことを言う^[2]。この場合、置換の積を定義して置換群の概念が得られる。集合 S が n 元からなる有限集合ならば、S 上の置換は n! 個存在する。

組合せ論の文脈で[編集]

組合せ論において置換とは、有限集合の各元を一つずつ、かつ唯一つずつ用いて得られる列と理解するのが普通である^[3]。ここで、「列」の概念は「集合」の概念と異なり、列に現れる項は何らかの順序に従っていなければならない。つまり列は（それが空でなければ）「初項」を持ち、（長さが 2 より小さくなければ）第二項を持ち、といった具合に各項が順番に現れる。対照的に、集合の元は決まった順番を持たず、例えば {1, 2, 3} と {3, 2, 1} は見た目が異なるだけで全く同じ集合である。この意味で、n 個の元からなる有限集合 S 上の置換は、各 i を列の第 i 項へ写すものとみて {1, 2, …, n} から S への全単射である。あるいは、x < y は、列の中で x の後に y が現れるという意味でさだめて、S 上の一つの全順序を与えるものと見ることもできる。この意味での S の置換も、やはり n! 通り存在する。

置換の概念を少し弱めて「同じ元が二度は現れることがないが、与えられた集合の全ての元を使い切る必要はない」ものとした列を考えることが、初等組合せ論においてたびたびある。実際には、与えられた n 個の元からなる集合から、決められた長さ k の列を考えるという形で、この概念が用いられることが多い。これらの対象は、本項に言う置換の概念と区別するために、順列と呼ばれ、二項係数と深く関連する。

また、有限多重集合 M 上の置換は、重複置換とも呼ばれ、M の各元が、自身の M における重複度とちょうど同じ数だけ現れるような列である。M の各元の重複度が、（適当な順に）m₁, m₂, …, m_l で、それらの和（つまり M の位数）が n であるとすると、M 上の置換の総数は多項係数

${\displaystyle {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}}$

によって与えられる。

群論的取扱い[編集]

群論においてある集合上の置換は、その集合からその集合自身の上への全単射を言う^[2]。任意に与えられた集合の上の置換全体の成す集合は、写像の合成を積として、恒等変換を単位元とする群を成し、これを S の対称群と呼ぶ^[4]。対称群は、同型を除いてその集合の濃度のみに依存して決まり、S の元の具体的な特徴がどうであるかは群構造に影響を与えない^[5]。対称群は有限集合上のものを考えることがほとんどで、この場合には適当な自然数 n に対して S = {1, 2, …,n} であるとして一般性を失わない。こうして n 次の対称群 Σ_n が定まる。

対称群の任意の部分群を置換群と呼ぶ^[6]。ケイリーの定理により、実は任意の群が何らかの置換群に同型であり^[7]、特に有限群は何らかの有限対称群の部分群に同型であることがわかる。しかし置換群は、抽象群よりも多くの構造を持つものであり、たとえば置換群の任意の元には巡回置換型を定義することができるが、置換群として実現されたのではない群がこれと同値な付加構造をもつことは必ずしも求められない。例えば、Σ₃ は自然に置換群となり、その任意の互換は巡回型が (2,1) となるが、ケイリーの定理の証明に従って Σ₃ を Σ₆ の部分群として（つまり、Σ₃ 自身に属する全 6 個の元の置換として）実現すれば、この置換群での互換の巡回置換型は (2, 2, 2) になる。つまり、ケイリーの定理の成立にも拘らず、置換群の研究は抽象群の研究とは異なる部分を持っているということになる。

記法について[編集]

有限集合 S の置換に対して、その記法は大きく三種類が存在する。1815年、コーシーによって導入された^[8]二行記法^{[訳語疑問点]}は一行目に S の元を書き、その各元の下に置換による像を書いて二行目とするものである。例えば、集合 {1, 2, 3, 4, 5} のある置換は

${\displaystyle \sigma ={\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}}$

と書くことができ、上と下の対応が同じなら横の順序は問わない記法である。

${\displaystyle \sigma ={\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}={\begin{bmatrix}2&4&5&1&3\\5&3&1&2&4\end{bmatrix}}={\begin{bmatrix}5&4&3&2&1\\1&3&4&5&2\end{bmatrix}}=\cdots }$

1852年、エンリコ・ベッチはこれを

${\displaystyle \sigma ={\begin{bmatrix}1&2&3&4&5\\\sigma (1)&\sigma (2)&\sigma (3)&\sigma (4)&\sigma (5)\end{bmatrix}}}$

のような対応関係と見て σ は σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, σ(5) = 1 を満たす写像とした。

コーシーの流儀では有理式 F(x₁, x₂, x₃, x₄, x₅) の置換を

${\displaystyle F(x_{1},x_{2},x_{3},x_{4},x_{5})\sigma =F(x_{1},x_{2},x_{3},x_{4},x_{5}){\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}=F(x_{2},x_{5},x_{4},x_{3},x_{1})}$

のように記述し、さらに別の置換τを行った時も右から作用させて

${\displaystyle \{F(x_{1},x_{2},x_{3},x_{4},x_{5})\sigma \}\tau =F(x_{1},x_{2},x_{3},x_{4},x_{5})(\sigma \tau )}$

としたため σ の後に τ を行う置換を στ で表すようになった。

一方でベッチの流儀を使う場合は合成写像として

${\displaystyle \tau (\sigma (1))=(\tau \circ \sigma )(1)}$

のように書き、時によって合成の記号「∘ 」を省略し σ の後に τ を行う置換を τσ で表した。一般に置換は交換可能ではないので置換の順序には注意が必要である。

二行記法の下の行だけを書くのが一行記法^{[訳語疑問点]}であり、先ほどの例であげた置換は一行記法だと 25431 で表される（成分が複数の文字、例えば二桁の数で表されるような場合には、成分の間にコンマを入れるのが典型的である）。

第三の記法として置換の巡回置換表現（英語版）^[10]は、置換を続けて施す効果に焦点を当てたものになっている。これは、置換を（少なくとも二つの元を持つ）軌道に対応する巡回置換の積として表す方法である。相異なる軌道は互いに素（交わりを持たない）から、感覚的には「互いに素な巡回置換に分解する」方法とも言える。このような記法を得るには、以下のようにする。まず S の元 x を σ(x) ≠ x なるようにとり、σ を繰り返し施して得られる像の列 (x σ(x) σ(σ(x)) …) を、像として x が現れるまで続ける。こうして書き下された値の集合は σ に関して x の属する軌道であり、得られた列はこの軌道に対応する σ の巡回置換成分の括弧書き記法になる。この後、既に書き下された軌道に属さない S の元 y があればそれを取って σ(y) ≠ y であるならば、同様にして対応する巡回置換成分が得られるから、以下これを繰り返して、S の任意の元が何れかの巡回置換に属するかさもなくば σ の不動点となるまで続ける。この手続きにおいて、新しい巡回置換を作るための始点とする元の取り方は一通りとは限らないから、一つの置換に対する巡回置換表示は、一般には複数存在する。例えば、やはり先と同じ例で言えば

${\displaystyle {\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}={\begin{bmatrix}1&2&5\end{bmatrix}}{\begin{bmatrix}3&4\end{bmatrix}}={\begin{bmatrix}3&4\end{bmatrix}}{\begin{bmatrix}1&2&5\end{bmatrix}}={\begin{bmatrix}3&4\end{bmatrix}}{\begin{bmatrix}5&1&2\end{bmatrix}}}$

のような表示が可能である。σ の各巡回置換成分 (x₁ x₂ … x_l) はそれ自身が置換を表しており、具体的にはこの軌道上で σ と同じく i < l のとき x_i を x_i+1 に写し、x_l を x₁) に写す一方、この軌道に属さない S の元は何れも動かさない。位数が l であるような軌道は、長さ l の巡回置換と呼ばれる。σ　の相異なる軌道は定義により交わりを持たないから、それらに対応する巡回置換が可換であることは容易に分かり、σ はそれらの巡回置換の（施す順番を問わない）積に表される。従って、置換の巡回置換表現に現れる巡回置換の連結は置換の合成として解釈できるので、それを以って置換の「分解」と称する。分解に現れる巡回置換の順番を並べ替える以外に、σ を互いに疎な軌道を持つ巡回置換（σ と無関係な巡回置換も含めて）の積に書く方法はないので、そういう意味で巡回置換分解は一意的である。置換の巡回置換表現が一意的でない部分として、個々の巡回置換の表し方が一通りでないことが挙げられる。例えば上の例でも (5 1 2) は (1 2 5) と書いても同じ（だが (5 2 1) は異なる置換）である。

位数 1 の軌道（つまり σ の不動点 x ∈ S）は対応する巡回置換を持たない。なぜならそのような置換は x 同様に x 以外の S の元を不動にする、言い換えれば恒等変換になり、x とは無関係になるからである。σ が x を不動にすることを強調するために、σ の巡回置換表示に (x) を含めることは可能である（し、循環と不動点（英語版）で述べるように組合せ論ではその方が標準的でさえある）けれども、これは σ の分解における（群論的）因子には対応しない。「巡回置換」の概念に恒等置換も含めるならば、互いに素な巡回置換への置換の分解の（因子の順番を除く）一意性は失われる。恒等置換の互いに素な巡回置換への分解は空積、つまりその巡回置換表示は空となり、e などの別な記号を宛がうのが通例である。

長さ 2 の巡回置換は互換と呼ばれ^[11]、二つの元をただ入れ替えるだけの置換である。

置換の積と逆置換[編集]

二つの置換の積は、それらの写像としての合成によって与えられる。つまり、σπ は与えられた集合の各元 x を σ(π(x)) へ写す。ここで注意すべきは、写像の記法に従って書いているため、一番右にある置換が最初に引数に適用されるということである。文献によっては、一番左の因子を最初に作用させる代わりに、置換をその引数の「右側」に書くものもある。例えば、冪記法を用いて、σ が x に作用することを x^σ で書けば、積は x^σπ = (x^σ)^π によって定められる。それでも、これらは置換の乗法に関して「異なる」規則を与えるものであるから、本項では写像の記法に従って一番右の因子から適用する流儀に従うものとする。

二つの全単射の合成は再び全単射を与えるから、二つの置換の積は再び置換を与える。写像の合成は結合的であるから、置換の積に関してもそうで、 (σπ)ρ = σ(πρ) が任意の置換に関して成立する。これにより、二つより多くの置換の積において、積の順番を表すグループ化の括弧を書かないのが普通である。また、中黒などの乗法を指し示す記号も、省略するのが通例である。

集合の各元をそれ自身に写す恒等置換は、この置換の積に関する単位元である。二行記法で言えば、この単位元は

${\displaystyle {\begin{bmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{bmatrix}}}$

である。

全単射は逆写像を持つから、置換もそうで、σ の逆元 σ⁻¹ は再び置換になる。陽に書けば、σ(x) = y なる限り σ⁻¹(y) = x が成り立つ。二行記法で逆置換を得るには、二つの行を入れ替えればよい（必要なら入れ替えた後列を並べ替えて一行目が与えられた順番になるようにする）。例えば、

${\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}}}$

である。巡回置換表示で逆置換を得るには、現れる巡回置換において元を逆順に並べなおせば、それがそのまま逆置換の巡回置換表示になる。

積が結合的で、単位元を持ち、任意の元が逆元を持つということから、S 上の置換全体の成す集合は群となり、S の対称群と呼ばれる。

有限集合上の任意の置換は互換の積に表すことができる^[12]。与えられた置換に対してそのような表示は無数に存在するけれども、それらの表示の中に現れる互換の数の偶奇は表示によらない^[12]。これにより、任意の置換は偶置換または奇置換に分類することができる。

置換の乗法を置換の巡回置換表現のもとで書くための平易なパターンというものは存在せず、積の巡回置換表示に現れる巡回置換は、積を取る個々の置換に現れる巡回置換とは全く異なるものになってしまう。しかし、置換 σ に対して別の置換 π による共軛変換を取る、つまり積 πσπ⁻¹ を作る特別の場合においては、巡回置換構造が保たれる。共軛変換で得られた置換の巡回置換表示は、σ の巡回置換表示に現れる各成分に π を施したものとして与えられる^[13]。

集合 {1, 2, …, n} 上の置換を n 次正方行列として表すこともできる。これを行うのに自然な方法は二種類あるが、行列の積が置換の積に同じ順番で対応するのはそのうちの一方だけである。このとき、置換 σ には i = σ(j) のとき m_{i j} = 1 でそれ以外のとき m_{i j} = 0 となるような行列 M = [m_{i j} ] が対応し、σ に対応する置換行列と呼ばれる。

置換の組合せ論[編集]

組合せ論における n 元集合 S の置換は、S の元を（各元をちょうど一回ずつ）適当な順に並べたものである。これは厳密には、集合 {1, 2, …, n} から S への全単射を言う。S = {1, 2, …, n} のときには、群論的な定義と一致することに注意せよ。より一般に、集合 {1, 2, …, n} の代わりに、その元が全順序付けられた任意の集合を用いることができる。

S の全順序を用いないで定義できる置換の群論的解釈とも関係する組合せ論的性質の一つは、置換 σ の循環構造（英語版） (cycle structure) で、これは、σ　の循環の長さを記述する n の分割である。ここでは、σ の任意の不動点に対して分割の "1" の部分が存在する。不動点を持たない置換は完全順列 (derangement) と呼ばれる。

しかし、他の組合せ論的性質は S の順序やそれと置換とを関連付ける方法に直接的に関係している。

ascent, descent, run[編集]

n の置換 σ の ascent（上昇点^{[訳語疑問点]}）とは、次の値が現在のものよりも大きくなる、任意の位置 i (< n) を言う。つまり、σ = σ₁σ₂…σ_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 の置換の総数は、オイラー数 (組合せ論)（英語版） ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$ で与えられる。これは k 個の descent を持つ n の置換の総数にも等しい^[14]。

置換の ascending run（上昇列^{[訳語疑問点]}）とは、置換の空でない連続した増大部分列で、両端で延長できないものをいう。これは連続する ascent の極大列に対応する（後者は空でもよい。連続する二つの descent の間には、まだ長さ 1 の ascending run が存在する）。対照的に、置換の増大部分列は、連続しているものに限らない。これは与えられた置換から適当な位置の値を落として得られる元の増大列である。例えば、置換 2453167 は ascending run 245, 3, 167 を持ち、また増大部分列の1つは 2367 である。

置換が k − 1 個の descent を持つならば、それは k 個の ascending run の和でなければならない。従って、k 個の ascending run を持つ n の置換の総数は、k − 1 個の descent を持つ n の置換の総数 ${\displaystyle \textstyle \left\langle {n \atop k-1}\right\rangle }$ に等しい^[15]。

転倒[編集]

置換 σ の転倒とは、置換の成分が逆転する、即ち i < j かつ σ_i > σ_j となる位置の対 (i, j) を言う^[16]。故に 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 は解消する。別のところに descent ができるかもしれないが）。この操作によって転倒数は 1 減少する。転倒数が 0 でないならば、恒等置換でなく、したがって少なくとも一つの descent が存在する。バブルソートおよび挿入ソートはこの方法で列を正順にする特定の実例と解釈することができる。ついでながら、この方法で任意の置換 σ が基本互換の積に表せることが示せる。これにより、置換 σ は、それを表す互換の列を単に逆転させることで、恒等置換にすることができる。実は、σ を恒等置換にする基本互換の列を全て数え上げることにより（それを逆順にして）、σ の基本互換の積として表す長さ最短の表示を全て見つけることができる。

転倒数 k を持つ n の置換の総数はメイホン数によって表される^[17]。それは（X を q に置き換えて）q 階乗 [n]_q! と呼ばれる積

${\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^k の係数である。

関連項目[編集]

ポータル 数学

ウィキメディア・コモンズには、置換 (数学)に関連するカテゴリがあります。

注釈[編集]

参考文献[編集]

• 鈴木通夫『群論』 18巻、岩波書店〈現代数学〉、1977年。ISBN 978-4-00-730271-8。 
• 成嶋弘『数え上げ組合せ論入門』（改訂版）日本評論社〈日評数学選書〉、2003年。ISBN 4-535-60138-0。 
• Bóna, Miklós (2004). Combinatorics of Permutations. Chapman Hall-CRC. ISBN 1-58488-434-7 
• Bóna, Miklós (2012). Combinatorics of Permutations (Second ed.). CRC Press. doi:10.1201/b12210. ISBN 978-1-4398-5051-0. MR2919720. Zbl 1255.05001. https://books.google.com/books?id=Y3nRBQAAQBAJ 
• Kleiner, Israel (1986), “The evolution of group theory: A brief survey”, Math. Mag. 59: 195-215, doi:10.2307/2690312, MR0863090, Zbl 0608.01016 
• 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.
• Humphreys, J. F. (1996). A Course in Group Theory. Oxford University Press. ISBN 978-0-19-853459-4. MR1420410. Zbl 0843.20001. https://books.google.com/books?id=2jBqvVb0Q-AC