円順列

円順列$cir(n)$の定義

無題

無題

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

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

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

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

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

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

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

ここで,円順列を定義しておこう.

円順列 $cir(n)$ の定義

「区別するn個のものを,円形に並べた列」のことをn個の円順列(circular permutation)という. $FTEXT$ では,その並べ方の総数を $\boldsymbol{cir(n)}$ と表すことにする.

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

円順列$cir(n)$の計算

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

円順列 $cir(n)$ の計算

$n$ 個の円順列の総数 $cir(n)$ は

\[cir(n)=\dfrac{n!}{n}=(n-1)!\]

と計算できる.

無題

無題

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

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

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

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

\[cir(n) = (n − 1)!\]

と考えることができる.

ネックレス順列$neck(n)$の定義・計算

無題

無題

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

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

円順列とネックレス順列

  1. 7個の異なる玉を円形に並べるとき,その並べ方は何通りあるか.
  2. 7個の異なる玉を円形に並べてネックレスを作るとき,その作り方は何通りあるか.

  1. $cir(7)=(7-1)!=\boldsymbol{720}$ 通り
  2. $neck(7)=\dfrac{(7-1)!}{2}=\boldsymbol{360}$ 通り