1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

https://www.geeksforgeeks.org/coin-change-dp-7/amp/

$\endgroup$
1
  • $\begingroup$ That's the solution in o(nv), and I wonder if there exist a faster one. For predefined set of coins, I have provided solution in o(n), can it be generalized to not predefined set of coins read from the input? $\endgroup$
    – yomol777
    Nov 9, 2022 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.