重複組合せ

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

解釈と表示

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

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

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

を満たすものを言う。

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

(\underbrace {x_{1},\cdots ,x_{1}} _{f(x_{1}){\text{ elements}}},\underbrace {x_{2},\cdots ,x_{2}} _{f(x_{2}){\text{ elements}}},\cdots ,\underbrace {x_{n},\cdots ,x_{n}} _{f(x_{n}){\text{ elements}}})\qquad (\textstyle \sum \limits _{i}f(x_{i})=k)

に対応付けられる。逆に、 $E$ の元からなる非減少 $k$ -組 $(a 1, a 2, \dots, a k)$ , つまり

a 1 \leq a 2 \leq \dots \leq a k

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

f (x 1) + f (x 2) + \dots + f (x n) = k

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

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

重複組合せの総数

詳細は「多重集合係数（英語版）」を参照

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

{\text{H}}_{k}^{n}={\binom {n+k-1}{k}}={\frac {(n+k-1)!}{k!~(n-1)!}}

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

証明 1（漸化式を用いる方法）

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

{\text{H}}_{k}^{n}={\text{H}}_{k-1}^{n}+{\text{H}}_{k}^{n-1}

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

証明 2（単調増大列に帰着する方法）

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

b 1 = a 1 + 0, b 2 = a 2 + 1, \dots, b k = a k + k - 1

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

{\binom {n+k-1}{k}}

で与えられる。

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

証明 1 と同様に2通りに数える論法（フランス語版）^[4]による。

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

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

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

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

{\frac {k}{n}}{\text{H}}_{k}^{n}={\text{H}}_{k-1}^{n}+{\frac {k-1}{n}}{\text{H}}_{k-1}^{n}

となり、整理すれば

{\text{H}}_{k}^{n}={\frac {n+k-1}{k}}{\text{H}}_{k-1}^{n}

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

証明 4（組分けに帰着する方法）

詳細は「マルと仕切りの論法（英語版）」を参照

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

| | … |

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

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

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

{\binom {n+k-1}{k}}

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

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

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