地道に数えて解決できる問題でしょうか？

いえ、地道に数えたのですが・・・
途中で挫折し答えが出ておりませぬ すいません。
パターンは何となくわかったのですが
2005（2000）まで広げることができなかったのでうまい考え方はないかなと出してみました

500円の作り方は19161通りあるそうです。
私ももう一回考えてみます。

500円の作り方が2万通りあるってことは，1000円の作り方は4億通りくらいはあるって事になるんじゃないの？

ですよね

ちょっと無理がありました。反省

地道に数えました。
１種類使用の場合：　　　　2通り
２種類使用の場合：　　　934通り
３種類使用の場合：　 65,744通り
４種類使用の場合：　920,750通り
５種類使用の場合：2,823,670通り
６種類使用の場合：　928,300通り
７種類使用の場合：　　5,000通り
計4,744,440通りでした。