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

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

　ｎに対する両替の仕方をＤnであらわせば，

ｎ　　４　５　９　10　14　15　19　20　24　25

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

目標はＤ100であるが，

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

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

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

１円と５円と１０円と５０円を使う両替の仕方をＤnで表せば，

　　Ｄn＝Ｃn＋Ｄn-50

すなわち，５０円を使わない，５０円を使う両替の仕方に分けることができる．同様に

　　Ｃn＝Ｂn＋Ｃn-10

　　Ｂn＝Ａn＋Ｂn-5

　　Ａ0＝Ｂ0＝Ｃ0＝Ｄ0＝１

という漸化式の問題となる．

ｎ　　０　５　10　15　20　25　30　35　40　45　50・・・100

Ａn 　１　１　１　１　１　１　１　１　１　１　１・・・？

Ｂn 　１　２　３　４　５　６　７　８　９　10　11・・・？

Ｃn 　１　２　４　６　９　12　16　20　25　30　37・・・？

Ｄn 　１　２　４　６　９　12　16　20　25　30　37・・・？

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