重複組合せ

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

解釈と表示

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

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

$(\underset{f(x_1)\text{ elements}}{\underbrace{x_1,\cdots ,x_1}},\underset{f(x_2)\text{ elements}}{\underbrace{x_2,\cdots ,x_2}},\cdots ,\underset{f(x_n)\text{ elements}}{\underbrace{x_n,\cdots ,x_n}})(\sum _{i}f(x_i)=k)$

に対応付けられる。逆に、テンプレート:Mvar の元からなる非減少 テンプレート:Mvar-組 テンプレート:Math, つまり

テンプレート:Math2

を満たすものは、テンプレート:Mvar の各元に対してそれがこの テンプレート:Mvar-組に現れる回数を割り当てることにより、写像 テンプレート:Math2を定める。これが

テンプレート:Math

を満たすことは明らかであり、従って テンプレート:Mvar は テンプレート:Mvar に関する テンプレート:Mvar-重複組合せである。

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

重複組合せの総数

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

上昇階乗冪による表現

重複組合せの総数は、区別のある テンプレート:Mvar個の箱に”区別のない” テンプレート:Mvar枚のカードを入れる（1つの箱に複数枚入れてもよい）ときの場合の数である。まず、区別のある テンプレート:Mvar個の箱に”区別のある” テンプレート:Mvar枚のカードを入れる場合の数を求める。ただし箱の中のカードの相対的な位置も区別して数える。１枚目のカードの入れ方は テンプレート:Mvar 通り、2枚目は1枚目のカードの上下どちらに入れるかの選択肢も増えるので入れ方は テンプレート:Math 通り、3枚目はさらに選択肢が増え テンプレート:Math2 通り。結局 テンプレート:Mvar 枚の入れ方の総数は上昇階乗冪 $n^{\bar{k}}=n(n+1)(n+2)\cdots (n+k-1)$ である。これは重複組合せの総数に テンプレート:Mvar 枚のカードの順列の総数 テンプレート:Mvar をかけたものに等しいので、重複組合せの総数は $n^{\bar{k}}/k!$ である。（組合せの総数が下降階乗冪を用いて $n^{\underset{\_}{k}}/k!$ となるのと対をなしている。）

その他の重複組合せに同値な数え上げ

テンプレート:Math は多変数多項式に関する全次数 テンプレート:Mvar の単位単項式（つまり係数 テンプレート:Math の単項式）の総数に等しい。

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

関連項目

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

外部リンク

• テンプレート:高校数学の美しい物語
• テンプレート:Cite web