重複置換

数学における重複置換（ちょうふくちかん、テンプレート:Lang-fr-short）は、区別不能なものを含む対象を順番を考慮して複数の組に分ける方法を言う（対象は区別できないが、組は区別が付く）。例えば、テンプレート:Math は二つのテンプレート:Math と一つのテンプレート:Mvar を持つ重複置換である。

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

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

定義

位数テンプレート:Mvar の有限集合テンプレート:Mvar をテンプレート:Mathと書く。テンプレート:Mvar はテンプレート:Math なる自然数で、テンプレート:Math を

テンプレート:Math

を満たす非負整数とする。このとき、テンプレート:Mvar の元からなる重複度テンプレート:Math のテンプレート:Mvar-重複置換とは、テンプレート:Mvar の各元テンプレート:Mvar がそれぞれテンプレート:Mvar 回現れるテンプレート:Mvar-組（項数テンプレート:Mvar の有限列）を言う。

例えば

\begin{matrix} (\underset{⏟}{x_{1}, \dots, x_{1}}, & \underset{⏟}{x_{2}, \dots, x_{2}}, & \dots, & \underset{⏟}{x_{k}, \dots, x_{k}}) \\ _{n_{1} f o i s} & _{n_{2} f o i s} & _{n_{k} f o i s} \end{matrix}

はその一つである。

重複置換の数え上げ

テンプレート:Main

定理

重複度テンプレート:Math のテンプレート:Mvar-重複置換の総数テンプレート:Math は

p (n_{1}, n_{2}, \dots, n_{k}) = (\binom{n}{n_{1}, n_{2}, \dots, n_{k}}) = \frac{n!}{n_{1}! n_{2}! \dots n_{k}!}

で与えられる。この数は多項係数として知られる。

証明

所期のテンプレート:Mvar-組を作るにはテンプレート:Math 個のテンプレート:Math の位置を決め、テンプレート:Math 個のテンプレート:Math の位置を決め、……、テンプレート:Math 個のテンプレート:Math の位置を決めれば十分である。

テンプレート:Math の入るテンプレート:Math 箇所をテンプレート:Math 箇所から選ぶ方法が $(\binom{n_{1} + n_{2} + \dots + n_{k}}{n_{1}})$ 通り、
テンプレート:Math の入るテンプレート:Math 箇所をテンプレート:Math 箇所から選ぶ方法が $(\binom{n_{2} + \dots + n_{k}}{n_{2}})$ 通り、
…
テンプレート:Math の入るテンプレート:Math 箇所を残りに入れる方法が $(\binom{n_{k}}{n_{k}})$ 通り。

以上をまとめると、

(\binom{n_{1} + n_{2} + \dots + n_{k}}{n_{1}}) (\binom{n_{2} + \dots + n_{k}}{n_{2}}) \dots (\binom{n_{k}}{n_{k}}) = \frac{n!}{n_{1}! n_{2}! \dots n_{k}!}

を得る。

応用

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

(x_{1} + x_{2} + \dots + x_{k})^{n} = \underset{n factors}{\underset{⏟}{(x_{1} + x_{2} + \dots + x_{k}) (x_{1} + x_{2} + \dots + x_{k}) \dots (x_{1} + x_{2} + \dots + x_{k})}}

を、テンプレート:Math なる任意のテンプレート:Mvar についてテンプレート:Mvar 番目の因子から取った項を第テンプレート:Mvar-成分とするテンプレート:Math からなるテンプレート:Mvar-組の積の和の形に展開することを考える。任意のテンプレート:Math に対して、このテンプレート:Mvar-組に現れるテンプレート:Math の個数をテンプレート:Math とするとテンプレート:Math が成り立ち、対応する積は $x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{k}^{n_{k}}$ の形になる。自然数の列テンプレート:Math でテンプレート:Math を満たすものを与えたとき、 $x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{k}^{n_{k}}$ の形の項の総数は重複度テンプレート:Math のテンプレート:Mvar-重複置換の総数に等しい。

こうして多項定理:

(x_{1} + x_{2} + \dots + x_{k})^{n} = \sum_{n_{1} + n_{2} + \dots + n_{k} = n} \frac{n!}{n_{1}! n_{2}! \dots n_{k}!} x_{1}^{n_{1}} x_{2}^{n_{2}} \dots x_{k}^{n_{k}}

を得る（テンプレート:Math のとき二項定理が導かれる）。

重複置換

目次

定義

重複置換の数え上げ

応用

関連項目

ナビゲーションメニュー

重複置換

定義

重複置換の数え上げ

応用

関連項目

ナビゲーション メニュー

検索

ナビゲーションメニュー