巡回順列

固定要素を持たない（数学的な）順列の種類

数学、特に群論において、巡回置換（しゅこうかんけい、英: cyclic permutation）は、単一のサイクルからなる置換である。 ^{[1] [2]巡回置換は}サイクルと呼ばれることもある。^[3]巡回置換にk個の要素がある場合、 kサイクルと呼ばれることもある。一部の研究者はこの定義を拡張し、最大で 1 つの非自明なサイクルに加えて、固定点を持つ置換も含める。^{[3] [4]}サイクル記法では、巡回置換は、要素を置換順に括弧で囲んで並べたリストで表される。

例えば、1を3に、3を2に、2を4に、4を1に送る順列(1 3 2 4)は4巡回順列であり、1を3に、3を2に、2を1に、4を4に送る順列(1 3 2)(4)は、一部の研究者によって3巡回順列とみなされている。一方、1を3に、3を1に、2を4に、4を2に送る順列(1 3)(2 4)は、{1, 3}と{2, 4}のペアをそれぞれ個別に順列化するため、巡回順列ではない。

巡回置換のより広い定義において、固定点を許容する場合、これらの固定点はそれぞれ置換の自明な軌道を構成し、残りのすべての点を含む単一の非自明な軌道が存在する。これは定義として次のように用いることができる。巡回置換（固定点を許容する）とは、単一の非自明な軌道を持つ置換である。有限個の元を持つすべての置換は、非自明な軌道が互いに素である巡回置換に分解することができる。^[5]

順列の個々の巡回部分はサイクルとも呼ばれ、したがって 2 番目の例は 3 サイクルと 1 サイクル (または固定点) で構成され、3 番目の例は 2 サイクルが 2 つで構成されます。

意味

1 つの 8 サイクルで構成される巡回順列。

巡回置換の正確な定義については、広く合意されているわけではない。一部の研究者は、集合Xの置換 σが巡回的であるとは、「置換された集合の各対象を、他の全ての対象の位置を順に通過させる」と定義している^[1]。あるいは、同義語として、巡回記法による表現が単一の巡回からなる場合と定義している^[2] 。一方、固定点を許容するより寛容な定義を提示する研究者もいる^{[3] [4]。}

Xの空でない部分集合Sが の閉路であるとは、 Sへの制約がSの巡回置換となる場合である。Xが有限である場合、その閉路は互いに素であり、それらの和はXとなる。つまり、それらはの閉路分解と呼ばれる分割を形成する。したがって、より寛容な定義によれば、 Xの置換が巡回的であるためには、 X がその唯一の閉路となる必要がある。 ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma .}$

例えば、順列は、循環記法と2行記法（2通り）で次のように 書かれる。

${\displaystyle {\begin{aligned}(1\ 4\ 6\ &8\ 3\ 7)(2)(5)\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}}$

6サイクルが1つと1サイクルが2つあり、そのサイクル図は右に示されています。この順列を循環的と考える著者もいれば、そうでないと考える著者もいます。

拡大定義では巡回するが制限定義では巡回しない順列で、固定点が2つ（1巡回）あり、6巡回がある。

定義が拡大されると、単一のサイクルから構成されない循環順列が存在します。

より正式には、拡大定義において、集合Xの順列を全単射関数として捉えた場合、によって生成される部分群のXへの作用が、複数の元を持つ軌道を最大で1つしか持たないとき、それはサイクルと呼ばれる。^{[6]この概念は、} X が有限集合である場合に最もよく用いられる。その場合、最大の軌道Sも有限となる。Sの任意の元を とし、任意の に対してとする。S が有限である場合、となる最小の数が存在する。すると、 であり、は によって定義される順列である。 ${\displaystyle \sigma }$ ${\displaystyle \sigma :X\to X}$ ${\displaystyle \sigma }$ ${\displaystyle s_{0}}$ ${\displaystyle s_{i}=\sigma ^{i}(s_{0})}$ ${\displaystyle i\in \mathbf {Z} }$ ${\displaystyle k\geq 1}$ ${\displaystyle s_{k}=s_{0}}$ ${\displaystyle S=\{s_{0},s_{1},\ldots ,s_{k-1}\}}$ ${\displaystyle \sigma }$

${\displaystyle \sigma (s_{i})=s_{i+1}}$0 ≤ i < kの場合

の任意の元に対しては、 となる。 によって固定されない元は、 ${\displaystyle \sigma (x)=x}$ ${\displaystyle X\setminus S}$ ${\displaystyle \sigma }$

${\displaystyle s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}}$。

巡回順列は、コンパクトサイクル記法を用いて表すことができます（この記法では、 k組との混同を避けるため、要素間にコンマは入れません）。サイクルの長さは、その最大軌道の要素数です。長さkのサイクルは、 kサイクルとも呼ばれます。 ${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$

1-サイクルの軌道は順列の不動点と呼ばれるが、順列として考えるとすべての1-サイクルは恒等順列となる。^[7]サイクル表記法を用いる場合、混乱が生じないときは1-サイクルは省略されることが多い。^[8]

基本的なプロパティ

対称群に関する基本的な結果の1つは、任意の置換は互いに素なサイクル（より正確には、互いに素な軌道を持つサイクル）の積として表現できることである。このようなサイクルは互いに交換可能であり、置換の表現はサイクルの順序を除いて一意である。^[a]したがって、この表現におけるサイクルの長さの多重集合（サイクル型）は、置換によって一意に決定され、対称群における置換の符号と共役類は両方ともそれによって決定される。^[9]

対称群Snのkサイクルの_数は、に対して、次の同値な式で与えられます。 ${\displaystyle 1\leq k\leq n}$ $${\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(n-k)!k}}.}$$

kサイクルのシグネチャは( −1 ) ^{k  − 1}です。

サイクルの逆は、要素の順序を逆にすることで与えられます。特に、 であるため、すべての2サイクルはそれ自身の逆です。互いに素なサイクルは可換であるため、互いに素なサイクルの積の逆は、それぞれのサイクルを個別に逆順にした結果です。 ${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$ ${\displaystyle \sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})}$ ${\displaystyle (a~b)=(b~a)}$

転置

マトリックスの ${\displaystyle \pi }$

2つの要素のみを持つ循環は転置と呼ばれます。例えば、2と4を入れ替える順列は2循環なので、 と書くことができます。 ${\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}}$ ${\displaystyle \pi =(2\ 4)}$

プロパティ

任意の順列は転置の合成（積）として表現できる。正式には、転置は群の生成元である。^[10]実際、転置される集合が{1, 2, ..., n }であるとき、任意の順列は隣接する転置 など。これは、任意の転置が隣接する転置の積として表せることから導かれます。具体的には、 kをlに1ステップずつ移動し、その後lをkがあった場所に戻すのようこの転置は、kとlを入れ替えるだけで、他に変化はありません。 ${\displaystyle (1~2),(2~3),(3~4),}$ ${\displaystyle (k~~l)}$ ${\displaystyle k<l}$

${\displaystyle (k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).}$

順列を転置の積に分解するには、例えば、順列を互いに素な閉路の積として書き、長さが 3 以上の閉路をそれぞれ転置と長さが 1 短い閉路の積に繰り返し分割します。

${\displaystyle (a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).}$

これは、最初の要求が から へ、そして最終的に へ移動することであることを意味します。代わりに、右因子を最初に実行することで、要素を現在の位置に保ちながらロールすることができます（演算子表記では通常どおり、また「順列」の記事の慣例に従います）。これはの位置に移動しているので、最初の順列の後、要素とはまだ最終位置に到達していません。その後に実行される転置は、のインデックスによってアドレスを移動し、最初に と であったものを交換します。 ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle b}$ ${\displaystyle c,}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle z}$ ${\displaystyle a.}$ ${\displaystyle a}$ ${\displaystyle z}$ ${\displaystyle b,}$ ${\displaystyle a}$ ${\displaystyle z}$ ${\displaystyle (a~b),}$ ${\displaystyle z}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle z.}$

実際、対称群はコクセター群であり、つまり、順序 2 の要素 (隣接転置) によって生成され、すべての関係が特定の形式になります。

対称群に関する主要な結果の一つは、与えられた順列の転置への分解の全てが偶数個の転置を持つか、全てが奇数個の転置を持つかのいずれかである、というものである。^[11]これにより、順列の偶奇性を明確に定義できる概念となる。

参照

• サイクルソート- ソートする順列をサイクルに分解し、それを個別に回転させてソート結果を得ることができるという考えに基づくソートアルゴリズム。
• サイクルと固定点
• 整数の巡回置換
• サイクル表記
• タンパク質における循環置換
• フィッシャー・イェーツ・シャッフル

注記

1. サイクル表記は一意ではないことに注意してください。各kサイクルは、その軌道の選択に応じて、 k つの異なる方法で記述できます。 ${\displaystyle s_{0}}$

参考文献

1. Gross, Jonathan L. (2008).コンピュータアプリケーションにおける組み合わせ法. 離散数学とその応用. フロリダ州ボカラトン: Chapman & Hall/CRC. p. 29. ISBN 978-1-58488-743-0。
2. Knuth, Donald E. (2002). 『コンピュータプログラミングの芸術』 Addison-Wesley. p. 35.
3. ボガート, ケネス・P. (2000).入門組合せ論（第3版）. ロンドン: ハーコート・アカデミック・プレス. p. 554. ISBN 978-0-12-110830-4。
4. Rosen, Kenneth H. (2000).離散数学と組合せ数学ハンドブック. ボカラトン、ロンドン、ニューヨーク: CRCプレス. ISBN 978-0-8493-0149-0。
5. エールリッヒ、ガートルード (2013). 『抽象代数の基礎概念』 ドーバー数学ブックス. クーリエ社. p. 69. ISBN 9780486291864。
6. フレイリー 1993, p. 103
7. ロットマン 2006、108ページ
8. サガン 1991、2ページ
9. ロットマン 2006、117、121ページ
10. ロットマン 2006、118ページ、提案2.35
11. ロットマン 2006、122ページ

出典

• アンダーソン、マーロウ、フェイル、トッド（2005年）『抽象代数学入門』チャップマン＆ホール／CRC、第2版。ISBN 1-58488-515-7。
• ジョン・フレイリー (1993)、抽象代数の最初のコース(第 5 版)、アディソン・ウェスリー、ISBN 978-0-201-53467-2
• ロットマン、ジョセフ・J.（2006年）、抽象代数の入門講座（第3版）、プレンティス・ホール、ISBN 978-0-13-186267-8
• セーガン、ブルース・E.（1991）『対称群／表現、組合せアルゴリズム、対称関数』、ワズワース＆ブルックス／コール、ISBN 978-0-534-15540-7

外部リンク

この記事にはPlanetMathの cycle からの資料が組み込まれており、これはCreative Commons Attribution-Share-Alike Licenseに基づいてライセンスされています。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Cyclic_permutation&oldid=1296557739#Transpositions"