100円と500円硬貨で1000円を支払う方法は、

　　1．500円玉2枚　　、2．500円玉1枚と100円玉5枚　　、3．100円玉10枚

以上の3通り可能。では、10円、50円、100円硬貨で1000円を支払う方法は？

　また、1、5、10、50、100、500円硬貨で1000円を支払う方法は？

　もちろん硬貨の中には使用しない種類があっても構わないものとして、それぞれの硬貨は
十分多くあるものとする。


　らすかるさんからのコメントです。（平成２７年９月２８日付け）

・　1円硬貨でn円を表す方法は1通り　→　5n円を表す方法も1通り

・　1円硬貨と5円硬貨で5n円を表す方法は、Σ[k=0〜n]1=n+1通り
　→ 10n円を表す方法は、Σ[k=0〜2n]1=2n+1通り

・　1円硬貨と5円硬貨と10円硬貨で10n円を表す方法は、Σ[k=0〜n](2k+1)=(n+1)²通り
　→ 50n円を表す方法は、Σ[k=0〜5n](2k+1)=(5n+1)²通り

・　1円硬貨と5円硬貨と10円硬貨と50円硬貨で50n円を表す方法は、
　Σ[k=0〜n](5k+1)²=(n+1)(50n²+55n+6)/6通り
　→ 100n円を表す方法は(2n+1){50(2n)²+55(2n)+6}/6=(2n+1)(100n²+55n+3)/3通り

・　1円硬貨と5円硬貨と10円硬貨と50円硬貨と100円硬貨で100n円を表す方法は、
　Σ[k=0〜n](2k+1)(100k²+55k+3)/3=(n+1)(100n³+240n²+131n+6)/6通り
　→ 500n円を表す方法は、(5n+1){100(5n)³+240(5n)²+131(5n)+6}/6
　　　= (5n+1)(12500n³+6000n²+655n+6)/6通り

・　1円硬貨と5円硬貨と10円硬貨と50円硬貨と100円硬貨と500円硬貨で500n円を表す方法
　は、Σ[k=0〜n](5k+1)(12500k³+6000k²+655k+6)/6
　　　= (n+1)(12500n⁴+29375n³+15800n²-195n+6)/6通り

　よって、1、5、10、50、100、500円硬貨で1000円を支払う方法は、n=2を代入して248908通り

　10円、50円、100円硬貨で1000円を支払う方法は、1円、5円、10円硬貨で100円を支払う方
法と同じなので、上の途中式から、(n+1)²でn=10として121通り


（コメント）　問題の前半部分について考えてみました。

　ｘ、ｙ、ｚ を０以上の整数として、求める場合の数は、方程式 ｘ＋５ｙ＋１０ｚ＝１００　の解の
個数である。明らかに、０≦ｚ≦１０　なので、

・　ｚ＝０　のとき、ｘ＋５ｙ＝１００　より、０≦ｙ≦２０　なので、解は、２１通り
・　ｚ＝１　のとき、ｘ＋５ｙ＝９０　より、０≦ｙ≦１８　なので、解は、１９通り
・　ｚ＝２　のとき、ｘ＋５ｙ＝８０　より、０≦ｙ≦１６　なので、解は、１７通り
・　ｚ＝３　のとき、ｘ＋５ｙ＝７０　より、０≦ｙ≦１４　なので、解は、１５通り
・　ｚ＝４　のとき、ｘ＋５ｙ＝６０　より、０≦ｙ≦１２　なので、解は、１３通り
・　ｚ＝５　のとき、ｘ＋５ｙ＝５０　より、０≦ｙ≦１０　なので、解は、１１通り
・　ｚ＝６　のとき、ｘ＋５ｙ＝４０　より、０≦ｙ≦８　なので、解は、９通り
・　ｚ＝７　のとき、ｘ＋５ｙ＝３０　より、０≦ｙ≦６　なので、解は、７通り
・　ｚ＝８　のとき、ｘ＋５ｙ＝２０　より、０≦ｙ≦４　なので、解は、５通り
・　ｚ＝９　のとき、ｘ＋５ｙ＝１０　より、０≦ｙ≦２　なので、解は、３通り
・　ｚ＝１０　のとき、ｘ＋５ｙ＝０　より、ｘ＝０、ｙ＝０　なので、解は、１通り

　以上から、

　　１＋３＋５＋７＋９＋１１＋１３＋１５＋１７＋１９＋２１＝１１（１＋２１）/２＝１２１（通り）