巡回順列

数学、特に群論において、巡回置換（しゅうこうけい、英: 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 サイクルで構成されます。

巡回置換の正確な定義については、広く合意が得られていません。一部の著者は、集合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 つあり、そのサイクル図は右に示されています。著者の中には、この順列を循環的であると考える人もいれば、そうでない人もいます。

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

より正式には、拡大定義では、集合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]

対称群S _nのkサイクルの数は、に対して、次の同値な式で 与えられます。${\displaystyle 1\leq k\leq n}$$${\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n !}{(nk)!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)}$

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があった場所に戻すを、これら 2 つが入れ替わり、他の変更は行われません。 ${\表示スタイル (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 の要素 (隣接する転置) によって生成され、すべての関係は特定の形式になります。

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

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

• Anderson, Marlow および Feil, Todd (2005)、『抽象代数入門』、Chapman & Hall/CRC、第 2 版。ISBN 1-58488-515-7。 
• フレイリー、ジョン（1993）、抽象代数学入門（第5版）、アディソン・ウェスレー、ISBN 978-0-201-53467-2
• ロットマン、ジョセフ・J.（2006）、応用付き抽象代数入門（第3版）、Prentice-Hall、ISBN 978-0-13-186267-8
• セーガン、ブルース E. (1991)、「対称群 / 表現、組合せアルゴリズム、対称関数」、ワズワース & ブルックス/コール、ISBN 978-0-534-15540-7

• 順列の循環表記法、ビデオでは循環分解について説明します。

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