置換 (数学)
数学における置換（ちかん、テンプレート:Lang-en-short）の概念は、いくつか僅かに異なった意味で用いられるけれども、何れも対象や値を「並べ替える」ことに関するものである。有り体に言えば、対象からなる集合の置換というのは、それらの対象に適当な順番を与えて並べることを言う。例えば、集合 {1, 2, 3} の置換は、
- (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
の全部で六種類ある順序組である。単語のアナグラムは、単語を構成する文字列に対する置換として定められる。そういった意味での置換の研究は、一般には組合せ論に属する話題である。
テンプレート:Anchor相異なる n-個の対象の置換の総数は テンプレート:Nowrap 通りであり、これは "n!" と書いて n の階乗と呼ばれる。
置換の概念は、多かれ少なかれ（あるいは陰に陽に）、数学のほとんどすべての領域に現れる。例えばある有限集合上に異なる順序付けが考えられる場合に、単にそれらの順番を無視したいとか、無視した時にどれほどの配置が同一視されるかを知る必要があるなどの理由で、置換が行われることも多い。同様の理由で、置換は計算機科学におけるソートアルゴリズムの研究において生じる。
代数学、特に群論において、集合 S 上の置換は S から自身への全単射、つまり写像 テンプレート:Nowrap で 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年ごろにラグランジュが多項式方程式の研究において、方程式の根の置換と方程式の可解性との関係を観察したことである。 個の方向性を著しく推し進めた結果が、ガロワの研究を経て、何が（一変数）多項式方程式の可解と不可解とを根本的に決めているかを完全に記述するガロワ理論に結実する。現代数学において、同様に問題の理解に際して関連するある種の置換を調べることになるという状況は多く存在している。
一般性
置換の概念を研究対象とする分野について挙げる。
群論の文脈で
群論とその周辺分野では、無限集合も含めた任意の集合上の置換を考えることができる。即ち、集合 S の置換とは、S から S 自身への全単射のことを言う。この場合、置換の積を定義して置換群の概念が得られる。集合 S が n-元からなる有限集合ならば、S 上の置換は n!-個存在する。
組合せ論の文脈で
組合せ論において置換は、有限集合の各元を一つずつ、かつ唯一つずつ用いて得られる列と理解するのが普通である。ここで、「列」の概念は「集合」の概念と異なり、列に現れる項は何らかの順序に従っていなければならない。つまり列は（それが空でなければ）「初項」を持ち、（長さが 2 より小さくなければ）第二項を持ち、といった具合に各項が順番に現れる。対照的に、集合の元は決まった順番を持たず、例えば {1, 2, 3} と {3, 2, 1} は見た目が異なるだけで全く同じ集合である。この意味で、n-個の元からなる有限集合 S 上の置換は、各 i を列の第 i-項へ写すものとみて {1, 2, …, n} から S への全単射である。あるいは、テンプレート:Nowrap は、列の中で x の後に y が現れるという意味でさだめて、S 上の一つの全順序を与えるものと見ることもできる。この意味での S の置換も、やはり n! 通り存在する。
置換の概念を少し弱めて「同じ元が二度は現れることがないが、与えられた集合の全ての元を使い切る必要はない」ものとした列を考えることが、初等組合せ論においてたびたびある。実際には、与えられた n 個の元からなる集合から、決められた長さ k の列を考えるという形で、この概念が用いられることが多い。これらの対象は、本項に言う置換の概念と区別するために、順列 (sequences without repetition) と呼ばれ、二項係数と深く関連する。
また、有限多重集合 M 上の置換は、重複順列とも呼ばれ、M の各元が、自身の M における重複度とちょうど同じ数だけ現れるような列である。M の各元の重複度が、（適当な順に）m1, m2, …, ml で、それらの和（つまり M の位数）が n であるとすると、M 上の置換の総数は多項係数
- <math>{n \choose m_1,m_2,\ldots,m_l} = \frac{n!}{m_1!\,m_2!\, \cdots\,m_l!}</math>
によって与えられる。
群論的取扱い
テンプレート:Main 群論においてある集合上の置換は、その集合からその集合自身の上への全単射を言う。任意に与えられた集合の上の置換全体の成す集合は、写像の合成を積として、恒等変換を単位元とする群を成し、これを S の対称群と呼ぶ。対称群は、同型を除いてその集合の濃度のみに依存して決まり、S の元の具体的な特徴がどうであるかは群構造に影響を与えない。対称群は有限集合上のものを考えるのが殆どで、この場合は適当な自然数 n に対して S = {1, 2, …,n} であるものとして一般性を失わない。こうして n-次の対称群 テンプレート:Math が定まる。
対称群の任意の部分群を置換群と呼ぶ。ケイリーの定理により、実は任意の群が何らかの置換群に同型であり、特に有限群は何らかの有限対称群に同型であることがわかる。しかし置換群は、抽象群よりも多くの構造を持つものであり、例えば置換群の任意の元には巡回置換型を定義することができるが、置換群として実現されたのではない群がこれと同値な付加構造をもつことは必ずしも求められない。例えば、テンプレート:Math は自然に置換群となり、その任意の互換は巡回型が (2,1) となるが、ケイリーの定理の証明に従って テンプレート:Math を テンプレート:Math の部分群として（つまり、テンプレート:Math 自身に属する全 6-個の元の置換として）実現すれば、この置換群での互換の巡回置換型は (2,2,2) になる。つまり、ケイリーの定理の成立にも拘らず、置換群の研究は抽象群の研究とは異なる部分を持っているということになる。
記法について
有限集合 S の置換に対して、その記法は大きく三種類が存在する。ケイリーによる二行記法は一行目に S の元を書き、その各元の下に置換による像を書いて二行目とするものである。例えば、集合 {1,2,3,4,5} のある置換は
- <math>\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix}</math> と書くことができて、これは σ が σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, σ(5) = 1 を満たすことを意味する。
この二行目だけを書くのが一行記法であり、先ほどの例であげた置換は一行記法だと 25431 で表される（成分が複数の文字、例えば二桁の数で表されるような場合には、成分の間にコンマを入れるのが典型的である）。
第三の記法としてテンプレート:仮リンクは、置換を続けて施す効果に焦点を当てたものになっている。これは、置換を（少なくとも二つの元を持つ）軌道に対応する巡回置換の積として表す方法である。相異なる軌道は互いに素（交わりを持たない）から、感覚的には「互いに素な巡回置換に分解する」方法とも言える。このような記法を得るには、以下のようにする。まず S の元 x を テンプレート:Nowrap なるようにとり、σ を繰り返し施して得られる像の列 (x σ(x) σ(σ(x)) …) を、像として x が現れるまで続ける。こうして書き下された値の集合は σ に関して x の属する軌道であり、得られた列はこの軌道に対応する σ の巡回置換成分の括弧書き記法になる。この後、既に書き下された軌道に属さない S の元 y があればそれを取って テンプレート:Nowrap であるならば、同様にして対応する巡回置換成分が得られるから、以下これを繰り返して、S の任意の元が何れかの巡回置換に属するかさもなくば σ の不動点となるまで続ける。この手続きにおいて、新しい巡回置換を作るための始点とする元の取り方は一通りとは限らないから、一つの置換に対する巡回置換表示は、一般には複数存在する。例えば、やはり先と同じ例で言えば
- <math>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix}=\begin{pmatrix}1 & 2 & 5 \end{pmatrix} \begin{pmatrix}3 & 4 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 5 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}5 & 1 & 2 \end{pmatrix}</math> のような表示が可能である。σ の各巡回置換成分 (x1 x2 … xl) はそれ自身が置換を表しており、具体的にはこの軌道上で σ と同じく テンプレート:Nowrap のとき 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 などの別な記号を宛がうのが通例である。
長さ 2 の巡回置換は互換と呼ばれ、二つの元をただ入れ替えるだけの置換である。
置換の積と逆置換
二つの置換の積は、それらの写像としての合成によって与えられる。つまり、σπ は与えられた集合の各元 x を σ(π(x)) へ写す。ここで注意すべきは、写像の記法に従って書いているため、一番右にある置換が最初に引数に適用されるということである。文献によっては、一番左の因子を最初に作用させる代わりに、置換をその引数の「右側」に書くものもある。例えば、冪記法を用いて、σ が x に作用することを xσ で書けば、積は xσπ = (xσ)π によって定められる。それでも、これらは置換の乗法に関して「異なる」規則を与えるものであるから、本項では写像の記法に従って一番右の因子から適用する流儀に従うものとする。
二つの全単射の合成は再び全単射を与えるから、二つの置換の積は再び置換を与える。写像の合成は結合的であるから、置換の積に関してもそうで、 (σπ)ρ = σ(πρ) が任意の置換に関して成立する。これにより、二つより多くの置換の積において、積の順番を表すグループ化の括弧を書かないのが普通である。また、中黒などの乗法を指し示す記号も、省略するのが通例である。
集合の各元をそれ自身に写す恒等置換は、この置換の積に関する単位元である。二行記法で言えば、この単位元は
- <math>\begin{pmatrix}1 & 2 & 3 & \cdots & n \\ 1 & 2 & 3 & \cdots & n\end{pmatrix}</math>
である。
全単射は逆写像を持つから、置換もそうで、σ の逆元 σ−1 は再び置換になる。陽に書けば、σ(x) = y なる限り σ−1(y) = x が成り立つ。二行記法で逆置換を得るには、二つの行を入れ替えればよい（必要なら入れ替えた後列を並べ替えて一行目が与えられた順番になるようにする）。例えば、
- <math>\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix}^{-1}
=\begin{pmatrix}2 & 5 & 4 & 3 & 1\\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}
=\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2\end{pmatrix}</math>
である。巡回置換表示で逆置換を得るには、現れる巡回置換において元を逆順に並べなおせば、それがそのまま逆置換の巡回置換表示になる。
積が結合的で、単位元を持ち、任意の元が逆元を持つということから、S 上の置換全体の成す集合は群となり、S の対称群と呼ばれる。
有限集合上の二にの置換は互換の積に表すことができる。さらに言えば、与えられた置換に対してそのような表示は無数に存在するけれども、それら無数の表示の中に奇数個の互換を持つ表示と偶数個の互換を持つ表示とを両方とも持つような置換は存在しない。即ち、任意の置換はこのような表示に現れる互換の数の偶奇性により、偶か奇かに分類することができる。
置換の乗法を巡回置換記法のもとで書くための平易なパターンというものは存在せず、積の巡回置換表示に現れる巡回置換は、積を取る個々の置換に現れる巡回置換とは全く異なるものになってしまう。しかし、置換 σ に対して別の置換 π による共軛変換を取る、つまり積 πσπ−1 を作る特別の場合においては、巡回置換構造が保たれる。共軛変換で得られた置換の巡回置換表示は、σ の巡回置換表示に現れる各成分に π を施したものとして与えられる[2]。
集合 {1, 2, …, n} 上の置換を n-次正方行列として表すこともできる。これを行うのに自然な方法は二種類あるが、行列の積が置換の積に同じ順番で対応するのはそのうちの一方だけである。このとき、置換 σ には i = σ(j) のとき mij = 1 でそれ以外のとき mij = 0 となるような行列 M = (mij) が対応し、σ に対応する置換行列と呼ばれる。
置換の組合せ論
組合せ論における 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) を言う。つまり、σ = σ1σ2…σ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 の置換の総数は、テンプレート:仮リンク <math>\textstyle\left\langle{n\atop k}\right\rangle</math> で与えられる。これは k-個の descent を持つ n の置換の総数にも等しい[3]。
置換の ascending run（テンプレート:訳語疑問点範囲）とは、テンプレート:訳語疑問点範囲。これは連続する ascent の極大列に対応する（後者は空でもよい。二つの連続する ascent の間には、まだ長さ 1 の ascending run が存在する）。対照的に、置換の増大部分列は、隣接的でなくともよい。これは与えられた置換の適当な位置の値を落とす (omit) ことで得られる元の列である。例えば、置換 2453167 は ascending run 245, 3, 167 を持ち、また増大部分列 2367 を持つ。
置換が k − 1 個の descent を持つならば、それは k-個の ascending run の和でなければならない。従って、k-個の ascending run を持つ n の置換の総数は、k − 1 個の descent を持つ n の置換の総数 <math>\textstyle\left\langle{n\atop k-1}\right\rangle</math> に等しい[4]。
転倒
置換 σ の転倒とは、置換の成分が逆転する、即ち i < j かつ σi > σj となるような位置の対 (i, j) を言う[5]。故に descent とは、二つの隣接する位置における転倒に他ならない。例えば、置換 σ = 23154 は三つの転倒 (1,3), (2,3), (4,5) をそれぞれ成分の対 (2,1), (3,1), (5,4) において持つ。
転倒数 k を持つ n の置換の総数はメイホン数によって表される[6]。それは（X を q に置き換えて）q-階乗 テンプレート:Math と呼ばれる積
- <math>\prod_{m=1}^n\sum_{i=0}^{m-1}X^i=1(1+X)(1+X+X^2)\cdots(1+X+X^2+\cdots+X^{n-1})</math>
の展開における Xk の係数である。
関連項目
注釈
参考文献
- Miklós Bóna. "Combinatorics of Permutations", Chapman Hall-CRC, 2004. ISBN 1-58488-434-7.
- Donald Knuth. The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing. Addison-Wesley, 2005. ISBN 0-201-85393-0.
- Donald Knuth. 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.. A course in group theory. Oxford University Press, 1996. ISBN 978-0-19-853459-4
