組み合わせの質問です

質問

こんにちは、組み合わせ論は趣味です。
さて、次のような問題の一般解は、どのように求めるのか、あるいは、どのような呼び方（例、数珠順列）をするのか、教えていただけませんか。

例題：『A色 ２個、Ｂ色 ３個、C色 ５個のあわせて１０個の玉がある。ここから、４個を取り出す場合、何通りあるか。1個も取り出されない色があっても良い。』

上記はあくまで例であり、『色の種類数がｋ種類、それぞれr1個、r2個、・・・、rk個の玉から、m個を取り出す場合』が知りたいことです。

完全回答でなくても、ヒントになるような考え方が分かるとうれしいです。
どうぞよろしくお願いいたします。

回答No.5

nag0720 · ベストアンサー

式の意味は理解されたようですね。

これを無理やり一般形にするとしたら、

r1,r2,・・・,rkのうち、mより少ない個数がs種類あり、それをr1,r2,・・・,rsとすれば、

Σ[n=0～s](-1)^nΣ[p∈P(n)]kH(m-R(p)-n)

となるのかな。

ただし、P(n)はs種類の色からn種類選ぶ組み合わせの集合、
R(p)は選んだ種類の個数の合計とします。

例えば、s=3のとき、
P(0)={}
P(1)={(1),(2),(3)}
P(2)={(1,2),(1,3),(2,3)}
P(3)={(1,2,3)}

R()=0
R(1)=r1
R(2)=r2
R(3)=r3
R(1,2)=r1+r2
・・・・

計算量は、2^s個の重複組み合わせの加減算になりますね。

お礼

nag0720さん、ありがとうございました。
定式化まで、無事つれてきていただきました。
ここまでくれば、多倍長計算にて、実際の計算ができそうです。

ネットってすばらしいですね。

回答No.4

nag0720

ちょっと考察してみました。

r1≦r2≦・・・≦rk　とします。

m≦r1≦r2≦・・・≦rk　の場合は、組合せの数は重複組合せで、kＨm

r1＜m≦r2≦r3≦・・・≦rk　の場合は、
r1=mと仮定すれば、組み合わせの数は、kＨm
そこから超過した分を引けばいいから、
kＨm - kＨ(m-r1-1)

r1≦r2＜m≦r3≦・・・≦rk　の場合は、
r1=r2=mと仮定すれば、組み合わせの数は、kＨm
そこから超過した分を引いて、
kＨm - { kＨ(m-r1-1) + kＨ(m-r2-1) - kＨ(m-r1-r2-2) }
（この式はちょっと怪しいけどたぶんこんな感じになるでしょう）

r1≦r2≦r3＜m≦r4≦・・・≦rk　の場合も同じようにして計算すればいいんですが、とりあえずここまで。

ちなみに、m個取ることとm個残すことは同じだから、
mを(r1+r2+・・・+rk)-mに置き換えることができます。

A色2個、B色3個、C色5個から4個取りだす場合をこの式に適用すると、
r1≦r2≦＜m≦r3　だから、
3Ｈ4 - { 3Ｈ(4-2-1) + 3Ｈ(4-3-1) - 3Ｈ(4-2-3-2) }
= 3Ｈ4 - { 3Ｈ1 + 3Ｈ0 }
= 6C4 - { 3C1 + 2C0 }
= 15 - { 3 + 1 }
= 11

補足

すばらしい。定式化が見えてきた気がします。

ご返答を自分に分かるように書いてみたいと思います。

(1)m≦r1≦・・・の場合
・これは、m個取り出すときに制限がないことを表しますね。
・よって『k色の玉が無数にあり、そこからm個取り出す場合』という重複組み合わせの一般例に置き換わります。
・この回答は、『m個の玉とk-1個の仕切りの合計m+k-1個の並べ方数』となり、
(m+k-1)!/m!(k-1)! == (m+k-1)Cm == kHm　ですね。

(2)r1＜m≦r2・・・・の場合
・｛１色目がr1個以内の場合数｝＝｛１色目の玉数に制限がない場合数｝－｛１色目がr1個超過の場合数｝、ということですね。
・前項は、無制限なので先の(1)と同じ場合数。
・後項は、『m個のうち、先に１色目にr1+1個を割り当てる。残りのm-(r1+1)個をk色から取り出す場合数』となりますね。
・よって、kH(m-r1-1)に等しくなる。

(3)r1≦r2＜m≦r3≦・・・の場合
・集合演算の考え方ですね。図で書くとわかりやすいのですがね。
・｛１色目がr1個以内、かつ２色目がr2個以内の場合数｝
　＝｛玉数に制限がない場合数｝
　　－｛１色目がr1個超過の場合数｝－｛２色目がr2個超過の場合数｝＋｛１色目がr1個超過し、かつ２色目もr2個超過した場合数｝
・この最後の項は、『２項目と３項目で２回引かれているので、加算している』という意味ですね。
・２項目、３項目は、(2)と同じ式。
・最後の項は、先ほどと同じように考えるとととして、『m個のうち、先に１色目にr1+1個を、２色目にr2+1個を割り当てる。残りのm-(r1+1)-(r2+1)個をk色から取り出す場合数』となりますね。
・よって、最終項＝kH{m-(r1+1)-(r2+1)｝ですね。

後は、集合の重なり組み合わせの爆発はありますが、これの繰り返しということですね。

これで、答えが見えた気がします。（質問者）

回答No.3

B-juggler

Ｎｏ．１です。補足ありがとうです＾＾；

「定式化が可能かどうか」？

おそらく不可能でしょうね。
理由は　場合わけが必要になりますから。

例えばこうしますね。
Ａ：２個　Ｂ：３個　Ｃ：５個　で４個取り出す。

→　Ａのキャパ：２個　同Ｂ：３　同Ｃ：５　として　４個を振り分ける。

Ａに二つ入る場合；残りＢ，Ｃ各１個　ｏｒ　Ｂに２個　ｏｒ　Ｃに２個
　つまりこの場合は三通りあります。

Ａのキャパ　を替えて、３つにすると？
Ａに三つ入る場合；残り一つ　Ｂ一つ　ｏｒ　Ｃ一つ　の二通り。

Ａのキャパは　ｒ１　のことですから、変わってくるわけですね。

ここで場合わけが必要で、ほかのやり方では不可能かと思いますよ。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

例えばだけど、　ｒ１，ｒ２，・・・・・，ｒｋ＞ｍ　なら　定式化どころか、
引く必要がないので、簡単ですが・・・＾＾；

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

回答No.2

nag0720

色の種類数がｋ種類、それぞれr1個、r2個、・・・、rk個の玉から、m個を取り出す場合

これは単純な式で求めることはできないでしょう。

k=2で、r1≦r2とした場合でさえ、
　0≦m≦r1のとき、m+1通り
　r1≦m≦r2のとき、r1+1通り
　r2≦m≦r1+r2のとき、r1+r2-m+1通り
と、r1,r2,r1+r2とmとの大小関係によって答えが違ってきます。

k=3になると、r1,r2,r3,r1+r2+r3とmとの大小関係だけでなく、r1+r2とr3の大小関係も影響してきて、かなり複雑になります。

A色2個、B色3個、C色5個から4個取りだす場合は、
Aが0個のとき、4通り
Aが1個のとき、4通り
Aが2個のとき、3通り
計11通りと、種類を１つ減らして数える。

k種類の場合は、同じようにして種類を１つずつ減らしながら数えていくしかないでしょうね。

補足

ありがとうございます。やはり難問ですか。。(-_-;)

ご回答拝見し、こんな風にも置き換えられるかと思いました。
『x1+x2+...+xk=mを満たす、k個の自然数x1,x2,...,xkの解はいくつあるか。ここでmは整数（0<m)とし、r個の自然数r1,...,rkについて、0<=x1<=r1、...、0<=xk<=rkとする。（必要なら、0<r1<=r2<=...<=rkとの制約つけてよい）

k=mなら簡単なんですけどねぇ。（質問者）

回答No.1

B-juggler

う～ん、えっと。こんにちは。

これはこう読み替えてもいいですよね？
「Ａ、Ｂ、Ｃの三つの箱がある。Ａには２個、Ｂには３個、Ｃには５個ボールが入る。
このとき、４個のボールを箱に入れるとき、詰め方は何通りになるか？
ただし空箱があっても良いものとする」

これだと、結構楽に行けますね・・・。面倒か・・・。

Ａに二つ入ると、もう入らないから、ＢとＣに振り分けることになりますし、

Ｂに三つ入ると、ＡとＣにどっちか入るわけですね。

入らない分をどう解釈する勝手だけで、３＾４から引いていく形を取ると思いますよ。
　＃重複が厄介ですけれど。

（ボールの行き先の箱３通り）＾（ボールの個数）＝３＾４　ですね。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

補足

その、重複の数こそが、問題点です。
そこを、定式化できるでしょうか？（質問者より）