1円玉，5円玉，10円玉を使ってN円をぴったり支払う方法の数

1円玉，5円玉，10円玉を使って $N$ 円をぴったり支払う方法の数を研究します．

同じことをやっている人は，ググった感じだと

組み合わせの問題です。 -（１）1円、5円、10円の硬貨をとりまぜて合計- 数学 | 教えて!goo
や
西三数学サークル通信44号
なんかがありました．

この記事では以下の定理を二通りの方法で証明します．

定理
$N$ は非負整数とする．1円玉，5円玉，10円玉を使って $N$ 円を正確に支払う方法の数は

非負整数 $n$ を使って $N=10n,10n+1,10n+2,10n+3,10n+4$ と書けるとき

$(n+1)^2$ 通り，

非負整数 $n$ を使って $N=10n+5,10n+6,10n+7,10n+8,10n+9$ と書けるとき

$(n+1)(n+2)$ 通り
である．

証明１．（直接数える証明）

非負整数 $n$ を使って $N=10n,10n+1,10n+2,10n+3,10n+4$ と書けるとします．
10円玉を何個使うかで場合分けします．
10円玉を $n$ 個使う場合は，払い方は1通り．
10円玉を $n-1$ 個使う場合は，払い方は5円玉を2個，1個，0個使う場合の3通り．
10円玉を $n-2$ 個使う場合は，払い方は5円玉を4個，3個，...，0個使う場合の5通り．
...
10円玉を $0$ 個使う場合は，払い方は5円玉を $2n$ 個，...，0個使う場合の $2n+1$ 通り．

これらを合わせると， $\sum_{i=0}^n(2i+1)=(n+1)^2$ 通り．

一方，非負整数 $n$ を使って $N=10n+5,10n+6,10n+7,10n+8,10n+9$ と書けるとします．
10円玉を $n$ 個使う場合は，払い方は5円玉を1個，0個使う場合の2通り．
10円玉を $n-1$ 個使う場合は，払い方は5円玉を3個，2個，1個，0個使う場合の4通り．
...
10円玉を $0$ 個使う場合は，払い方は5円玉を2n+1個，...，0個使う場合の2n+2通り．

これらを合わせると， $\sum_{i=0}^n(2i+2)=(n+1)(n+2)$ 通り．
（証明終）

証明２．（母関数を使う証明）

1円玉，5円玉，10円玉を使って $N$ 円を支払う方法の数は，形式的冪級数
$(1+q+q^2+q^3+\cdots)(1+q^5+q^{10}+q^{15}+\cdots)(1+q^{10}+q^{20}+q^{30}+\cdots)$
$=\frac{1}{(1-q)(1-q^5)(1-q^{10})}$
における $q^N$ の係数です．

定理の主張は，その $q^N$ の係数が，
非負整数 $n$ を使って $N=10n,10n+1,10n+2,10n+3,10n+4$ と書けるとき $(n+1)^2$ であり，非負整数 $n$ を使って $N=10n+5,10n+6,10n+7,10n+8,10n+9$ と書けるとき $(n+1)(n+2)$ であるというものです．

よって示すべき式は
$\sum_{n=0}^\infty(n+1)^2q^{10n}(1+q+q^2+q^3+q^4)$
$+\sum_{n=0}^\infty(n+1)(n+2)q^{10n+5}(1+q+q^2+q^3+q^4)$
$=\frac{1}{(1-q)(1-q^5)(1-q^{10})}$
です．

$(1+q+q^2+q^3+q^4)=\frac{1-q^5}{1-q}$ なので，この部分を右辺におしやり，さらに $q^5$ を新しく $x$ と書きます．
$\sum_{n=0}^\infty(n+1)^2(x^2)^{n}+x\sum_{n=0}^\infty(n+1)(n+2)(x^2)^{n} =\frac{1}{(1-x)^2(1-x^2)}$

左辺を
$\sum_{n=0}^\infty n^2x^n=\frac{x(1+x)}{(1-x)^3},$
$\sum_{n=0}^\infty nx^n=\frac{x}{(1-x)^2},$
$\sum_{n=0}^\infty x^n=\frac{1}{1-x},$
などを使って計算すれば右辺に一致します．
（証明終）