# Number of ways to make change in o(k), where k is number of coins

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.

Dynamic programming provides an $$O(nv)$$ solution where $$n$$ is the number of coins and $$v$$ is the target value. A slight variation to the classic coin change dynamic programming solution can be used to count number of solutions.