重複置換
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/13 07:55 UTC 版)
ナビゲーションに移動 検索に移動数学における重複置換（ちょうふくちかん、仏: permutations avec répétition）は、区別不能なものを含む対象を順番を考慮して複数の組に分ける方法を言う（対象は区別できないが、組は区別が付く）。例えば、112, 121, 211 は二つの 1 と一つの 2 を持つ重複置換である。
一部に区別のつかないものを含む n 個の対象を並べ替えて特定の順番に並べるとき、いくつか同じものが生じる場合がある。k ≤ n として、n 個の対象がつくる n-組が k 種類の相異なる組に分けられるとき、その各々が n1, n2, …, nk 個の対象を含む（ただし、n1 + n2 + … + nk =n を満たす）ものを考える。このような n-組のなかで区別不能なものを入れ替えて得られる n-組は同じものと考える。例えば、文字列 MATHÉMATIQUE のアナグラムを全て求めようとするとき、二つの A は区別が付かないのでこれらを入れ替えても文字列としては変わらないが、É と E を入れ替えたときは文字列として相異なる。
重複置換を同じものを含む順列と呼ぶことがある。
定義
位数 k の有限集合 E を E = {x1, x2, …, xk}と書く。n は k ≤ n なる自然数で、n1, n2, …, nk を
- n1 + n2 + … + nk = n
を満たす非負整数とする。このとき、E の元からなる重複度 (n1, n2, …, nk) の n-重複置換とは、E の各元 xi がそれぞれ ni 回現れる n-組（項数 n の有限列）を言う。
例えば
- 重複置換のページへのリンク
