重複順列

数学における重複順列（ちょうふくじゅんれつ、, ）は、区別可能な  個の対象から重複を許して  個の対象を取り出して特定の順番でならべることで生じる。大抵の場合、これを -組（あるいは長さ  のリスト）として表す。例えば、 から  までの番号が振られた  個の玉が入った箱から  個の玉を取り出して、取り出した順番に番号をリストに記録すると重複順列を得る。 

 定義 
重複順列の定義の仕方は（同値なものが）いくつかある。

 定義 1 位数   の有限集合  と非負整数  が与えられたとき、 の元からなる -重複順列（または  個の元から重複を許して  個選んで作られる -項順列）とは、 の元を要素とする -順序組（-項の有限列）を言う。
 定義 2 位数   の有限集合  と非負整数  が与えられたとき、 の元からなる -重複順列とは、集合 から  への写像のことを言う。

 重複順列の総数 
 定理  位数  の有限集合  と自然数  に対して、 の元からなる -重複順列全体の成す集合は有限であり、その位数は  で与えられる。

 証明
 -組として見れば、 の元からなる -重複順列全体の成す集合は  に他ならない。故にその位数に関して  は明らか。
 から  への写像と見れば、 の行き先が  通り、 の行き先が  通り、……、 の行き先が  通りであるから、相異なる写像は  通りである。

 使用例 
モールス信号は二種類の記号 "─", "●" を字母とする語（文字列）である。 を非負整数とすると、 文字の語は集合 に関する -重複順列であり、長さがちょうど  の語は  種類である。

 関連項目 
 組合せ (数学)
 重複組合せ
 順列
 置換 (数学)
 重複置換

 外部リンク 
 Nombre de combinaisons et d’arrangements avec répétitions limitées. Par Michel Hort

Category:組合せ論
Category:数列
Category:順列
Category:数学に関する記事