# Number of $N$-size configurations of coins to total a specific sum

Let's say we have a bunch of coins with denominations $d_1, d_2,\ldots,d_n$ and a target sum $M$. Is it possible to count the total number of ways I can select exactly $N$ coins (with replacement) that add up to $M$?

For example, if the denominations are $0.05, 0.10, 0.15, 0.20, 0.50$ and the total $M = 0.75$, there are 12 permutations of $N = 3$ coins that total to $M$.

If possible, I would prefer to count the number of permutations, but combinations are acceptable as well.

I understand this is a dynamic programming problem but I was wondering if there's a way of counting the number of solutions.

I have found several related questions such as [fixed sum combinations]{Fixed sum of combinations} and [number of ways to select a sum with limited number of elements]{Number of ways to select a sum with limited number of elements} but there are some differences.

• Does it help that the dynamic programming solution can be adapted to also count the number of solutions? – Misha Lavrov Apr 5 '17 at 3:28
• @MishaLavrov I am interested in alternative, non dynamic programming solutions but yes, thank you for making that point. – undefinederrorname Apr 5 '17 at 3:37

$$f(x) = (x^{d_1} + x^{d_2} + ... + x^{d_m})^N$$
where the exponents $d_1, d_2, ..., d_m$ are the denominations, $N$ is the size of configuration (number of coins to be used), and (after expanding) the coefficient of $x^M$ represents the number of configurations of $N$ coins that add to $M$.