重複置換
所期の 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}!}}}
を得る。