重複組合せ

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

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

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

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

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

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

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

重複組合せの総数

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

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

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

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

出典

重複組合せ

Źródło i licencja