重複組合せ

数学の一分野である組合せ論における重複組合せ（ちょうふくくみあわせ、じゅうふくくみあわせ、; 重複選択、"Stars and bars"）とは、取り出した元の並びは考慮しないが、（通常の（非重複）組合せと異なり）同じ元を複数取り出すことが許される「組合せ」を言う。例えば、（通常の）サイコロを10回投げるとき、各出目が何回目に振ったときに出たものか考えなければ、サイコロの出目の「組合せ」となるが、各面のうちには複数回現れるものが存在することになる（たとえば、出目  が1回、 が3回、 が2回、 が4回であるときがその一例である）。

 解釈と表示 
区別可能な 個の元からなる集合  から重複を許して -元を選ぶ組合せ（-重複組合せ）とは、 から連続して  個の元を選ぶ方法であって、選んだ  個の元の順番は考慮せず、かつ複数回同じ元を選ぶことが許されるというものである。これにより、重複する元をも含めて  個の元からなる非順序組が得られる（この非順序組は、重複する元を持たないという集合の定義に反するから集合ではないが、その定義を拡張した多重集合となる）。そこで元  を選ぶ回数（零回でもいい）を  と書けば、 個の元を選ぶことは制約条件  で表せるから、

集合  に全順序関係  を入れて考えるとき、 に関する -重複組合せは、以下のような非減少（つまり広義の増大） -順序組

に対応付けられる。逆に、 の元からなる非減少 -組 , つまり

を満たすものは、 の各元に対してそれがこの -組に現れる回数を割り当てることにより、写像 を定める。これが  

を満たすことは明らかであり、従って  は  に関する -重複組合せである。

従って、 に関する -重複組合せ全体の成す集合と から  への広義単調増大写像全体の成す集合との間に全単射が存在する。

 重複組合せの総数 

重複組合せの総数を計算する最も効果的で単純な方法は、非重複組合せの総数を計算する方法を用いることである（組合せ (数学)を参照）。実際、上で述べたように 個の元から重複を許して 個の元を選ぶ組合せの総数は、 個の元から 個の元を重複を許さずに選ぶ組合せの総数に等しい。

上昇階乗冪による表現
 重複組合せの総数は、区別のある 個の箱に”区別のない” 枚のカードを入れる（1つの箱に複数枚入れてもよい）ときの場合の数である。まず、区別のある 個の箱に”区別のある” 枚のカードを入れる場合の数を求める。ただし箱の中のカードの相対的な位置も区別して数える。１枚目のカードの入れ方は  通り、2枚目は1枚目のカードの上下どちらに入れるかの選択肢も増えるので入れ方は  通り、3枚目はさらに選択肢が増え  通り。結局  枚の入れ方の総数は上昇階乗冪  である。これは重複組合せの総数に  枚のカードの順列の総数  をかけたものに等しいので、重複組合せの総数は  である。（組合せの総数が下降階乗冪を用いて  となるのと対をなしている。）

 その他の重複組合せに同値な数え上げ 
 は多変数多項式に関する全次数  の単位単項式（つまり係数  の単項式）の総数に等しい。

同様に  はシュヴァルツの定理（偏微分は微分する変数の順番に依らず等しい）の成立する 級の 変数函数に対する 階偏導函数の総数に等しい（順番を考慮する必要があるときには  通りである）。

 出典 

 関連項目 

 重複置換
 組合せ (数学)
 写像12相
 重複順列
 順列
 置換 (数学)

 外部リンク 



Category:組合せ論
Category:数学に関する記事