［Ｑ］１円，５円，１０円，５０円の4種類の硬貨で１００円を両替するには何通りの仕方があるか？

両替する方法を考えるのであるが，直角三角形内や格子直角三角錐内の格子点の個数に対応する問題である．これくらいの数であれば，しらみ潰しに数え上げた方が着実であるといえるかもしれないが，十分な見通しが立たない場合も少なくない．

母関数と漸化式を使って，すべてをリストアップすることができると少しの労力でｘｘ通りあることが求められる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】母関数

全部を１円で両替の仕方をＡn

１円と５円を使う両替の仕方をＢn

１円と５円と１０円を使う両替の仕方をＣn

１円と５円と１０円と５０円を使う両替の仕方をＤnで表すことにして，ｎに対する両替の仕方をＤnであらわせば，

ｎ　　４　５　９　10　14　15　19　20　24　25

Ｄn 　１　２　２　４　４　６　６　９　９　12

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

目標はＤ100であるが，母関数を用いると・・・

　（１−ｘ）^-1＝Ａ0＋Ａ1ｘ＋Ａ2ｘ^2＋・・・

　（１−ｘ）^-1（１−ｘ^5）^-1＝Ｂ0＋Ｂ1ｘ＋Ｂ2ｘ^2＋・・・

　（１−ｘ）^-1（１−ｘ^5）^-1（１−ｘ^10）^-1＝Ｃ0＋Ｃ1ｘ＋Ｃ2ｘ^2＋・・・

　（１−ｘ）^-1（１−ｘ^5）^-1（１−ｘ^10）^-1（１−ｘ^50）^-1＝Ｄ0＋Ｄ1ｘ＋Ｄ2ｘ^2＋・・・

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝