重複組合せ
■重複組合せ《解説》
※順序が違えば別物として数えるのが「順列」,順序だけ違うものは同じものして数えるのが「組合せ
【例】
異なる2つのものa,bから重複を許して3つとる方法
重複組合せ

 
重複順列
{a,a,a}
{a,a,b}
{a,b,b}
{b,b,b}
計4通り
←→
←→
←→
←→
(a,a,a)       1通り
(a,a,b),(a,b,a),(b,a,a)3通り
(a,b,b),(b,a,b),(b,b,a)3通り
(b,b,b)     1通り
計8通り
○ 重複組合せの記号
 異なるn個のものから重複を許してr個とってくる組合せの総数を
nHr
で表します.
(注意)
異なるものが何個(n)あって,それらから何個(r)取ってくるのか,どちらが n でどちらが r かを「慎重に」見極めることが大切

≪表1≫
A3210
B0123
 例えば,2人の人A,Bに同質のお菓子3個を分ける方法の数を数えたいものとする.ただし,どちらかが1つももらわない場合や全部もらってしまう分け方も許されるものとする.
===> いずれも≪表1≫のように4通りになる.

≪表2≫
{A,A,A}
{A,A,B}
{A,B,B}
{B,B,B}

 これは,異なる2人の名前を重複を許して3回呼ぶ場合の数に等しい.(名前が呼ばれたらお菓子がもらえると考える)
===> ≪表2≫のように4通りになる.
※これらは
「異なる2つのものから重複を許して3個取って来る」場合の総数となっており,
「異なる3つのものから重複を許して2個取って来る」場合の総数
≪表3≫
A211000
B010210
C001012
≪表4≫
{A,A} , {A,B} , {A,C} , {B,B} , {B,C} , {C,C}

とは違う.

○ 重複組合せnHrの公式を作るには

1. 重複順列の総数から割り算で求めることはできない
 ▼まず思いつくのは,順列と組合せの対応ですが
 順列 ÷r! → 組合せ
 のように,順列をr!で割ると組合せになりますが,重複順列Πと重複組合せの関係は単純ではありません.
 これは,上の例のように重複組合せの中身ごとに並べ方の総数が変わり,倍率が一定のr!にならないからです.
【例】
異なる2つのものa,bから重複を許して3つとる方法
重複組合せ

 
重複順列
{a,a,a}
{a,a,b}
{a,b,b}
{b,b,b}
計4通り
←→
←→
←→
←→
(a,a,a)       1通り
(a,a,b),(a,b,a),(b,a,a)3通り
(a,b,b),(b,a,b),(b,b,a)3通り
(b,b,b)     1通り
計8通り
 そこで,重複順列から逆算して重複組合せを求めるという方針を推し進めても公式は得られません.

2. 具体例で考える
【例】
 4人の子供に重複を許して5個の同質のボールを分け与える方法

 4人の子供を区別するために,右図のように縦棒|を3個置きます.

 右図のbのように,仕切り棒が隣り合う場合は0個を表すものとします.

 このようにすれば,○5個,|3個同じものがあるときの順列の総数が求める数値となります.
 a=2,b=0,c=2,d=1となる分け方

(縦棒の両側は各々a君,d君のボールです.- - このように,両端を含む4か所を区別するときは,(植木算で!)仕切り棒は4-1=3本です.)
→右上に続く

 《公式にする方法》
 上の答は=56 ですが,しばしば登場するものに,毎回図を書くのは大変なので,通常への読み替え公式を利用します.

 5はボールの数(r)です.3は子供の数(n)-1です.
したがって,この結果は
と表すことができます.
 ところで,分母に登場する2つの数n−1とrの和が分子n+r−1に等しいような式は,いつでもCに直すことができます.
【例】

 そこで,n+r-1 となります.

3. 公式ができた
《HをCに直す公式》
n+r-1C

(-1は植木算になるから)

⇒ この公式を使って,Hが登場したら機械的にCに直してから数字にする
≪植木算:n−1になる理由をしっかり覚えよう!≫

○ 例題と解答
【例1】
 次の値を求めなさい.  4H5

 (答案)
4H5=4+5−1C5=8C5==56・・・(答)
※「5個の同質のボール4人の子供に分ける方法(1つももらえない子供がいるいる場合も含む)」に対応
※「異なる4個のものから重複を許して5個とってくる組合せの総数」と書くと,上記とgiveとtakeが逆に見えますが,まったく同じです.
※「4人の子供の名前を5回呼ぶ方法としても同じ(重複を許してかつ1度も呼ばれない子供がいる場合も含む)」
【例2】
 次の値を求めなさい.  5H3

 (答案)
5H3=5+3−1C3=7C3==35・・・(答)
※「5人の子供3個の同質のお菓子を分ける方法(1つももらえない子供がいるいる場合,全部もらってしまう子供がいる場合も含む)」
※「3個の同質のお菓子5人の子供に分ける方法(1つももらえない子供がいるいる場合,全部もらってしまう子供がいる場合も含む)」

(参考)
○ 重複組合せではnよりもrの方が大きいことがある
※順列の総数nPrや組合せの総数nCrでは,とってくるものの数rn以下でなければなりませんが,重複順列や重複組合せでは,同じものを何回使ってもよいので,重複順列の総数nΠrや重複組合せの総数nHrにおいてはrnよりも大きい場合があります.
≪ありえない≫
3P4
2C5
≪ありえる≫
3Π4=34=81
2H5=6C5=6


○ 重複組合せの記号には,なぜH を使うのか
 次数(掛けてある文字の数)が等しい多項式を「同次多項式」「斉次多項式」という(Homogeneous polynomial).重複組合せは,同次多項式の異なる項の数として登場するので,このHを記号にしたもの.

上の【例】では2つの文字で作られる3次式が何通りあるかを示しています.
(a+b)3を展開してできる同次式の総数は
=aaa+aab+aba+baa+abb+bab+bba+bbb
順序を区別すれば,項の数は「重複順列」
23=8通りになる
=a3+3a2b+3ab2+b3
文字の部分が同じものを同類項として整理すれば,文字の組合わせはa3 , a2b , ab2 ,b32H3=4種類になる

《問題》 左の値に等しいものを,右から選びなさい.
(ルール:左の式を一つクリックし,続けて答をクリックしたとき,合っていれば消えます.
・・・間違ったときは,ヒントを読む場合も読まない場合もやり直すボタンを押せば再開できます.




















■[個別の頁からの質問に対する回答][重複組合せについて/17.8.19]
≪植木算:r−1になる理由をしっかり覚えよう!≫ のところ、題と最終行のnとrが逆だと思います
=>[作者]:連絡ありがとう.おっと,この間違いはダメージが大きい,謝罪の記者会見級です.訂正しました.
■[個別の頁からの質問に対する回答][重複組合せについて/17.5.14]
お世話になっています。 上において質問と回答のところに >問題を選択した時に、背景色が濃く、明暗比が悪いために見づらい の意見があったので私も確認してみました。私にも十分見えますが、選択した場合に背景色が白から青になるのでコントラストの関係で見えにくくなるということではないかと思います。 他の端末や色弱の人にどう見えるかについてはわかりません。 ※なんとなく気になったので意見を送信させていただきました。回答は不要です。
=>[作者]:連絡ありがとう.
■[個別の頁からの質問に対する回答][重複組合せについて/17.5.4]
文系の自分でも良く理解できます 解説がとても分かり易いです。 ただ、重複順列 重複組み合わせの公式で、何故マイナス1なのか、文章からは、理解できません 理由を教えて頂ければうれしいです
=>[作者]:連絡ありがとう.質問・要望は重複順列の頁からですが,内容が重複組合せの頁に関してですので,重複組合せに関する質問として回答します.マイナス1になる理由は,先頭の例で絵を使って述べているように,植木算の考え方でn個のものを区別するにはn−1本の仕切り棒がいるからです.
■[個別の頁からの質問に対する回答][重複組合せについて/17.4.22]
よくわからない
=>[作者]:連絡ありがとう.できれば助けてやりたいと考えていても,どこがどう分からないのかを述べないと,助けようがありません.
■[個別の頁からの質問に対する回答][重複組合せについて/17.3.10]
例題が少ない
=>[作者]:連絡ありがとう.例題は理屈の部分で,重複組合せの総数は組合せの総数に読み替えて解くということさえ分かれば,後は重複組合せを組合せに直す練習をするのみです.問題は10題あります.サブメニューから文章題も選べます.
■[個別の頁からの質問に対する回答][重複組合せについて/16.11.29]
問題を選択した時に、背景色が濃く、明暗比が悪いために見づらい
=>[作者]:連絡ありがとう.そんなことはありません.よく見えます--きっぱり