#### Problem

Find how many ways are there to pay an amount \(n\) using coins of \(c_1, c_2,\cdots, c_k\).

To count the ways of summing \(n\), what we need is the coefficient of \(x^n\) in

\[

\prod_{i=1}^{k}(1+x^{c_i}+x^{2c_i}+x^{3c_i}+\cdots) = \prod_{i=1}^{k}\frac{1}{1-x^{c_i}}

\]

Now \(x^c-1=(x-\omega_{1})(x-\omega_{2})\cdots(x-\omega_{c})\) and we can represent the product above as

\[

\frac{(-1)^{k}}{Q(x)} = \frac{(-1)^{k}}{(x-a_1)^{m_1}(x-a_2)^{m_2}\cdots(x-a_l)^{m_l}}

\]

where \(m_i\) is the multiplicity of \(a_i\) in the denominator. Decomposing in partial fractions we get

\[

\sum_{i=1}^{m_1} \frac{A_1^{i}}{(x-a_1)^{i}}

+ \cdots +

\sum_{i=1}^{m_l} \frac{A_l^{i}}{(x-a_l)^{i}}

\]

And using

\[

\sum_{n=0}^{\infty} \binom{n+k}{k}t^n = \frac{1}{(1-t)^{k+1}}

\]

we end up with (up to a factor \((-1)^k\))

\[

\sum_{i=1}^{m_1}\binom{n+i-1}{i-1}\frac{(-1)^{i}A_1^{i}}{a_1^{n+i}}

+ \cdots +

\sum_{i=1}^{m_l}\binom{n+i-1}{i-1}\frac{(-1)^{i}A_l^{i}}{a_l^{n+i}}

\]

To calculate \(A_i^{m_i}\) we observe that

\[

\left. \frac{(x-a_i)^{m_i}}{Q(x)}\right|_{x=a_i} = A_i^{m_i}

\]

and to get the other \(A_i\)s we have

\[

\left.

\frac{1}{j!}

\frac{d^j}{dx^j}

\left(

\frac{(x-a_i)^{m_i}}{Q(x)}

\right)

\right|_{x=a_i}

= A_i^{m_i-j}

\]

For the partial fraction expansion we have followed the exposition here.

Let \(F(x)\) be a proper fraction, and let the denomitor \(Q(x)\) have roots \(a_1,\cdots,a_l\) with multiplicities \(k_1,\cdots,k_l\)

\[

F(x) = \frac{P(x)}{Q(x)} = \frac{P(x)}{(x-a_1)^{k_1} \dots (x-a_l)^{k_l}}

\]

partial fraction expansion has than the form

\[

F(x) = \sum_{i=1}^{k_1} \frac{A_1^{i}}{(x-a_1)^{i}} +

\sum_{i=1}^{k_2} \frac{A_2^{i}}{(x-a_2)^{i}} +

\cdots +

\sum_{i=1}^{k_l} \frac{A_l^{i}}{(x-a_l)^{i}}

\]

Then

\[

\left. F(x)(x-a_i)^{k_i}\right|_{x=a_i} = A_i^{k_i}

\]

and to get the other \(A_i\)s we have

\[

\left.

\frac{1}{j!}

\frac{d^j}{dx^j}

\left(

F(x)(x-a_i)^{k_i}

\right)

\right|_{x=a_i}

= A_i^{k_i-j}

\]