順列(円順列・同じものを含む順列・重複順列)

 

順列 Permutation

 a, b, c, d, e という 5 つのアルファベットから 3 つの文字を選んで並べます。ただし文字を重複して選ぶことはしないものとします。その並べ方は何通りあるでしょう。

 Excel順列の基本

 図のように空白のマス目を使うとイメージしやすいです。
 まず 5 つの文字から 1 つを選んで左端に入れます。その方法は 5 通りですね。次に中央に入れる文字を選びます。1 度選んだ文字を再び使用することはできないので、4 文字から 1 つを選ぶことになります。つまり 4 通りです。同様に右端に入れる文字の選び方は 3 通りとなります。よって積の法則から、並べ方の総数は
 
\[5\times 4\times 3=60\]
となります。このとき、

abc, dae, ced

などの1つ1つを a, b, c, d, e から 3 個とった 順列 (permutation) とよびます。

 一般に $n$ 個の異なったものから r 個を取り出して 1 列に並べたものを順列とよび、その総数は
\[_n\mathrm{P}_r=n(n-1)(n-2)\:\cdots\:(n-r+1)\tag{A1}\]で与えられます。

 たとえば上の例では 5 個のものから 3 個をとるので、その総数は
 
\[_5\mathrm{P}_3=5\times 4\times 3=60\]
と書くことができます。また特に $n=r$ のときには
 
\[_n\mathrm{P}_n=n(n-1)(n-2)\:\cdots\:3\cdot 2\cdot 1=n!\]
で与えられます。$n!$ は 階乗 を表す記号です。通常は (A1) で計算する方法が簡単ですが、ある種の証明などでは順列の総数を階乗記号で表したほうが便利なこともあります。
 
\[\begin{align*}_n\mathrm{P}_r&=n(n-1)(n-2)\:\cdots\:(n-r+1)\\[6pt]
&=\frac{n(n-1)(n-2)\:\cdots\:(n-r+1)(n-r)\:\cdots\:2\cdot 1}{(n-r)\:\cdots\:2\cdot 1}=\frac{n!}{(n-r)!}\end{align*}\]
 $0!=1$ と定義されているので、$n=r$ のときは $_n\mathrm{P}_n=n!$ となります。
 

円順列 Circular Permutation

 A, B, C, D の 4 人が丸いテーブルに座って食事をします。このとき、異なる順序の座り方は何通りあるのか数えてみましょう。
 
 回転させると一致します

 上の図にあるように、回転して一致する場合は同じ並び方とします。
 そこで A さんを固定させて、残りの人の座り方を考えることにします。

 円順列Aを固定

 その並び方の総数は $_3\mathrm{P}_3=3!=12$ 通りになります。

 一般に $n$ 個の異なるものを円形に並べるとき、異なる並べ方の総数は $(n-1)!$ で与えられます。

 このような順列のことを 円順列 (circular permutation) とよびます。
 

首飾り順列 Necklace Permutation

 円順列とよく似たものに 首飾り順列 (necklace permutation) というものがあります。円順列と同じく平面内の回転操作に加えて、裏返すことによって一致するものは同じ並びとみなします。

 

 各々の並び方に対して裏返しは 2 通りあるので、

 一般に $n$ 個の異なるものからつくられる首飾り順列の総数は $(n-1)/2!$ 個あります。

 たとえば 6 個の異なる色の玉を用いて数珠をつくる方法は
 
\[\frac{(6-1)!}{2}=60\]
あります。
 

同じものを含む順列 Permutations of Multisets

 赤い玉 3 つと青い玉 2 つの並べ方の総数を調べてみましょう。考えやすいように、赤い玉には 1, 2, 3 という番号を、青い玉にも 1, 2 という番号を割り振ります。この 5 つの異なる玉の並び方は $5!$ 個あります。

 同じものを含む順列

 そして番号によって区別しないことにすれば、上の図のように青い玉の 1 と 2 を入れ替えても同じ並び方ですし、赤い玉は 1, 2, 3 のどれを入れ替えても同じです。つまり並べ方の総数は
 
\[\frac{5!}{2!3!}=10\]
となります。

 $n$ 個の中に $p$ 個の同じもの、$q$ 個の同じもの、$r$ 個の同じもの ... があるとき、$n$ 個のものを全て 1 列に並べる順列の総数は
\[\frac{n!}{p!q!r!\cdots}\]あります。ただし
\[n=p+q+r+\cdots\]です。

 

重複順列 Permutations with Repetition

 1, 2, 3, 4, 5 の 5 つの数字を用いてつくる 3 桁の整数はいくつあるのか考えてみます。ただし同じ数字を繰り返し使ってよいことにします。100 の位の選び方は 5 通り、10 の位も 5 通り、1 の位も 5 通りあるので、つくられる整数は全部で $5^3=125$ 個ということになります。

 $n$ 個の異なったものから、繰り返しとることを許して $r$ 個とるときの並べ方は $n^r$ 個です。

 このような順列を 重複順列 (permutations with repetition) とよびます。
 ≫ 数学事典

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください