支払い方は何通り？

久しく記事を書いていなかったので、ちょっとしたことでも書いてみよう。

千円札と二千円札を使って $${n}$$千円を支払う方法の総数は、支払いに二千円札を何枚使えるかを数えれば良いので（使う二千円札の枚数を決めれば、使う千円札の枚数は残額によって自動的に決まる、という状況）

$$
\Bigl\lfloor\frac{n}{2}\Bigr\rfloor+1
$$

通り。同じように、千円札と五千円札を使って $${n}$$千円を支払う方法の総数は

$$
\Bigl\lfloor\frac{n}{5}\Bigr\rfloor+1
$$

だし、千円札と一万円札を使って $${n}$$千円を支払う方法の総数は

$$
\Bigl\lfloor\frac{n}{10}\Bigr\rfloor+1
$$

通りということになるね。

では、千円札と二千円札と五千円札を使って $${n}$$千円を支払う方法の総数はどれぐらいあるか、というと、結論を先に書くと

$$
\Bigl\lfloor \frac{n(n+8)}{20}\Bigr\rfloor+1
$$

通りある。これは結局のところ

$$
a+2b+5c=n
$$

という方程式の非負整数解 $${(a,b,c)}$$ が何組あるかを数える問題と同じということになるけれど、母関数の考え方を使えば

$$
\frac1{(1-x)(1-x^2)(1-x^5)}
$$

を $${x}$$ のべき級数として展開したときの $${x^n}$$ の係数を求める問題ということにもなる。なんでかというと、等比級数の和の公式を使えば

$$
\frac1{(1-x)(1-x^2)(1-x^5)}
=\sum_{a=0}^\infty x^a \sum_{b=0}^\infty x^{2b} \sum_{c=0}^\infty x^{5c}
=\sum_{a=0}^\infty \sum_{b=0}^\infty \sum_{c=0}^\infty x^{a+2b+5c}
$$

となるから。一方で

$$
\frac1{(1-x)(1-x^2)(1-x^5)}
=\frac{13}{40}\frac1{1-x}+\frac14\frac1{(1-x)^2}+\frac1{10}\frac1{(1-x)^3}
+\frac18\frac1{1+x}+\frac15\frac{1+x^2-x^3-x^4}{1-x^5}
$$

という部分分数分解が出来るので、この右辺を（一般化された）二項定理を使って展開すれば、$${x^n}$$ の係数は

$$
\frac{13}{40}+\frac{n+1}4+\frac{(n+1)(n+2)}{20}+\frac{(-1)^n}8+\frac{f(n)}5
$$

となる。ただし $${f(n)}$$ は、$${n\equiv 0,2 \pmod5}$$ ならば $${1}$$、$${n\equiv 3,4 \pmod 5}$$ ならば $${-1}$$、$${n\equiv 1 \pmod5}$$ ならば $${0}$$ である。最後の2項の和は絶対値が $${\frac{13}{40}}$$ 以下なので、求める係数は

$$
\Bigl\lfloor \frac{13}{40}+\frac{n+1}4+\frac{(n+1)(n+2)}{20}+\frac{13}{40} \Bigr\rfloor
=\Bigl\lfloor \frac{n(n+8)}{20} \Bigr\rfloor+1
$$

となる、という仕組みです。

全種類のお札、千円札と二千円札と五千円札と一万円札を使って $${n}$$千円を支払う方法の総数はどれぐらいあるか、という問題も原理的には同じように考えれば良くて、今度は

$$
\frac1{(1-x)(1-x^2)(1-x^5)(1-x^{10})}
$$

のべき級数展開における $${x^n}$$ の係数を調べることになります。