置換 (数学)のソースを表示

{{otheruses|置換|初等組合せ論におけるpermutation|順列}}
{{see also|対称群}}
[[File:Permutations RGB.svg|thumb|150px|三種類の玉の置換、全六種]]
[[数学]]における'''置換'''（ちかん、{{lang-en-short|''permutation''}}）の概念は、いくつか僅かに異なった意味で用いられるが、いずれも対象や値を「並べ替える」ことに関するものである。有り体に言えば、対象からなる集合の置換というのは、それらの対象に適当な順番を与えて並べることを言う。例えば、集合 {1, 2, 3} の置換は、
: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
の全部で六種類ある[[タプル|順序組]]である。単語の[[アナグラム]]は、単語を構成する文字列に対する置換として定められる。そういった意味での置換の研究は、一般には[[組合せ論]]に属する話題である。  

相異なる ''n'' 個の対象の置換の総数は {{nowrap|''n''×(''n'' − 1)×(''n'' − 2)×...×2×1}} 通りであり、これは "''n''!" と書いて ''n'' の[[階乗]]と呼ばれる。

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

[[代数学]]、特に[[群論]]において、[[集合]] ''S'' 上の置換は ''S'' から自身への[[全単射]]（つまり写像 {{nowrap|''S'' → ''S''}} で ''S'' の各元が像としてちょうど一つずつ現れるもの）として定義される。これは各元 ''s'' を対応する ''f''(''s'') と入れ替えるという意味での ''S'' の並び替え (rearrangement) と関連する。このような置換の全体は[[対称群]]と呼ばれる[[群 (数学)|群]]を成す。重要なことは、置換の[[写像の合成|合成]]が定義できること、つまり二つの並び替えを続けて行うと、それは全体として別の並べ替えになっているということである。''S'' 上の置換は、''S'' の元（あるいはそれを特定の記号によって置き換えたもの）を対象として、それらに対象の並び替えとして[[群作用|作用する]]。

初等組合せ論において、「{{仮リンク|label=順列と置換|12種の数え上げ問題|en|Twelvefold way}}」はともに ''n'' 元集合から ''k'' 個の元を取り出す方法として可能なものを数え上げる問題に関するもので、取り出す順番を勘案するのが ''k''-順列、順番を無視するのが ''k''-組合せである。''k'' = ''n'' の場合には、''k''-順列は本項に言う意味での置換となるが、それ以外の場合には[[順列]]の項へ譲る。

== 歴史 ==
[[File:Augustin Louis Cauchy.jpg|thumb|150px|[[オーギュスタン＝ルイ・コーシー]] (1789–1857)]]
''n'' 個の要素の置換の総数を決定する規則は少なくとも1150年ごろにはヒンズー文化において知られていた。インドの数学者[[バースカラ2世]]による著書に
<blockquote>
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.<ref>N. L. Biggs, ''The roots of combinatorics'', Historia Math. 6 (1979) 109−136</ref>
</blockquote>
と訳せる一節が含まれる。

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

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

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

=== 組合せ論の文脈で ===
[[File:Permutations with repetition.svg|thumb|多重集合上の置換]]
[[組合せ論]]において'''置換'''とは、有限集合の各元を一つずつ、かつ唯一つずつ用いて得られる[[列 (数学)|列]]と理解するのが普通である{{sfn|Bóna|2012|p={{google books quote|id=Y3nRBQAAQBAJ|page=1|1}}|loc=Definition 0.1}}。ここで、「列」の概念は「集合」の概念と異なり、列に現れる項は何らかの順序に従っていなければならない。つまり列は（それが空でなければ）「初項」を持ち、（長さが 2 より小さくなければ）第二項を持ち、といった具合に各項が順番に現れる。対照的に、集合の元は決まった順番を持たず、例えば {1, 2, 3} と {3, 2, 1} は見た目が異なるだけで全く同じ集合である。この意味で、''n'' 個の元からなる有限集合 ''S'' 上の置換は、各 ''i'' を列の第 ''i'' 項へ写すものとみて {1, 2, …, ''n''} から ''S'' への[[全単射]]である。あるいは、{{nowrap|''x'' &lt; ''y''}} は、列の中で ''x'' の後に ''y'' が現れるという意味でさだめて、''S'' 上の一つの[[全順序]]を与えるものと見ることもできる。この意味での ''S'' の置換も、やはり ''n''! 通り存在する。

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

また、有限[[多重集合]] ''M'' 上の置換は、[[重複置換]]とも呼ばれ、''M'' の各元が、自身の ''M'' における重複度とちょうど同じ数だけ現れるような列である。''M'' の各元の重複度が、（適当な順に）''m''<sub>1</sub>, ''m''<sub>2</sub>, …, ''m''<sub>''l''</sub> で、それらの和（つまり ''M'' の位数）が ''n'' であるとすると、''M'' 上の置換の総数は[[多項係数]]
: <math>{n \choose m_1,m_2,\ldots,m_l} = \frac{n!}{m_1!\,m_2!\, \cdots\,m_l!}</math>
によって与えられる。

== 群論的取扱い ==
{{Main|対称群}}
群論においてある集合上の'''置換'''は、その集合からその集合自身の上への[[全単射]]を言う{{sfn|鈴木|1977|p=53|loc=定義 7.1}}。任意に与えられた集合の上の置換全体の成す集合は、[[写像の合成]]を積として、[[恒等変換]]を単位元とする[[群 (数学)|群]]を成し、これを ''S'' の'''[[対称群]]'''と呼ぶ{{sfn|鈴木|1977|p=54}}。対称群は、[[同型を除いて]]その集合の[[濃度 (数学)|濃度]]のみに依存して決まり、''S'' の元の具体的な特徴がどうであるかは群構造に影響を与えない{{sfn|鈴木|1977|p=54|loc=(7.2)}}。対称群は有限集合上のものを考えることがほとんどで、この場合には適当な自然数 ''n'' に対して ''S'' = {1, 2, …,''n''} であるとして[[一般性を失わない]]。こうして ''n'' 次の対称群 {{math|&Sigma;<sub>''n''</sub>}} が定まる。 

対称群の任意の部分群を'''[[置換群]]'''と呼ぶ{{sfn|鈴木|1977|p=55|loc=定義 7.3}}。[[ケイリーの定理]]により、実は任意の群が何らかの置換群に同型であり{{sfn|鈴木|1977|p=55|loc=(7.4)}}、特に有限群は何らかの有限対称群の部分群に同型であることがわかる。しかし置換群は、抽象群よりも多くの構造を持つものであり、たとえば置換群の任意の元には[[巡回置換型]]を定義することができるが、置換群として実現されたのではない群がこれと同値な付加構造をもつことは必ずしも求められない。例えば、{{math|&Sigma;<sub>3</sub>}} は自然に置換群となり、その任意の互換は巡回型が (2,1) となるが、ケイリーの定理の証明に従って {{math|&Sigma;<sub>3</sub>}} を {{math|&Sigma;<sub>6</sub>}} の部分群として（つまり、{{math|&Sigma;<sub>3</sub>}} 自身に属する全 6 個の元の置換として）実現すれば、この置換群での互換の巡回置換型は (2, 2, 2) になる。つまり、ケイリーの定理の成立にも拘らず、置換群の研究は抽象群の研究とは異なる部分を持っているということになる。

=== 記法について === 
有限集合 ''S'' の置換に対して、その記法は大きく三種類が存在する。[[1815年]]、[[オーギュスタン＝ルイ・コーシー|コーシー]]によって導入された{{sfn|Kleiner|1986|p=202}}{{訳語疑問点範囲|'''二行記法'''|date=2018-04-01}}は一行目に ''S'' の元を書き、その各元の下に置換による像を書いて二行目とするものである。例えば、集合 {1, 2, 3, 4, 5} のある置換は
: <math>\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix}</math>
と書くことができ、上と下の対応が同じなら横の順序は問わない記法である。
: <math>\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix}=\begin{pmatrix}
2 & 4 & 5 & 1 & 3 \\
5 & 3 & 1 & 2 & 4\end{pmatrix}=\begin{pmatrix}
5 & 4 & 3 & 2 & 1 \\
1 & 3 & 4 & 5 & 2\end{pmatrix}=\cdots
</math>

[[1852年]]、[[エンリコ・ベッチ]]はこれを
: <math>\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
\sigma(1) & \sigma(2) & \sigma(3) & \sigma(4) & \sigma(5)\end{pmatrix}</math>
のような対応関係と見て ''σ'' は ''σ''(1) = 2, ''σ''(2) = 5, ''σ''(3) = 4, ''σ''(4) = 3,  ''σ''(5) = 1 を満たす写像とした。

コーシーの流儀では有理式 ''F''(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>, ''x''<sub>4</sub>, ''x''<sub>5</sub>) の置換を
: <math>F(x_1,x_2,x_3,x_4,x_5)\sigma=F(x_1,x_2,x_3,x_4,x_5)\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
2 & 5 & 4 & 3 & 1\end{pmatrix}=F(x_2,x_5,x_4,x_3,x_1)</math>
のように記述し、さらに別の置換''τ''を行った時も右から作用させて
: <math>\{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)</math>
としたため ''σ'' の後に ''τ'' を行う置換を ''στ'' で表すようになった。

一方でベッチの流儀を使う場合は[[写像#合成|合成写像]]として
: <math>\tau(\sigma(1)) = (\tau \circ \sigma)(1)</math>
のように書き、時によって合成の記号「∘ 」を省略し ''σ'' の後に ''τ'' を行う置換を ''τσ'' で表した。一般に置換は交換可能ではないので置換の順序には注意が必要である。

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

[[File:Permutation cycles qtl1.svg|thumb|200px|置換 {{font color|lightblue|(1 7 5)}}{{font color|palegreen|(2 4 8)}}{{font color|pink|(3 6)}} のグラフ{{sfn|成嶋|2003|p=88}}。ここでは対応する軌道と巡回置換を同じ色で彩色している。]]
第三の記法として置換の'''{{仮リンク|巡回置換表現|en|Cycle notation}}'''{{sfn|成嶋|2003|p=145}}は、置換を続けて施す効果に焦点を当てたものになっている。これは、置換を（少なくとも二つの元を持つ）[[軌道 (群論)|軌道]]に対応する[[巡回置換]]の積として表す方法である。相異なる軌道は[[素集合|互いに素]]（交わりを持たない）から、感覚的には「互いに素な巡回置換に分解する」方法とも言える。このような記法を得るには、以下のようにする。まず ''S'' の元 ''x'' を {{nowrap|σ(''x'') ≠ ''x''}} なるようにとり、σ を繰り返し施して得られる像の列  (''x'' σ(''x'') σ(σ(''x'')) …) を、像として ''x'' が現れるまで続ける。こうして書き下された値の集合は σ に関して ''x'' の属する軌道であり、得られた列はこの軌道に対応する σ の巡回置換成分の括弧書き記法になる。この後、既に書き下された軌道に属さない ''S'' の元 ''y'' があればそれを取って {{nowrap|''σ''(''y'') ≠ ''y''}} であるならば、同様にして対応する巡回置換成分が得られるから、以下これを繰り返して、''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>
のような表示が可能である。σ の各巡回置換成分 (''x''<sub>1</sub> ''x''<sub>2</sub> … ''x''<sub>''l''</sub>) はそれ自身が置換を表しており、具体的にはこの軌道上で σ と同じく {{nowrap|''i'' &lt; ''l''}} のとき ''x''<sub>''i''</sub> を ''x''<sub>''i''+1</sub> に写し、''x''<sub>''l''</sub> を ''x''<sub>1</sub>) に写す一方、この軌道に属さない ''S'' の元は何れも動かさない。位数が ''l'' であるような軌道は、長さ ''l'' の巡回置換と呼ばれる。σ　の相異なる軌道は定義により交わりを持たないから、それらに対応する巡回置換が[[交換法則|可換]]であることは容易に分かり、σ はそれらの巡回置換の（施す順番を問わない）積に表される。従って、置換の巡回置換表現に現れる巡回置換の連結は置換の合成として解釈できるので、それを以って置換の「分解」と称する。分解に現れる巡回置換の順番を並べ替える以外に、σ を互いに疎な軌道を持つ巡回置換（σ と無関係な巡回置換も含めて）の積に書く方法はないので、そういう意味で巡回置換分解は一意的である。置換の巡回置換表現が一意的でない部分として、個々の巡回置換の表し方が一通りでないことが挙げられる。例えば上の例でも (5 1 2) は (1 2 5) と書いても同じ（だが (5 2 1) は異なる置換）である。

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

長さ 2 の巡回置換は[[互換 (数学)|'''互換''']]と呼ばれ{{sfn|鈴木|1977|pp=284–285|loc=定義 2.5}}、二つの元をただ入れ替えるだけの置換である。

=== 置換の積と逆置換 ===
{{Main|対称群}}

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

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

集合の各元をそれ自身に写す恒等置換は、この置換の積に関する単位元である。二行記法で言えば、この単位元は
:<math>\begin{pmatrix}1 & 2 & 3 & \cdots & n \\ 1 & 2 & 3 & \cdots & n\end{pmatrix}</math>
である。

[[全単射]]は[[逆写像]]を持つから、置換もそうで、σ の逆元 σ<sup>−1</sup> は再び置換になる。陽に書けば、σ(''x'') = ''y'' なる限り σ<sup>−1</sup>(''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'' の対称群と呼ばれる。

有限集合上の任意の置換は互換の積に表すことができる{{sfn|鈴木|1977|p=285|loc=(2.6)}}。与えられた置換に対してそのような表示は無数に存在するけれども、それらの表示の中に現れる互換の数の偶奇は表示によらない{{sfn|鈴木|1977|p=285|loc=(2.6)}}。これにより、任意の置換は[[置換の偶奇性|'''偶置換'''または'''奇置換''']]に分類することができる。

[[File:Symmetric group 3; Cayley table; matrices.svg|thumb|置換の合成は、置換行列の積に対応する]]
置換の乗法を置換の巡回置換表現のもとで書くための平易なパターンというものは存在せず、積の巡回置換表示に現れる巡回置換は、積を取る個々の置換に現れる巡回置換とは全く異なるものになってしまう。しかし、置換 σ に対して別の置換 π による[[共軛 (群論)|共軛変換]]を取る、つまり積 πσπ<sup>−1</sup> を作る特別の場合においては、巡回置換構造が保たれる。共軛変換で得られた置換の巡回置換表示は、σ の巡回置換表示に現れる各成分に π を施したものとして与えられる{{sfn|Humphreys|1996|p={{Google books quote|id=2jBqvVb0Q-AC|page=84|text=conjugate permutations have the same cycle type|84}}}}。

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

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

''S'' の全順序を用いないで定義できる置換の群論的解釈とも関係する組合せ論的性質の一つは、置換 σ の{{仮リンク|循環と不動点|en|cycles and fixed points|label=循環構造}} (cycle structure) で、これは、σ　の循環の長さを記述する ''n'' の[[自然数の分割|分割]]である。ここでは、σ の任意の不動点に対して分割の "1" の部分が存在する。不動点を持たない置換は[[完全順列]] (derangement) と呼ばれる。

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

=== ascent, descent, run ===
''n'' の置換 σ の ''ascent''（{{訳語疑問点範囲|上昇点|date=2012年9月}}）とは、次の値が現在のものよりも大きくなる、任意の位置 ''i'' (&lt; ''n'') を言う。つまり、σ = σ<sub>1</sub>σ<sub>2</sub>…σ<sub>''n''</sub> のとき、''i'' が ascent であるとは σ<sub>''i''</sub> &lt; σ<sub>''i''+1</sub> となることを言う。

例えば、置換 3452167 は 1, 2, 5, 6 番目の位置に ascent を持つ。

同様に ''descent''（{{訳語疑問点範囲|下降点|date=2012年9月}}）は σ<sub>''i''</sub> &gt; σ<sub>''i''+1</sub> となる位置 ''i'' (&lt; ''n'') を言う。従って、1 &le; ''i'' &lt; ''n'' なる任意の ''i'' は、σ の ascent であるか descent であるかの何れかになる。

''k'' 個の ascent を持つ ''n'' の置換の総数は、{{仮リンク|オイラー数 (組合せ論)|en|Eulerian number}} <math>\textstyle\left\langle{n\atop k}\right\rangle</math> で与えられる。これは ''k'' 個の descent を持つ ''n'' の置換の総数にも等しい{{sfn|Bóna|2004|p=3}}。

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

置換が ''k'' &minus; 1 個の descent を持つならば、それは ''k'' 個の ascending run の和でなければならない。従って、''k'' 個の ascending run を持つ ''n'' の置換の総数は、''k'' &minus; 1 個の descent を持つ ''n'' の置換の総数 <math>\textstyle\left\langle{n\atop k-1}\right\rangle</math> に等しい{{sfn|Bóna|2012|pp={{google books quote|id=Y3nRBQAAQBAJ|page=4|4}}f}}。

=== 転倒 ===
{{main|転倒 (数学)}}

置換 σ の'''転倒'''とは、置換の成分が逆転する、即ち ''i'' &lt; ''j'' かつ &sigma;<sub>''i''</sub> &gt; &sigma;<sub>''j''</sub> となるような位置の対 (''i'', ''j'') を言う{{sfn|Bóna|2012|p={{google books quote|id=Y3nRBQAAQBAJ|page=53|53}}|loc=Definition 2.1}}。故に descent とは、二つの隣接する位置における転倒に他ならない。例えば、置換 σ = 23154 は三つの転倒 (1,3), (2,3), (4,5) をそれぞれ成分の対 (2,1), (3,1), (5,4) において持つ。

{{訳語疑問点範囲|あるいは転倒を、順番が逆になる値の対 (σ<sub>''i''</sub>, σ<sub>''j''</sub>) と定める場合もある。こうしても転倒の数（[[転倒数]]）は変化しないし、この逆順にされた対は逆置換 σ<sup>−1</sup> の上で述べた意味での逆転になる。転倒数は置換の成分がどれほど入れ違いになっているかの度合いを表す重要な測度であり、σ と σ<sup>−1</sup> とでは転倒数は同じになる。''k'' 個の転倒を持つ置換を正順にする（恒等置換に変換する）ために、[[基本互換]]（隣接互換）を続けて（右乗によって）適用する方法が常に可能で、そのような操作を ''k'' 個並べた列が必要になる。さらに言えば、基本互換をうまく選ぶ方法があって、それには各段階において ''i'' がその置換の descent のときに ''i'' と {{nowrap|''i'' + 1}} とを入れ替えて、''i'' が descent でないようにすれば十分である（この操作で目当ての descent は解消しても、別のところに descent ができるかもしれない）。この操作によって転倒数は 1 減少するから、それで転倒数が 0 になったときにそれが恒等置換でないならば、少なくとも一つの descent が存在することに注意する。[[バブルソート]]および[[挿入ソート]]はこの方法で列を正順にする特定の実例と解釈することができる。ついでながら、この方法で任意の置換 σ が基本互換の積に表せることが示せる。これにより、置換 σ は、それを表す互換の列を単に逆転させることで、恒等置換にすることができる。実は、σ を恒等置換にする基本互換の列を全て数え上げることにより（それを逆順にして）、σ の基本互換の積として表す長さ最短の表示を全て見つけることができる。|date=2012年9月}}

転倒数 ''k'' を持つ ''n'' の置換の総数はメイホン数によって表される{{sfn|Bóna|2004|pp=43ff}}。それは（''X'' を ''q'' に置き換えて）[[q階乗|''q'' 階乗]] {{math|[''n'']<sub>''q''</sub>!}} と呼ばれる積
:<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>
の展開における ''X''<sup>''k''</sup> の係数である。

== 関連項目 ==
{{Portal|数学}}
{{Commons category|Permutations}}
<div style="column-count:3;">
* {{仮リンク|交代置換|en|Alternating permutation}}
* [[組合せ論]]
* [[畳み込み]]
* {{仮リンク|輪環の順|en|Cyclic order}}
* {{仮リンク|巡回置換|en|Cycle (mathematics)}}
* [[置換の符号|置換の偶奇性]]
*[[Factorial number system]]
*[[Superpattern]]
*[[Josephus permutation]]
* [[レヴィ・チヴィタ記号]]
* [[置換群]]
*[[Permutation pattern]]
* [[置換多項式]]
* {{仮リンク|対称群の表現論|label=対称群の置換表現|en|Permutation representation (symmetric group)}}
* {{仮リンク|ランダム置換|en|Random permutation}}
*[[Rencontres numbers]]
*[[Sorting network]]
*[[Substitution cipher]]
* [[対称群]]
* {{仮リンク|置換の弱順序|en|Weak order of permutations}}
</div>

== 注釈 ==
{{Reflist|2}}

== 参考文献 ==
* {{cite book
    |和書
    |last1              = 鈴木
    |first1             = 通夫
    |authorlink1        = 鈴木通夫
    |year               = 1977
    |title              = 群論
    |series             = 現代数学
    |volume             = 18
    |publisher          = 岩波書店
    |isbn               = 978-4-00-730271-8
    |ref                = harv
}}
* {{cite book
    |和書
    |last1              = 成嶋
    |first1             = 弘
    |year               = 2003
    |title              = 数え上げ組合せ論入門
    |edition            = 改訂版
    |series             = 日評数学選書
    |publisher          = [[日本評論社]]
    |isbn               = 4-535-60138-0
    |ref                = harv
}}
<!-- I'll promote this to references if I add another section to the main text. ~~~~ -->
* {{cite book
    |last1              = Bóna
    |first1             = Miklós
    |year               = 2004
    |title              = Combinatorics of Permutations
    |publisher          = Chapman Hall-CRC
    |isbn               = 1-58488-434-7
    |mr                 = 
    |zbl                = 
    |doi                = 
    |ref                = harv
}}
* {{cite book
    |last1              = Bóna
    |first1             = Miklós
    |year               = 2012
    |title              = Combinatorics of Permutations
    |edition            = Second
    |url                = {{google books|Y3nRBQAAQBAJ|plainurl=yes}}
    |publisher          = CRC Press
    |isbn               = 978-1-4398-5051-0
    |mr                 = 2919720
    |zbl                = 1255.05001
    |doi                = 10.1201/b12210
    |ref                = harv
}}
* {{citation
    |last1              = Kleiner
    |first1             = Israel
    |year               = 1986
    |title              = The evolution of group theory: A brief survey
    |journal            = Math. Mag.
    |volume             = 59
    |pages              = 195–215
    |mr                 = 0863090
    |zbl                = 0608.01016
    |doi                = 10.2307/2690312
}}
* [[Donald Knuth|Knuth, Donald]]. ''The Art of Computer Programming'', Volume&nbsp;4: ''Generating All Tuples and Permutations'', Fascicle&nbsp;2, first printing.  Addison-Wesley, 2005. ISBN 0-201-85393-0.
* Knuth, Donald. ''The Art of Computer Programming'', Volume&nbsp;3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.&nbsp;11–72.
* {{cite book
    |last1              = Humphreys
    |first1             = J. F.
    |year               = 1996
    |title              = A Course in Group Theory
    |url                = {{google books|2jBqvVb0Q-AC|plainurl=yes}}
    |publisher          = [[Oxford University Press]]
    |isbn               = 978-0-19-853459-4
    |mr                 = 1420410
    |zbl                = 0843.20001
    |ref                = harv
}}

{{DEFAULTSORT:ちかん}}
[[Category:抽象代数学]]
[[Category:組合せ論]]
[[Category:置換|*]]
[[Category:数学に関する記事]]