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}
\]
