巡回順列

固定元を持たない（数学的な）順列の一種

数学、特に群論において、巡回置換（しゅこうかんけい）とは、単一のサイクルからなる置換のことである。 ^{[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 つで構成されます。

定義

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 }（ある整数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．29ページ．ISBN 978-1-58488-743-0。
2. ドナルド・E. クヌース (2002). 『コンピュータプログラミングの芸術』 . アディソン・ウェスレー. 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, p. 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"