重複組合せの総数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/26 09:19 UTC 版)
詳細は「多重集合係数（英語版）」を参照 定理 ― 正整数 n に対して n 個の元からなる集合に関する k-重複組合せの総数を Hnk と書けば、 H k n = ( n + k − 1 k ) = ( n + k − 1 ) ! k ! ( n − 1 ) ! {\displaystyle H_{k}^{n}={n+k-1 \choose k}={\frac {(n+k-1)!}{k!~(n-1)!}}} すなわち、n + k − 1 個の元に関する k-組合せの総数に等しい。 証明 1 (漸化式を用いる方法) E = {x1, x2, …, xn}とする。E に関する元 x1 を含まない k-重複順列は、{x2, … , xn} に関する k-重複順列であるからその総数は Hn–1k である。一方、x1 を（少なくとも一つ）含む k-重複順列は、E に関する任意の n − 1-重複順列に x1 を一つ付け加えることで得られるから、その総数はHnk–1 である。これら二つで E に関する k-重複組合せは全て数え上げられるから、任意の n > 1 および k > 0 に対して漸化式 H k n = H k − 1 n + H k n − 1 {\displaystyle H_{k}^{n}=H_{k-1}^{n}+H_{k}^{n-1}} が成り立つ。任意の非負整数 k に対して H1k = 1 および正整数 n に対して Hn0 = 1 に注意すれば、n + k に関する帰納法により所期の結果を得る。 証明 2 (単調増大列に帰着する方法) E = {1, 2, …, n}としても一般性を失わない。E に関する k-重複組合せを、a1 ≤ a2 ≤ … ≤ ak なる非減少 k-組と看做すとき、これは b1 = a1 + 0, b2 = a2 + 1, … , bk = ak + k – 1 と置いて得られる k-組を考えることにより、集合 {1, 2, ..., n + k – 1} に関する狭義単調増大 k-組 b1 < b2 < … < bk と一対一に対応する。 後者は n + k − 1 個の元から重複を許すことなく k 個の元を選ぶ組合せに一対一対応するから、その総数 (= Hnk) は二項係数 ( n + k − 1 k ) {\displaystyle {n+k-1 \choose k}} で与えられる。 証明 3 (特定の元が現れる回数を数える方法) 証明 1 と同様に二通りに数える論法（フランス語版） による。 n 個の元からなる集合 E に関する k-重複組合せ Hnk 個を（元の並びとして）全て書き出すと、その一覧には E の元が k × Γnk 個現れることになる。E の元は対称的に現れるから、各々は k × Hnk/n 回現れる。(1) そこで E の元の一つを x と書いて、以下それが現れる回数を計算する。 全部で Hnk 個ある重複組合せのうちで x を（一つでも）含むものの数は Hnk–1 である。実際、x をひとつ取り除いた残りは（重複度込みで、順番を無視して）k – 1 個の元だが、それは（x は重複することができるから、選択肢からは除かれず）E の任意の元から選べる。x を少なくとも一つ含む重複組合せが Hnk–1 個あるということは、x が少なくとも Hnk–1 個は既に現れてることを保証する。(2) 全部で Hnk−1 個ある少なくとも一つ x を含む重複組合せの各々から元 x をひとつ取り除くと、残りは（重複度を込めて）k −1 個の元（これらの元の各々はもはや重複するとは限らない）だから、そのような組合せの一覧には (k – 1)Hnk–1 個の E の元が現れる。E の各元（特に x）は対称的に現れるから、x は (k – 1)Hnk–1/n 回生じる (3). 二通りに数えた方法を比較すると (1) = (2) + (3) であるから k n H k n = H k − 1 n + k − 1 n H k − 1 n {\displaystyle {\frac {k}{n}}H_{k}^{n}=H_{k-1}^{n}+{\frac {k-1}{n}}H_{k-1}^{n}} 隣整理すれば H k n = n + k − 1 k H k − 1 n {\displaystyle H_{k}^{n}={\frac {n+k-1}{k}}H_{k-1}^{n}} を得る。Hn0 = 1 に注意すれば、k に関して帰納的に所期の式を得る。 証明 4 (組分けに帰着する方法) 詳細は「マルと仕切りの論法（英語版）」を参照 n 個の元を 1, 2, …, n として、k-重複組合せを、1 をk1 個、2 を k2 個、と以下同様に（k1 + k2 + … + kn = k となるように取って）作るものとすれば、これは以下のように k 個のマル "●" とn − 1 個の仕切り "|" の並び ●…●k1 個 | ●…●k2 個 | … | ●…●kn 個 で一対一に表すことができる。ここで k 個のマルは互いに区別できないし、n − 1 個の仕切り棒も互いに区別不能であるから、このような「表示」の総数 (= Hnk) は n + k − 1 個の元の重複置換の総数であり、これは多項係数 ( n + k − 1 k , n − 1 ) = ( n + k − 1 ) ! k ! ( n − 1 ) ! {\displaystyle {\binom {n+k-1}{k,\,n-1}}={\frac {(n+k-1)!}{k!~(n-1)!}}} で与えられる。あるいはまた、k 個のマルのはいる「場所」を n + k − 1 箇所から選ぶと考えれば、証明 2 と同様に二項係数 ( n + k − 1 k ) {\displaystyle {n+k-1 \choose k}} によっても数えられる。 重複組合せの総数を計算する最も効果的で単純な方法は、非重複組合せの総数を計算する方法を用いることである（組合せの項を参照）。実際、上で述べたように n 個の元から重複を許して k 個の元を選ぶ組合せの総数は、n + k − 1 個の元から k 個の元を重複を許さずに選ぶ組合せの総数に等しい。 上昇階乗冪による表現 重複組合せの総数は、区別のある n 個の箱に”区別のない” k 枚のカードを入れる（１つの箱に複数枚入れてもよい）ときの場合の数である。まず、区別のある n 個の箱に”区別のある” k 枚のカードを入れる場合の数を求める。ただし箱の中のカードの相対的な位置も区別して数える。１枚目のカードの入れ方は n 通り、2枚目は1枚目のカードの上下どちらに入れるかの選択肢も増えるので入れ方は n + 1 通り、3枚目はさらに選択肢が増え n + 2 通り。結局 k 枚の入れ方の総数は上昇階乗冪 n k ¯ = n ( n + 1 ) ( n + 2 ) ⋯ ( n + k − 1 ) {\displaystyle n^{\overline {k}}=n(n+1)(n+2)\cdots (n+k-1)} である。これは重複組合せの総数に k 枚のカードの順列の総数 k! をかけたものに等しいので、重複組合せの総数は n k ¯ / k ! {\displaystyle n^{\overline {k}}/k!} である。（組合せの総数が下降階乗冪を用いて n k _ / k ! {\displaystyle n^{\underline {k}}/k!} となるのと対をなしている。）
※この「重複組合せの総数」の解説は、「重複組合せ」の解説の一部です。
「重複組合せの総数」を含む「重複組合せ」の記事については、「重複組合せ」の概要を参照ください。
- 重複組合せの総数のページへのリンク
