数学A 第1章 場合の数 — 重複組合せ

重複組合せについて

重複組合せnHrの定義

の目が描いてある正四面体のさいころを2回振って， 出た目の組（順番は考えない）をすべて書き出すと

の10通りとなる．これは，『同じものを含む順列』の考え方を利用し，次のように計算することができる．

まず，各組は

の順に並べて表すことにする．例えば，

を1個，

を1個使って作られる組は

と表す．この組に対して，さいころの目を表す2個の ○ と，異なる4文字の“しきり”を表す (4−1)=3 個の | からなる順列を，右図のように対応させる． つまり，3つの“しきり” | で4つの場所ができるので，その場所にある ○ の個数が，それぞれさいころの

の個数を表すものとするのである．

例えば，上の10組のうちの，

や

や

などは， ○ と | の順列で右図のように表すことができる．

こうすると，結局，区別しない2個の ○ と区別しない3個の | の計5個のものを並べたときの順列を計算すればよいから， 『同じものを含む順列』より

C(2,3)=5!/2!3!=10 通り

と数えることができる．

ここで， n 個のものから，繰り返し用いることを許して， r 個とって作る組について定義しておこう．

重複組合せnHrの計算

区別する n 個のものから，繰り返し用いることを許して， r 個取り出して作る組の総数 nHr も，先程の例と同じように考えることができる．

まず，右図のように， r 個の ○ と，（ n 個の入る場所を作るための） n−1 個の“しきり” | を並べる． こうしておいてから，区別しない r 個の ○ と区別しない n−1 個の | の計 r+n−1 個のものを並べたときの 『同じものを含む順列』を計算すればよいので

nHr=C(r, n-1)= r+n-1Cr

となる．普通 nHr を計算するには，このように ○ と | の並べ方を考えて r+n−1Cr に帰着してから計算するとよい．

さて，ここでさらに r+n−1Cr の計算をすすめてみると

r+n-1Cr = (r+n-1)!/(n-1)!r! = (r+n-1)(r+n-2)…n^r個の積(n-1)…2・1(n-1)…2・1・r! = n(n+1)…(n+r-2)(n+r-1)^r個の積r(r-1)…2・1

つまり

nHr=n(n+1)…(n+r-2)(n+r-1)^r個の積r(r-1)…2・1

と計算することもできる．この式は， nCr と比較すると覚えやすい．例えば

6C3=下がっていく6・5・43・2・1, 6H3=上がっていく6・7・83・2・1

である．

以上，まとめると

ボールと箱のモデル5

例えば， 5H3 の定義は

「区別する5個のものから，繰り返し用いることを許して，3個とりだしてつくる組の総数」

であったが，これはボールと箱のモデルを使って

「区別しない3個のボールを，区別する5個の箱に配る(何個でもよい)場合の総数」

といいかえることができる．それには，次のように考えるとよい．

準備として，ボールは区別しないので，それを ○,○,○ とし， 箱は区別するので番号をつけ，それを

としておく．

例えば，区別しない3個のボールを，区別する5個の箱に，図のように配ったとする．

このときは，5−3重複組合せのうちの {2,2,5} と対応すると考えることができる．

また逆に，5−3重複組合せのうちの {2,2,5} は，図のようなボールの配り方に対応すると考えることができる．

これ以外の5−3重複組合せも，ボールの箱への配り方と1対1に対応するので， 結局，ボールの箱への配り方の総数は 5H3 と一致するといえる．

一般に，次のようにまとめることができる．

最終更新: 2026-08-10