重複置換のソースを表示

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

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

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

== 定義 ==
[[濃度 (数学)|位数]] {{mvar|k}} の有限集合 {{mvar|E}} を {{math|1=''E'' = {''x''<sub>1</sub>, ''x''<sub>2</sub>, …, ''x''<sub>''k''</sub>} }}と書く。{{mvar|n}} は {{math|''k'' ≤ ''n''}} なる自然数で、{{math|''n''{{ind|1}}, ''n''{{ind|2}}, …, ''n''{{ind|''k''}}}} を
: {{math|''n''{{ind|1}} + ''n''{{ind|2}} + … + ''n''{{ind|''k''}} {{=}} ''n''}}
を満たす非負整数とする。このとき、{{mvar|E}} の元からなる重複度 {{math|(''n''{{ind|1}}, ''n''{{ind|2}}, …, ''n''{{ind|''k''}})}} の {{mvar|n}}-重複置換とは、{{mvar|E}} の各元 {{mvar|''x''{{ind|''i''}}}} がそれぞれ {{mvar|''n''{{ind|''i''}}}} 回現れる {{mvar|n}}-組（項数 {{mvar|n}} の[[列 (数学)|有限列]]）を言う。

例えば
: <math>\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}</math>
はその一つである。

== 重複置換の数え上げ ==
{{main|多項係数}}
; 定理: 重複度 {{math|(''n''{{ind|1}}, ''n''{{ind|2}}, …, ''n''{{ind|''k''}})}} の {{mvar|n}}-重複置換の総数 {{math|''p''(''n''{{ind|1}}, ''n''{{ind|2}}, …, ''n''{{ind|''k''}})}} は
:: <math>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!}</math>
: で与えられる。この数は[[多項係数]]として知られる。

; 証明 : 所期の {{mvar|n}}-組を作るには {{math|''n''{{ind|1}}}} 個の {{math|''x''{{ind|1}}}} の位置を決め、{{math|''n''{{ind|2}}}} 個の {{math|''x''{{ind|2}}}} の位置を決め、……、{{math|''n''{{ind|''k''}}}} 個の {{math|''x''{{ind|''k''}}}} の位置を決めれば十分である。
:* {{math|''x''{{ind|1}}}} の入る {{math|''n''{{ind|1}}}} 箇所を {{math|''n''{{ind|1}} + ''n''{{ind|2}} + … + ''n''{{ind|k}}}} 箇所から選ぶ方法が <math>\tbinom{n_1+n_2+\dotsb+n_k}{n_1}</math> 通り、
:* {{math|''x''{{ind|2}}}} の入る {{math|''n''{{ind|2}}}} 箇所を {{math|''n''{{ind|2}} + ''n''{{ind|3}} + … + ''n''{{ind|k}}}} 箇所から選ぶ方法が <math>\tbinom{n_2+\dotsb+n_k}{n_2}</math> 通り、
:* …
:* {{math|''x''{{ind|''k''}}}} の入る {{math|''n''{{ind|''k''}}}} 箇所を残りに入れる方法が <math>\tbinom{n_k}{n_k}</math> 通り。
: 以上をまとめると、
::<math>\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!}</math>
: を得る。

== 応用 ==
演算 "+" が可換（あるいはより一般に和の各項が "+" に関して可換）であるとき、
: <math>(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}}</math>
を、{{math|1 ≤ ''i'' ≤ ''n''}} なる任意の {{mvar|i}} について {{mvar|i}} 番目の因子から取った項を第 {{mvar|i}}-成分とする {{math|''x''{{ind|1}}, ''x''{{ind|2}}, …, ''x''{{ind|''k''}}}} からなる {{mvar|n}}-組の積の和の形に展開することを考える。任意の {{math|1 ≤ ''i'' ≤ ''k''}} に対して、この {{mvar|n}}-組に現れる {{math|''x''{{ind|''i''}}}} の個数を {{math|''n''{{ind|''i''}}}} とすると {{math|''n''{{ind|1}} + ''n''{{ind|2}} + … + ''n''{{ind|''k''}} {{=}} ''n''}} が成り立ち、対応する積は<math>\textstyle x_1^{n_1}x_2^{n_2}\dotsb x_k^{n_k}</math> の形になる。自然数の列 {{math|''n''{{ind|1}}, ''n''{{ind|2}}, …, ''n''{{ind|''k''}}}} で {{math|1=''n''{{ind|1}} + ''n''{{ind|2}} + … + ''n''{{ind|''k''}} = ''n''}} を満たすものを与えたとき、<math>\textstyle x_1^{n_1}x_2^{n_2}\dotsb x_k^{n_k}</math> の形の項の総数は重複度 {{math|(''n''{{ind|1}}, ''n''{{ind|2}}, …, ''n''{{ind|''k''}})}} の {{mvar|n}}-重複置換の総数に等しい。

こうして[[多項定理]]:
: <math>(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}</math>
を得る（{{math|1=''k'' = 2}} のとき[[二項定理]]が導かれる）。

== 関連項目 ==
* [[重複組合せ]]
* [[組合せ (数学)]]
* [[順列]]
* [[重複順列]]
* [[置換 (数学)]]
* [[写像12相]]
{{Portal|数学}}

{{DEFAULTSORT:ちようふくちかん}}
[[Category:組合せ論]]
[[Category:置換]]
[[Category:数学に関する記事]]