Godd afternoon,
We have set C of k coins; For example C = (2, 3)
We have positive integer n.
In how many ways we can represent n using those coins?
Example:
If n = 12; C = (2, 3) we can represent 12 as 3+3+3+3, 3+3+2+2+2 or 2+2+2+2+2+2, so in three ways.
Introduction:
For any predefined set of coins, there exists formula for number of ways to make change. We can find it using generating functions.
For example number of ways to represent n using set of coins (2, 5) is equal to n-th coefficient in $\frac{1}{(1 - x^2)(1 - x^3)}$ series expansion. We decompose this function to simple fractions. Then it's easy to find series expansion.
$F(x) = \frac{1}{(1 - x^2)(1 - x^3)} = \frac{1}{4(1 - x)} + \frac{1}{4(1 + x)} + \frac{1}{6(1 - x)^2} + \frac{1}{3(x^2 + x + 1)} = \frac{1}{4}\sum_{n=0}^{\infty}x^n + \frac{1}{4}\sum_{n=0}^{\infty}(-1)^nx^n + \frac{1}{6}(\frac{1}{1 - x})' + \frac{1}{3(x^2 + x + 1)} = ... = \frac{1}{4}\sum_{n=0}^{\infty}(\frac{1}{4} + \frac{(-1)^n}{4} + \frac{n+1}{6} + \frac{c_{n}}{3})x^n$
Where $c_{3k} = 1, c_{3k + 1} = -1, c_{3k + 2} = 0$.
We could represent $\frac{1}{x^2 + x + 1}$ as a sum of series with complex coefficients, it's easier however, to just find reverse formal series for polynomial $x^2 + x + 1$, and that's what I did.
Now, the actual question:
How to do this for C (set of coins) not predefined. Is there an algorithm we can use to replicate my reasoning in the computer? Decompose a fraction into simple fractions, determine the formula (automatically) and in constant time (in practice in linear time from number of coins, because the formula would contain k elements) find the result.
