組み合わせの問題です。

質問

（１）1円、5円、10円の硬貨をとりまぜて合計10n円にするしかたは(n+1)^2通りであることを証明せよ。n:整数です。
（２）さらに50円玉を加えて合計1000円にするしかたは何通りあるか？

という問題なんですけど、10円玉一枚、5円玉二枚、五円玉一枚＋1円玉五枚、1円玉十枚に分けてみたんですけど重複がでちゃって・・・

どなたか回答お願いします！！

回答No.1

postro · ベストアンサー

（１）1円、5円、10円の硬貨をとりまぜて合計10n円にするしかたは(n+1)^2通りであることを証明せよ。n:整数です。
１０円をｎ枚使う・・・１通り
１０円をｎ-1枚使う・・・３通り（５円を２，１，０枚使う）
１０円をｎ-２枚使う・・・５通り（５円を４，３，２，１，０枚使う）
・・・
１０円をｎ-ｋ枚使う・・・２ｋ+１通り（５円を２ｋ、・・・４，３，２，１，０枚使う）
・・・
１０円をｎ-ｎ枚使う・・・２ｎ+１通り（５円を２ｎ、・・・４，３，２，１，０枚使う）
全部で　Σ(k=0～n）｛２ｋ+１｝＝(n+1)^2 となる

（２）さらに50円玉を加えて合計1000円にするしかたは何通りあるか？
５０円を２０枚使う・・・１通り
５０円を２０-1枚使う・・・（５+１）＾２通り　1円、5円、10円の硬貨をとりまぜて合計１０＊５円払う
・・・
５０円を２０-ｋ枚使う・・・（ｋ+１）＾２通り　1円、5円、10円の硬貨をとりまぜて合計１０＊５ｋ円払う
・・・
５０円を２０-２０枚使う・・・（１００+１）＾２通り
全部で　Σ(k=0～20）｛５ｋ+１｝^2 となる

お礼

ありがとうございます。お礼遅くなってごめんなさい。助かりました。

回答No.3

postro

＃１です。訂正です。
誤：　５０円を２０-ｋ枚使う・・・（ｋ+１）＾２通り　1円、5円、10円の硬貨をとりまぜて合計１０＊５ｋ円払う
正：　５０円を２０-ｋ枚使う・・・（５ｋ+１）＾２通り　1円、5円、10円の硬貨をとりまぜて合計１０＊５ｋ円払う
ついでに計算間違いがなければ　Σ(k=0～20）｛５ｋ+１｝^2=73871

回答No.2

age_momo

(1)もっとスマートな考え方があると思うのですが手っ取り早く
やっつけるなら、

今、1円と5円玉で10k円にする組み合わせを考えます。(0≦k≦n)
ここで5円玉の枚数は
0,2,・・・,2k-1,2k
(2k+1)通り有ります。この時、1円玉は1通りです。
また、この状態で10n円にする10円玉の選び方も1通りです。
よって組み合わせ方は
Σ[k=0→n](2k+1)=(n+1)^2

(2)(1)を踏まえると50円玉は0枚から20枚まであり、m枚の時には
10,5,1円玉の組み合わせは
{(1000-50m)/10+1}^2=(101-5m)^2

よって組み合わせは

Σ[m=0→20](101-5m)^2=Σ[m=0→20](10201-1010m+25m^2)
=10201*Σ[m=0→20]1-1010*Σ[m=0→20]m+25*Σ[m=0→20]m^2
=10201*21-1010*20*21/2+20*21*41/6=73871

お礼

遅くなってごめんなさい。回答ありがとうございます。助かりました。