Loading AI tools
ウィキペディアから
数学の一分野である組合せ論における重複組合せ(ちょうふくくみあわせ、じゅうふくくみあわせ、英: combination with repetition, multi-choose; 重複選択、"Stars and bars")とは、取り出した元の並びは考慮しないが、(通常の(非重複)組合せと異なり)同じ元を複数取り出すことが許される「組合せ」を言う。例えば、(通常の)サイコロを10回投げるとき、各出目が何回目に振ったときに出たものか考えなければ、サイコロの出目の「組合せ」となるが、各面のうちには複数回現れるものが存在することになる(たとえば、出目 2 が1回、4 が3回、5 が2回、6 が4回であるときがその一例である)。
区別可能な n個の元からなる集合 E = {x1, x2, …, xn} から重複を許して k-元を選ぶ組合せ(k-重複組合せ)とは、E から連続して k 個の元を選ぶ方法であって、選んだ k 個の元の順番は考慮せず、かつ複数回同じ元を選ぶことが許されるというものである。これにより、重複する元をも含めて k 個の元からなる非順序組が得られる(この非順序組は、重複する元を持たないという集合の定義に反するから集合ではないが、その定義を拡張した多重集合となる)。そこで元 xi を選ぶ回数(零回でもいい)を f(xi) と書けば、k 個の元を選ぶことは制約条件 f(x1) + f(x2) + … + f(xn) = k で表せるから、
定義 ― 位数(濃度)n の有限集合 E に関する k-重複組合せとは、E から {0, 1, …, k} への写像 f: E → {0, 1, …, k} で条件
を満たすものを言う。
集合 E = {x1, x2, …, xn} に全順序関係 x1 < x2 < … < xn を入れて考えるとき、E に関する k-重複組合せは、以下のような非減少(つまり広義の増大) k-順序組
に対応付けられる。逆に、E の元からなる非減少 k-組 (a1, a2, …, ak), つまり
を満たすものは、E の各元に対してそれがこの k-組に現れる回数を割り当てることにより、写像 f: E → {0, 1, …, k} を定める。これが
を満たすことは明らかであり、従って f は E に関する k-重複組合せである。
従って、E に関する k-重複組合せ全体の成す集合と {1, 2, …, k} から E への広義単調増大写像全体の成す集合との間に全単射が存在する。
E = {x1, x2, …, xn} とする。E に関する元 x1 を含まない k-重複組合せは、{x2, … , xn} に関する k-重複組合せであるからその総数は
である。一方、x1 を(少なくとも1つ)含む k-重複組合せは、E に関する任意の n − 1-重複組合せに x1 を1つ付け加えることで得られるから、その総数は Hn
k−1 である。これら2つで E に関する k-重複組合せは全て数え上げられるから、任意の n > 1 および k > 0 に対して漸化式
が成り立つ[2]。任意の非負整数 k に対して H1
k = 1 および正整数 n に対して Hn
0 = 1 に注意すれば、n + k に関する帰納法により所期の結果を得る。
証明 1 と同様に2通りに数える論法[4]による。
n 個の元からなる集合 E に関する k-重複組合せ Hn
k 個を(元の並びとして)全て書き出すと、その一覧には E の元が k × Hn
k 個現れることになる。E の元は対称的に現れるから、各々は k × Hn
k / n 回現れる。(1)
そこで E の元の一つを x と書いて、以下それが現れる回数を計算する。
2通りに数えた方法を比較すると (1) = (2) + (3) であるから
となり、整理すれば
を得る。Hn
0 = 1 に注意すれば、k に関して帰納的に所期の式を得る。
n 個の元を 1, 2, …, n として、k-重複組合せを、1 をk1 個、2 を k2 個、と以下同様に(k1 + k2 + … + kn = k となるように取って)作るものとすれば、これは以下のように k 個のマル "●" とn − 1 個の仕切り "|" の並び
で一対一に表すことができる。ここで k 個のマルは互いに区別できないし、n − 1 個の仕切り棒も互いに区別不能であるから、このような「表示」の総数 (= Hn
k) は n + k − 1 個の元の重複置換の総数であり、これは多項係数
で与えられる[2]。あるいはまた、k個のマルの入る「場所」を n + k − 1 箇所から選ぶと考えれば、証明 2 と同様に二項係数
によっても数えられる[5]。
重複組合せの総数を計算する最も効果的で単純な方法は、非重複組合せの総数を計算する方法を用いることである(組合せ (数学)を参照)。実際、上で述べたように n個の元から重複を許して k個の元を選ぶ組合せの総数は、n + k − 1 個の元から k個の元を重複を許さずに選ぶ組合せの総数に等しい。
Hn
k は多変数多項式に関する全次数 k の単位単項式(つまり係数 1 の単項式)の総数に等しい。
同様に Hn
k はシュヴァルツの定理(偏微分は微分する変数の順番に依らず等しい)の成立する Ck級の n変数函数に対する k階偏導函数の総数に等しい(順番を考慮する必要があるときには nk 通りである)。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.