The method is based on generating functions, where we encode the total money in the exponent and the number of ways to encode them in the coefficient.
If we only have a single coin (with value $n$) and we are obligated to take $a$ coins, there is only one total value to create being $an$, so the generating function is:
$$x^{an}$$
If one can take multiple values, it is easy to see that the single values have to be summed, so
$$x^{an} + x^{bn} + x^{cn}$$
As this encodes, there is one way to get $an$, one to get $bn$ and one to get $cn$. If the number of coins is completely free, gene generating function becomes by consequence:
$$\sum_{i=0}^{\infty} x^{in} = \frac{1}{x^n-1}$$
As adding the values of different coins is equivalent to adding the exponents, which is equivalent to multiplying, combining multiple coins is equivalent to multiplying the generating functions. So if we have coins with values $c_1, c_2, ... \in S$, out generating function becomes
$$\prod_{c \in S} \frac{1}{x^c-1}$$
In the real numbers, the expression $x^c -1$ cannot be unbound in factors of the form $x-a$, so we have to consider our polynomial in a field that does allow this. An obvious extension would be the complex numbers, but to make calculations easier and more exact, we are going to use modular rings.
Note that by using this method, we will only get a final result modulo our prime, so our prime has to be selected large enough so that this doesn't matter.
First, we will have to select our modules for our modular ring. It has to follow the following properties:
- It has to be prime
- It needs roots of unity with as order the value of each coin, for every coin
- It needs to be larger than the maximum number of combinations $m^n$
Lets first take a look at how to construct roots of unity. If $g$ is a primitive root, then is
$$g^{p-1} \equiv 1 \pmod p$$
So
$$g^\frac{i(p-1)}{a}$$
is a root with order $a$ for $i$ between 0 and $a$
This only works when $p-1$ is a multiple of all single coins, or in other words, with the least common multiple of all coins. So if we generate numbers of the form $$(1+k.lcm(S))$$ until we have a prime that is larger than $m^n$, we have the correct modulo.
According to this theorem, this prime does always exist.
Then, if we have decided on the modulo and found the roots of unity, one can simplify the expression
$$\prod_{r \in T}\frac{1}{(x-r_c)^m}$$
with $T$ the multiset off all the roots and $m$ the multiplicity
According to the method of partial fractions, this can be rewritten as a sum of simple rational functions of the form
$$ \frac{A}{(x-r)^n}$$
with $A$ the undetermined coefficients, r the different roots and $n$ the counting multiplicities.
So for example, if the roots are (1,1,1,2,3,3), the values of r and n will be (1,1),(1,2),(1,3),(2,1),(3,1),(3,2).
Determining the undetermined coefficients is quite easy. Multiply both sides with $$\prod_{r \in T}(x-r_c)^m$$, so the right side will be $1$ and the left side each has a sum where each term is a polynomial with as roots all the original roots except for the root that was in the denominator, this root cancels out partially or fully with the denominator.
This means that we have a sum of polynomials with known roots. for each polynomial, the coefficient of every power can be calculated as follows:
- If there is only one root, the coefficient for 0 is minus the root, for 1 is 1 and for two or higher it is zero.
- If there are more roots, the coefficient is the coefficient of the polynomial without the root of the same order times minus the root, plus the coefficient of the polynomial without the root one order lower.
To combine the coefficients, we just have to sum them.
Now that we have the coefficients, we can finish the equation by stating that the constant has to be 1, and all other coefficients zero. This creates a system of linear equations, which can be solved by Cramers method. Note that we are still working in a ring, so that division works differently. When this is solved, we will have the undetermined coefficients.
The function
$$ \frac{A}{(x-r)^n}$$
when Taylor expanded, has the coefficients
$$A. (-a)^{-n-v} \binom{-n}{v}$$
This coefficients can be calculated and summed, if one sets $v$ to be the amount of initial money.