組合せ問題

質問

組合せの問題です

以下の10個の数字のうち、5個を任意に選んで合計が「19」となる組合せはいくつあるか。

1,1,2,2,3,3,4,4,5,5

これを計算で求めるにはどうしたらよいでしょう？

※
この問題では合計「19」で、選択する数字も10個（重複2個迄）しかありませんが、これが大きい数字となるととても場合分けで上げきれません。

回答No.2

app2358 · ベストアンサー

1がp1個、
2がp2個、
・・・
kがpk個あるとき、
任意のv個を選んで和がsになる組み合わせの数を一般に計算で求めるのは、
しようと思えばできるのでしょうが、ものすごく難しくなると思います。

この手の問題は、工夫すれば数え上げられるように作ってあるので、
数え上げてしまった方がよいと思います。

私がこの問題を解くとしたら、邪道かもしれないですが、まず5個で合計19になるので、平均3.8と考えます。
とすると、4以上の数をまったく使わなければ19には届かないということになります（3×5=15<19）。
もっと具体的に言えば、3以下の数字が1つあるたびに平均は4から0.2ポイント以上ずつ減っていきますので、この場合は少なくとも4が4つ以上入っていないと、合計は19に届きません。（説明がわかりにくくてごめんなさい。）

たとえば、仮に4, 4, 4, 4, 3でやっと19ですよね。

この問題の場合、4は2つしかありませんので、代わりに5を1回は必ず使わないといけないわけです。

ここまで来ればもう簡単で、5を1回使う場合と2回使う場合を数え上げればOKです。

1回の場合は5, 4, 4, 3, 3でないと19に届きません。

2回の場合は
5, 5, 4, 3, 2
5, 5, 4, 4, 1

なので、No.1の方と答えは同じです。

（ちなみに3が3つあって2が1個の場合は5, 5, 3, 3, 3もOKです。）

人によって解き方はさまざまなので、もっといい解き方があるかもしれないです。
（でも計算で求める、っていうのはちょっと難しすぎるかな・・・）

お礼

回答ありがとございます。

やはり計算で求めるのは難しいですよね。
いろいろ調べたのですが「重複組合せ」という考え方が近いのですが、「重複組合せ」は重複に制限がなく、今回のように２回迄とか制約があるとどうなるか難しいようです。

平均値から推測して場合分けを考えるのは参考になりました。
すべての場合分けをしなくてもたどりつけそうです。

回答No.1

nag0720

この問題は、次の３つに分けて計算することができます。
1が１つも選ばれない場合　＝　2,2,3,3,4,4,5,5から5個選んで合計が「19」になる組合せ
1が１つだけ選ばれる場合　＝　2,2,3,3,4,4,5,5から4個選んで合計が「18」になる組合せ
1が２つ選ばれる場合　　　＝　2,2,3,3,4,4,5,5から3個選んで合計が「17」になる組合せ

そしてこれは次のように変えることができます。
1,1,2,2,3,3,4,4から5個選んで合計が「14」になる組合せ
1,1,2,2,3,3,4,4から4個選んで合計が「14」になる組合せ
1,1,2,2,3,3,4,4から3個選んで合計が「14」になる組合せ

このように考えていけば、より簡単な問題に変えることができます。

数式で表すと、
1,1,2,2,3,3,・・・,n,nからm個選んで合計をkにする組み合わせをS(n,m,k)とすると、

S(n,m,k)=S(n-1,m,k-m)+S(n-1,m-1,k-m)+S(n-1,m-2,k-m)

が成り立ちます。

最初の問題は、
S(5,5,19)=S(4,5,14)+S(4,4,14)+S(4,3,14)

となりますが、S(4,4,14)=1、S(4,3,14)=0　などに注意してさらに細分すると、

=S(3,5,9)+S(3,4,9)+S(3,3,9)+1
=1+S(2,4,5)+S(2,3,5)+S(2,2,5)+1
=3

実際の組み合わせは、
1,4,4,5,5
2,3,4,5,5
3,3,4,4,5
の３通りです。

お礼

回答ありがとうございます。

私の理解不足か、S(n,m,k)の計算がよくわかりませんでした。
>S(4,4,14)=1、S(4,3,14)=0
等は実際に手で場合分けてして導かないと分からないような気がして・・

今回は1つの値に対して２つの重複迄ゆるされるのですが、そのS(n,m,k)の中に重複の条件がないので、例えば「1」の個数が2つから３つに変わった場合はどうなるかよくわかりませんでした。

分からないながらも、場合分けしてそれを足し合わせる、というところが参考になりました。

ありがとうございました。