重複組合せ

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

解釈と表示

相異なる（つまり区別可能な）n 個の元からなる集合 E = {x₁, x₂, …, x_n}から重複を許して k-元を選ぶ組合せ（k-重複組合せ）とは、E から連続して k 個の元を選ぶ方法であって、選んだ k 個の元の順番は考慮せず、かつ複数回同じ元を選ぶことが許されるというものである。これにより、重複する元をも含めて k 個の元からなる非順序組が得られる（この非順序組は、重複する元を持たないという集合の定義に反するから集合ではないが、その定義を拡張した多重集合となる）。そこで元 x_i を選ぶ回数（零回でもいい）を f(x_i) と書けば、k 個の元を選ぶことは制約条件 f(x₁) + f(x₂) + … + f(x_n) = k で表せるから、

定義 ― 位数（濃度）n の有限集合 E に関する k-重複組合せとは、E から {0, 1, …, k} への写像 f: E → {0, 1, …, k} で条件

$\sum _{x\in E}f(x)=k$

を満たすものを言う。

集合 E = {x₁, x₂, … , x_n}に全順序関係 x₁ < x₂ < … < x_n を入れて考えるとき、E に関する k-重複組合せは、以下のような非減少（つまり広義の増大） k-順序組

$(\underbrace {x_{1},\ldots ,x_{1}} _{f(x_{1}){\text{ elements}}},\underbrace {x_{2},\ldots ,x_{2}} _{f(x_{2}){\text{ elements}}},\ldots ,\underbrace {x_{n},\ldots ,x_{n}} _{f(x_{n}){\text{ elements}}})\quad (\sum _{i}f(x_{i})=k)$

に対応付けられる。逆に、E の元からなる非減少 k-組 (a₁, a₂, … , a_k), つまり

a₁ ≤ a₂ ≤ … ≤ a_k

を満たすものは、E の各元に対してそれがこの k-組に現れる回数を割り当てることにより、写像 f: E → {0, 1, …, k}; を定める。これが

f(x₁) + f(x₂) + … + f(x_n) = k

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

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

重複組合せの総数

→詳細は「多重集合係数」を参照

定理 ― 非負整数 n に対して n 個の元からなる集合に関する k-重複組合せの総数を Hn
k と書けば、

$H_{k}^{n}={n+k-1 \choose k}={\frac {(n+k-1)!}{k!~(n-1)!}},$

すなわち、n + k − 1 個の元に関する k-組合せの総数に等しい。

証明 1 (漸化式を用いる方法)

E = {x₁, x₂, …, x_n}とする。E に関する元 x₁ を含まない k-重複順列は、{x₂, … , x_n} に関する k-重複順列であるからその総数は Hn–1
k である。一方、x₁ を（少なくとも一つ）含む k-重複順列は、E に関する任意の n − 1-重複順列に x₁ を一つ付け加えることで得られるから、その総数はHn
k–1 である。これら二つで E に関する k-重複組合せは全て数え上げられるから、任意の n > 1 および k > 0 に対して漸化式

$H_{k}^{n}=H_{k-1}^{n}+H_{k}^{n-1}$

が成り立つ。任意の非負整数 k に対して H1
k = 1 および正整数 n に対して Hn
0 = 1 に注意すれば、n + k に関する帰納法により所期の結果を得る。

証明 2 (単調増大列に帰着する方法)

E = {1, 2, …, n}としても一般性を失わない。E に関する k-重複組合せを、a₁ ≤ a₂ ≤ … ≤ a_k なる非減少 k-組と看做すとき、これは

b₁ = a₁ + 0, b₂ = a₂ + 1, … , b_k = a_k + k – 1

と置いて得られる k-組を考えることにより、集合 {1, 2, ..., n + k – 1} に関する狭義単調増大 k-組 b₁ < b₂ < … < b_k と一対一に対応する。 後者は n + k − 1 個の元から重複を許すことなく k 個の元を選ぶ組合せに一対一対応するから、その総数 (= Hn
k) は二項係数

${n+k-1 \choose k}$

で与えられる。

証明 3 (特定の元が現れる回数を数える方法)

証明 1 と同様に二通りに数える論法 による。

n 個の元からなる集合 E に関する k-重複組合せ Hn
k 個を（元の並びとして）全て書き出すと、その一覧には E の元が k × Γ_n^k 個現れることになる。E の元は対称的に現れるから、各々は k × Hn
k/n 回現れる。(1)

そこで E の元の一つを x と書いて、以下それが現れる回数を計算する。

• 全部で Hn
  k 個ある重複組合せのうちで x を（一つでも）含むものの数は Hn
  k–1 である。実際、x をひとつ取り除いた残りは（重複度込みで、順番を無視して）k – 1 個の元だが、それは（x は重複することができるから、選択肢からは除かれず）E の任意の元から選べる。x を少なくとも一つ含む重複組合せが Hn
  k–1 個あるということは、x が少なくとも Hn
  k–1 個は既に現れてることを保証する。(2)
• 全部で Hn
  k−1 個ある少なくとも一つ x を含む重複組合せの各々から元 x をひとつ取り除くと、残りは（重複度を込めて）k −1 個の元（これらの元の各々はもはや重複するとは限らない）だから、そのような組合せの一覧には (k – 1)Hn
  k–1 個の E の元が現れる。E の各元（特に x）は対称的に現れるから、x は (k – 1)Hn
  k–1/n 回生じる (3).

二通りに数えた方法を比較すると (1) = (2) + (3) であるから

${\frac {k}{n}}H_{k}^{n}=H_{k-1}^{n}+{\frac {k-1}{n}}H_{k-1}^{n}$

隣整理すれば

$H_{k}^{n}={\frac {n+k-1}{k}}H_{k-1}^{n}$

を得る。Hn
0 = 1 に注意すれば、k に関して帰納的に所期の式を得る。

証明 4 (組分けに帰着する方法)

→詳細は「マルと仕切りの論法」を参照

n 個の元を 1, 2, …, n として、k-重複組合せを、1 をk₁ 個、2 を k₂ 個、と以下同様に（k₁ + k₂ + … + k_n = k となるように取って）作るものとすれば、これは以下のように k 個のマル "●" とn − 1 個の仕切り "|" の並び

●…●k₁ 個 | ●…●k₂ 個 | … | ●…●k_n 個

で一対一に表すことができる。ここで k 個のマルは互いに区別できないし、n − 1 個の仕切り棒も互いに区別不能であるから、このような「表示」の総数 (= Hn
k) は n + k − 1 個の元の重複置換の総数であり、これは多項係数

${\binom {n+k-1}{k,\,n-1}}={\frac {(n+k-1)!}{k!~(n-1)!}}$

で与えられる。あるいはまた、k 個のマルのはいる「場所」を n + k − 1 箇所から選ぶと考えれば、証明 2 と同様に二項係数

${n+k-1 \choose k}$

によっても数えられる。

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

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

Hn
k は 多変数多項式 に関する全次数 k の単位単項式（つまり係数 1 の単項式）の総数に等しい。

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

関連項目

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

外部リンク

• 『{{{2}}}』 - 高校数学の美しい物語
• Michel Hort. "Nombre de combinaisons et d'arrangements avec répétitions limitées". {{cite web}}: Cite webテンプレートでは|access-date=引数が必須です。 (説明)