円順列

無題

先程の『順列』では，区別するものを１列に並べる場合を考えたが，ここでは円形に並べる場合について考えてみる．

例えば， $\fbox{A}$ ， $\fbox{B}$ ， $\fbox{C}$ ， $\fbox{D}$ の4人が手をつないで1つの輪をつくるとき，輪のでき方には何通りあるか考えてみよう．

まず，この4人を1列に並べると右図のようになり，その並べ方は $4!$ 通りである．

ここで，例えば右図の①，②，③，④は，輪になった場合に下の図のようになると考えることができる．

これら4つの並び方は，回転させることによって重なるので，どれも同じ1つの並び方だと考えられる．

つまり，右図の①，②，③，④のように，“順送り”に並ぶ4つの順列は，円形に並べた場合には同一視するのである．

よって，この4人の作る輪は $\frac{4!}{4}=3!=6$ 通りある．

ここで，円順列を定義しておこう．

この例では， $cir(4)=\frac{4!}{4}=3!=6$ である．

一般に，区別する $n$ 個のものを円形に並べた場合の総数も，先程の例と同じように考えることができ， 次のようにまとめられる．

無題

また，円順列が $(n − 1)!$ と計算される理由は，次のように説明することもできる．

簡単のため，先程の $cir(4)$ が $3!$ で計算できることについて考えてみよう．

右図のように，まず $\fbox{A}$ を固定して，そこから円をつくるように残りの $\fbox{B}$ ， $\fbox{C}$ ， $\fbox{D}$ を並べると考えて， $3!$ 通りとなり，これは $cir(4)$ と一致する．

一般の $cir(n)$ の場合も，1つを固定して，その周りに残りの $n − 1$ 個のものを並べると考えて

と考えることができる．

無題

右図のように，円順列としては区別される2つの順列も，表裏をひっくり返すことができる場合には同一視して1通りと数える．

このように表裏をひっくり返すことができる場合の円順列を， ネックレス順列(nacklace permutation) または 数珠じゅず順列(beads permutation) といい， その総数を $FTEXT$ では $neck(n)$ と表す． $neck(n)=\dfrac{cir(n)}{2}=\frac{(n-1)!}{2}$ である．