数学における重複順列(ちょうふくじゅんれつ、, )は、区別可能な 個の対象から重複を許して 個の対象を取り出して特定の順番でならべることで生じる。大抵の場合、これを -組(あるいは長さ のリスト)として表す。例えば、 から までの番号が振られた 個の玉が入った箱から 個の玉を取り出して、取り出した順番に番号をリストに記録すると重複順列を得る。
定義 重複順列の定義の仕方は(同値なものが)いくつかある。
定義 1 位数 の有限集合 と非負整数 が与えられたとき、 の元からなる -重複順列(または 個の元から重複を許して 個選んで作られる -項順列)とは、 の元を要素とする -順序組(-項の有限列)を言う。 定義 2 位数 の有限集合 と非負整数 が与えられたとき、 の元からなる -重複順列とは、集合 から への写像のことを言う。
重複順列の総数 定理 位数 の有限集合 と自然数 に対して、 の元からなる -重複順列全体の成す集合は有限であり、その位数は で与えられる。
証明 -組として見れば、 の元からなる -重複順列全体の成す集合は に他ならない。故にその位数に関して は明らか。 から への写像と見れば、 の行き先が 通り、 の行き先が 通り、……、 の行き先が 通りであるから、相異なる写像は 通りである。
使用例 モールス信号は二種類の記号 "─", "●" を字母とする語(文字列)である。 を非負整数とすると、 文字の語は集合 に関する -重複順列であり、長さがちょうど の語は 種類である。
関連項目 組合せ (数学) 重複組合せ 順列 置換 (数学) 重複置換
外部リンク Nombre de combinaisons et d’arrangements avec répétitions limitées. Par Michel Hort