重複置換

数学における重複置換（ちょうふくちかん、仏: permutations avec répétition）は、区別不能なものを含む対象を順番を考慮して複数の組に分ける方法を言う（対象は区別できないが、組は区別が付く）。例えば、 $112, 121, 211$ は二つの $1$ と一つの $2$ を持つ重複置換である。

一部に区別のつかないものを含む $n$ 個の対象を並べ替えて特定の順番に並べるとき、いくつか同じものが生じる場合がある。 $k \leq n$ として、 $n$ 個の対象がつくる $n$ -組が $k$ 種類の相異なる組に分けられるとき、その各々が $n 1, n 2, \dots, n k$ 個の対象を含む（ただし、 $n 1 + n 2 + \dots + n k = n$ を満たす）ものを考える。このような $n$ -組のなかで区別不能なものを入れ替えて得られる $n$ -組は同じものと考える。例えば、文字列 MATHÉMATIQUE のアナグラムを全て求めようとするとき、二つの A は区別が付かないのでこれらを入れ替えても文字列としては変わらないが、É と E を入れ替えたときは文字列として相異なる。

重複置換を同じものを含む順列と呼ぶことがある。

定義

位数 $k$ の有限集合 $E$ を $E = {x 1, x 2, \dots, x k}$ と書く。 $n$ は $k \leq n$ なる自然数で、 $n 1, n 2, \dots, n k$ を

n 1 + n 2 + \dots + n k = n

を満たす非負整数とする。このとき、 $E$ の元からなる重複度 $(n 1, n 2, \dots, n k)$ の $n$ -重複置換とは、 $E$ の各元 $x i$ がそれぞれ $n i$ 回現れる $n$ -組（項数 $n$ の有限列）を言う。

例えば

{\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}}

はその一つである。

重複置換の数え上げ

→詳細は「多項係数」を参照

定理

重複度

(n 1, n 2, \dots, n k)

の

n

-重複置換の総数

p (n 1, n 2, \dots, n k)

は

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

-組を作るには

n 1

個の

x 1

の位置を決め、

n 2

個の

x 2

の位置を決め、……、

n k

個の

x k

の位置を決めれば十分である。

$x 1$ の入る $n 1$ 箇所を $n 1 + n 2 + \dots + n k$ 箇所から選ぶ方法が ${\tbinom {n_{1}+n_{2}+\dotsb +n_{k}}{n_{1}}}$ 通り、
$x 2$ の入る $n 2$ 箇所を $n 2 + n 3 + \dots + n k$ 箇所から選ぶ方法が ${\tbinom {n_{2}+\dotsb +n_{k}}{n_{2}}}$ 通り、
…
$x k$ の入る $n k$ 箇所を残りに入れる方法が ${\tbinom {n_{k}}{n_{k}}}$ 通り。

以上をまとめると、

{\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}!}}

を得る。

応用

演算 "+" が可換（あるいはより一般に和の各項が "+" に関して可換）であるとき、

(x_{1}+x_{2}+\dotsb +x_{k})^{n}=\underbrace {(x_{1}+x_{2}+\dotsb +x_{k})(x_{1}+x_{2}+\dotsb +x_{k})\dotsb (x_{1}+x_{2}+\dotsb +x_{k})} _{n{\text{ factors}}}

を、 $1 \leq i \leq n$ なる任意の $i$ について $i$ 番目の因子から取った項を第 $i$ -成分とする $x 1, x 2, \dots, x k$ からなる $n$ -組の積の和の形に展開することを考える。任意の $1 \leq i \leq k$ に対して、この $n$ -組に現れる $x i$ の個数を $n i$ とすると $n 1 + n 2 + \dots + n k = n$ が成り立ち、対応する積は $\textstyle x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$ の形になる。自然数の列 $n 1, n 2, \dots, n k$ で $n 1 + n 2 + \dots + n k = n$ を満たすものを与えたとき、 $\textstyle x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$ の形の項の総数は重複度 $(n 1, n 2, \dots, n k)$ の $n$ -重複置換の総数に等しい。