サイクルと固定点

数学において、有限集合Sの順列πのサイクルは、 Sに作用するπによって生成される部分群の軌道に全単射的に対応する。これらの軌道はS の部分集合であり、 { c ₁ , ..., c _n }と表記され、

π ( c _i ) = c _{i + 1}（ i = 1, ..., n − 1）、 π ( c _n ) = c ₁。

πの対応するサイクルは( c ₁ c ₂ ... c _n )と表されます。c 1_は軌道の任意の要素として選択できる ため、この表現は一意ではありません。

軌道の大きさn は対応するサイクルの長さと呼ばれます。n = 1の場合、軌道内の単一の要素は順列の 不動点と呼ばれます。

順列は各サイクルの式を与えることによって決定され、順列の表記法の1つは、そのような式をある順序で次々に書くことから成ります。例えば、

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

1を2に、6を8に、といった順列である。すると、

π = ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) ( 7) = ...

ここで、5と7はπの不動点です。π (5) = 5、π (7)=7だからです。このような式では長さ1のサイクルを書かないのが一般的ですが、必須ではありません。^[1]したがって、π  = (1 2 4 3)(6 8) は、この順列を表現するのに適切な方法です。

順列をそのサイクルのリストとして記述する方法はいくつかありますが、サイクルの数とその内容はS を軌道に分割することによって与えられるため、このようなすべての式で同じになります。

第一種符号なしスターリング数s ( k , j )は、 k個の要素とj個の互いに素な閉路を持つ順列の数を数える。^{[2] [3]}

（１）すべてのk > 0に対して： s ( k , k ) = 1。

（２）すべてのk > 0について： s ( k ,1) = ( k −1)！。

（３）すべてのk > j > 1について、 s ( k , j ) = s ( k − 1, j − 1) + s ( k − 1, j )·( k − 1)

(1) k個のサイクルを持つk個の要素の順列を構築する方法は 1 つしかありません。すべてのサイクルの長さは 1 でなければならないため、すべての要素は固定点である必要があります。

(2.a)長さkのすべてのサイクルは、1からkまでの数の順列として表すことができます。このような順列はk !個あります。

(2.b)長さkの閉路を表記する方法はk通りある。例えば、(1 2 4 3) = (2 4 3 1) = (4 3 1 2) = (3 1 2 4)である。

(2.c)最後に: s ( k , 1) = k !/ k = ( k − 1)!.

（３）k個の要素とj個の循環を持つ順列を構築するには2つの方法がある。

(3.a)要素kを不動点にしたい場合は、 k −1個の要素とj −1個のサイクルを持つs ( k −1, j −1)個の順列のうちの1つを選択し、要素kを長さ1の新しいサイクルとして追加します。

(3.b)要素kを 不動点にしたくない場合は、 k −1個の要素とj個のサイクルを持つs ( k −1, j )順列の1つを選択し、既存のサイクル内のk −1個の要素の1つの前に要素kを挿入します。

値f ( k , j )は、正確にj 個の固定点を持つk個の要素の順列の数を数えます。このトピックに関するメインの記事については、rencontres numbers を参照してください。

（１）すべてのj <0またはj > kに対して ：f ( k , j )=0。

（２） f（０，０）＝１。

（３）任意のk > 1およびk ≥ j ≥ 0に対して、 f ( k , j ) = f ( k − 1, j − 1) + f ( k − 1, j )·( k − 1 − j ) + f ( k − 1, j + 1)·( j + 1)

（３）j個の固定点を持つk個の要素の順列を構築するには3つの異なる方法がある。

(3.a) k −1個の要素とj −1個の固定点を持つf ( k −1, j −1)個の順列のうちの1つを選択し、要素kを新しい固定点として追加することができる。

(3.b) k −1個の要素とj個の固定点を持つf ( k −1, j )順列の1つを選択し、長さが1より大きい既存のサイクル内の要素kを( k −1) −j個の要素の1つの前に挿入することができる。

(3.c) k −1個の要素とj +1個の固定点を持つf ( k −1, j +1)個の順列のうちの1つを選択し、要素kとj +1個の固定点のうちの1つを結合して長さ2のサイクルを作ることができる。

• 巡回順列
• サイクル表記

• Brualdi, Richard A. (2010)、Introductory Combinatorics (第 5 版)、Prentice-Hall、ISBN 978-0-13-602040-0
• キャメロン、ピーター J. (1994)、組合せ論: トピック、テクニック、アルゴリズム、ケンブリッジ大学出版局、ISBN 0-521-45761-0
• ガースタイン、ラリー J. (1987)、離散数学と代数構造、WH フリーマン アンド カンパニー、ISBN 0-7167-1804-9