数学における重複置換(ちょうふくちかん、仏: permutations avec repetition)は、区別不能なものを含む対象を順番を考慮して複数の組に分ける方法を言う(対象は区別できないが、組は区別が付く)。例えば、112, 121, 211 は二つの 1 と一つの 2 を持つ重複置換である。
一部に区別のつかないものを含む n 個の対象を並べ替えて特定の順番に並べるとき、いくつか同じものが生じる場合がある。k ≤ n として、n 個の対象がつくる n-組が k 種類の相異なる組に分けられるとき、その各々が n1, n2, …, nk 個の対象を含む(ただし、n1 + n2 + … + nk =n を満たす)ものを考える。このような n-組のなかで区別不能なものを入れ替えて得られる n-組は同じものと考える。例えば、文字列 MATHEMATIQUE のアナグラムを全て求めようとするとき、二つの A は区別が付かないのでこれらを入れ替えても文字列としては変わらないが、E と E を入れ替えたときは文字列として相異なる。
重複置換を同じものを含む順列と呼ぶことがある。 位数 k の有限集合 E を E = {x1, x2, …, xk}と書く。n は k ? n なる自然数で、n1, n2, …, nk をn1 + n2 + … + nk = n を満たす非負整数とする。このとき、E の元からなる重複度 (n1, n2, …, nk) の n-重複置換とは、E の各元 xi がそれぞれ ni 回現れる n-組(項数 n の有限列)を言う。 例えば ( x 1 , … , x 1 ⏟ , x 2 , … , x 2 ⏟ , … , x k , … , x k ⏟ ) n 1 f o i s n 2 f o i s n k f o i s {\displaystyle {\begin{matrix}(\underbrace {x_{1},\ldots ,x_{1}} ,&\underbrace {x_{2},\ldots ,x_{2}} ,&\ldots ,&\underbrace {x_{k},\ldots ,x_{k}} )\\{}_{n_{1}{\rm {\,fois}}}&{}_{n_{2}{\rm {\,fois}}}&&{}_{n_{k}{\rm {\,fois}}}\end{matrix}}} はその一つである。
定義
重複置換の数え上げ詳細は「多項係数」を参照
定理
重複度 (n1, n2, …, nk) の n-重複置換の総数 p(n1, n2, …, nk) は p ( n 1 , n 2 , … , n k ) = ( n n 1 , n 2 , … , n k ) = n ! n 1 ! n 2 ! ⋯ n k ! {\displaystyle p(n_{1},n_{2},\ldots ,n_{k})={\binom {n}{n_{1},n_{2},\ldots ,n_{k}}}={\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}} で与えられる。この数は多項係数として知られる。
証明
所期の n-組を作るには n1 個の x1 の位置を決め、n2 個の x2 の位置を決め、……、nk 個の xk の位置を決めれば十分である。
x1 の入る n1 箇所を n1 + n2 + … + nk 箇所から選ぶ方法が ( n 1 + n 2 + ⋯ + n k n 1 ) {\displaystyle {\tbinom {n_{1}+n_{2}+\dotsb +n_{k}}{n_{1}}}} 通り、
x2 の入る n2 箇所を n2 + n3 + … + nk 箇所から選ぶ方法が ( n 2 + ⋯ + n k n 2 ) {\displaystyle {\tbinom {n_{2}+\dotsb +n_{k}}{n_{2}}}} 通り、
…
xk の入る nk 箇所を残りに入れる方法が ( n k n k ) {\displaystyle {\tbinom {n_{k}}{n_{k}}}} 通り。
以上をまとめると、 ( n 1 + n 2 + ⋯ + n k n 1 ) ( n 2 + ⋯ + n k n 2 ) ⋯ ( n k n k ) = n ! n 1 ! n 2 ! ⋯ n k ! {\displaystyle {\binom {n_{1}+n_{2}+\dotsb +n_{k}}{n_{1}}}{\binom {n_{2}+\dotsb +n_{k}}{n_{2}}}\dotsb {\binom {n_{k}}{n_{k}}}={\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}} を得る。