置換 (数学)

ウィキペディア

置換 (数学)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/09/06 04:05 UTC 版)

三種類の玉の置換、全六種

数学における置換（ちかん、英: 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-順列は本項に言う意味での置換となるが、それ以外の場合には順列の項へ譲る。

歴史

オーギュスタン＝ルイ・コーシー (1789–1857)

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次以上の代数方程式には解の公式が無い事を示した(アーベル–ルフィニの定理)。さらに代数的可解性を分析したガロアは、何が（一変数）多項式方程式の可解と不可解とを根本的に決めているのかを完全に記述するガロア理論に到達した。現代数学において、同様に問題の理解に際して関連するある種の置換を調べることになるという状況は多く存在している。

一般性

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

群論の文脈で

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

組合せ論の文脈で

多重集合上の置換

組合せ論において置換とは、有限集合の各元を一つずつ、かつ唯一つずつ用いて得られる列と理解するのが普通である。ここで、「列」の概念は「集合」の概念と異なり、列に現れる項は何らかの順序に従っていなければならない。つまり列は（それが空でなければ）「初項」を持ち、（長さが 2 より小さくなければ）第二項を持ち、といった具合に各項が順番に現れる。対照的に、集合の元に対しては順番の概念はなく、例えば {1, 2, 3} と {3, 2, 1} は表記が異なるだけで全く同じ集合を表す。この意味で、n 個の元からなる有限集合 S 上の置換は、各 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 上の置換の総数は多項係数

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

置換 (1 7 5)(2 4 8)(3 6) のグラフ。ここでは対応する軌道と巡回置換を同じ色で彩色している。

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

${\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}={\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}}$

置換の合成は、置換行列の積に対応する

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

集合 {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 の置換の総数は、オイラー数 (組合せ論) $\textstyle \left\langle {n \atop k}\right\rangle$

ポータル 数学

• 交代置換
• 組合せ論
• 畳み込み
• 輪環の順
• 巡回置換
• 置換の偶奇性
• Factorial number system
• Superpattern
• Josephus permutation
• レヴィ・チヴィタ記号
• 置換群
• Permutation pattern
• 置換多項式
• 対称群の置換表現
• ランダム置換
• Rencontres numbers
• Sorting network
• Substitution cipher
• 対称群
• 置換の弱順序
• 重複置換
• Heapのアルゴリズム

参考文献

• 鈴木通夫『群論』 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. MR 2919720. Zbl 1255.05001. https://books.google.co.jp/books?id=Y3nRBQAAQBAJ 
• Kleiner, Israel (1986), “The evolution of group theory: A brief survey”, Math. Mag. 59: 195-215, doi:10.2307/2690312, MR 0863090, 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. MR 1420410. Zbl 0843.20001. https://books.google.co.jp/books?id=2jBqvVb0Q-AC