重複組合せ

相異なる（つまり区別可能な）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} で条件

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

を満たすものを言う。

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

$${\displaystyle (\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}}})\qquad (\textstyle \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 への広義単調増大写像全体の成す集合との間に全単射が存在する。

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

$${\displaystyle 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-重複組合せであるからその総数は H n–1
k  である。一方、x₁ を（少なくとも一つ）含む k-重複組合せは、E に関する任意の n − 1-重複組合せに x₁ を一つ付け加えることで得られるから、その総数は H n
k–1  である。これら二つで E に関する k-重複組合せは全て数え上げられるから、任意の n > 1 および k > 0 に対して漸化式

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

が成り立つ[2]。任意の非負整数 k に対して H 1
k  = 1 および正整数 n に対して H n
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 と一対一に対応する[3]。 後者は n + k − 1 個の元から重複を許すことなく k 個の元を選ぶ組合せに一対一対応するから、その総数 (= H n
k ) は二項係数

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

で与えられる。

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

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

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

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

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

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

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

となり、整理すれば

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

を得る。H n
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 個の仕切り棒も互いに区別不能であるから、このような「表示」の総数 (= H n
k ) は n + k − 1 個の元の重複置換の総数であり、これは多項係数

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

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

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

によっても数えられる[5]。

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

上昇階乗冪による表現

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

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

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

• 『重複組合せの公式と例題（玉，整数解の個数）』 - 高校数学の美しい物語
• Michel Hort. "Nombre de combinaisons et d'arrangements avec répétitions limitées". Cite webテンプレートでは|access-date=引数が必須です。 (説明)