順列

出典: フリー百科事典『ウィキペディア（Wikipedia）』

組合せ数学における順列（じゅんれつ、permutation）は、あるひとつの集合から要素を選び出して、順番に意味を持たせて並べる (ordering) ときの、その並び（ordered list, sequence; 有限列）のことである。

順列をつくるとき、いくつかの要素を落として使わないこと（omission; 省略）やいくつかの要素を何度も使うこと（duplication, repetition; 重複）ができるが、取り出す要素に重複を許す順列を重複順列（ちょうふくじゅんれつ、repeated permutation）と呼んで特に区別する場合がある。たとえば、(1)、(1,3)、(1,3,2,3) などはそれぞれ （{1,2,3} の要素からなる）順列であり、この中では (1,3,2,3) が重複順列である。また、省略も重複もない特別な場合の順列を置換と呼ぶことがある[1]。

目次

[編集] 順列の総数

要素の選び方に一定の規則をあたえるとき、その順列の総数を数えるのは一般には難しい。いくつかの場合にはその総数を求める方法が与えられており、またその総数に特別の記号を与えてやることで他の場合に応用することができる。

[編集] 重複のない場合

n 個の異なった要素の中から m 個の相異なる要素を選び出した順列の個数（総数）はnPm と表され、

{}_n{\rm P}_m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}

と計算できる。ただし、記号 ! は階乗を意味する。

たとえば、math のなかから重複なしに二つの文字を取り出して得られる順列は

(m, a)、(m, t)、(m, h)、(a, m)、(a, t)、(a, h)、(t, m)、(t, a)、(t, h)、(h, m)、(h, a)、(h, t)

の 12 = 4!/(4-2)! 個である。

特にn 個の異なった要素の中から n 個全て選び出した順列の個数はnPn =n!となる。

[編集] 重複を許す場合

n 個の異なった要素から重複を許して m 個の要素を選び出した重複順列の総数は nΠm で表され、nm で計算できる。

また、選び出す要素ごとにその選び出す個数（重複度）を指定した重複順列の総数も計算できる。 例えば、{1, 2, ..., p} から n 個の要素を、 k が nk 個 (1 ≤ k ≤ p) であるように取り出して得られる重複順列の総数は

{n \choose n_1,n_2,\ldots,n_p} = \frac{n!}{n_1!\,n_2!\cdots n_p!}

である。

[編集] 置換

詳細は「対称群」を参照

有限集合 X の要素全てを落とさず重複無く用いて得られる順列は、特に置換と呼ばれる。つまり、置換は X 上の（X 自身への）全単射であり、写像の合成に関して置換群 (permutation group) と呼ばれる群を与える代数学的な対象となる。

[編集] 関連項目

[編集] 脚注

  1. ^ と言っても、順列も置換も対応する英語は permutation なのだが。
"http://ja.wikipedia.org/wiki/%E9%A0%86%E5%88%97" より作成