数学 における重複置換 （ちょうふくちかん、仏 : permutations avec répétition 112, 121, 211 は二つの 1 と一つの 2 を持つ重複置換である。
一部に区別のつかないものを含む n 個の対象を並べ替えて特定の順番に並べるとき、いくつか同じものが生じる場合がある。k ≤ n n 個の対象がつくる n -組 が k 種類の相異なる組に分けられるとき、その各々が n 1 , n 2 , …, n k n 1 + n 2 + … + n k n n -組のなかで区別不能なものを入れ替えて得られる n -組は同じものと考える。例えば、文字列 MATHÉMATIQUE のアナグラム を全て求めようとするとき、二つの A は区別が付かないのでこれらを入れ替えても文字列としては変わらないが、É と E を入れ替えたときは文字列として相異なる。
重複置換を同じものを含む順列 と呼ぶことがある。
位数 k の有限集合 E を E = {x 1 , x 2 , …, x k n は k ≤ n n 1 , n 2 , …, n k
n 1 + n 2 + … + n k n を満たす非負整数とする。このとき、E の元からなる重複度 (n 1 , n 2 , …, n k の n -重複置換とは、E の各元 x i n i 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}}}
はその一つである。
重複置換の数え上げ
編集
定理
重複度 (n 1 , n 2 , …, n k の n -重複置換の総数 p (n 1 , n 2 , …, n k
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 -組を作るには n 1 x 1 n 2 x 2 n k x k x 1 n 1 n 1 + n 2 + … + n k
(
n
1
+
n
2
+
⋯
+
n
k
n
1
)
{\displaystyle {\tbinom {n_{1}+n_{2}+\dotsb +n_{k}}{n_{1}}}}
x 2 n 2 n 2 + n 3 + … + n k
(
n
2
+
⋯
+
n
k
n
2
)
{\displaystyle {\tbinom {n_{2}+\dotsb +n_{k}}{n_{2}}}}
…
x k n k
(
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}!}}}
を得る。
演算 "+" が可換（あるいはより一般に和の各項が "+" に関して可換）であるとき、
(
x
1
+
x
2
+
⋯
+
x
k
)
n
=
(
x
1
+
x
2
+
⋯
+
x
k
)
(
x
1
+
x
2
+
⋯
+
x
k
)
⋯
(
x
1
+
x
2
+
⋯
+
x
k
)
⏟
n
factors
{\displaystyle (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 ≤ i ≤ n なる任意の i について i 番目の因子から取った項を第 i -成分とする x 1 , x 2 , …, x k n -組の積の和の形に展開することを考える。任意の 1 ≤ i ≤ k に対して、この n -組に現れる x i n i n 1 + n 2 + … + n k n
x
1
n
1
x
2
n
2
⋯
x
k
n
k
{\displaystyle \textstyle x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}}
n 1 , n 2 , …, n k n 1 + n 2 + … + n k n
x
1
n
1
x
2
n
2
⋯
x
k
n
k
{\displaystyle \textstyle x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}}
(n 1 , n 2 , …, n k の n -重複置換の総数に等しい。
こうして多項定理 :
(
x
1
+
x
2
+
…
+
x
k
)
n
=
∑
n
1
+
n
2
+
…
+
n
k
=
n
n
!
n
1
!
n
2
!
…
n
k
!
x
1
n
1
x
2
n
2
…
x
k
n
k
{\displaystyle (x_{1}+x_{2}+\ldots +x_{k})^{n}=\sum _{n_{1}+n_{2}+\ldots +n_{k}=n}{\frac {n!}{n_{1}!n_{2}!\ldots n_{k}!}}x_{1}^{n_{1}}x_{2}^{n_{2}}\ldots x_{k}^{n_{k}}}
を得る（k = 2二項定理 が導かれる）。
関連項目
編集
