Coin Change Problem Recurrence Relation with one parameter

Question

I have been looking through the recursive formulation for the coin change problem here and am wondering if it is possible to define the function $ C(N, m) $ in one parameter as $C(N)$, therefore not depending on the set $ S_{m} $? What would this function look like in general? If a concrete example is needed what would it look like for the set of coins {3 cents coin, 4 cents coin, 5 cent coin}?

Answer 1

One possible definition is $$ C(N) = \sum_{i \in S_m} C(N-i), $$ with base cases $C(0) = 1$ and $C(x) = 0$ for negative $x$. This counts the number of ways to write $N$ as a sum of elements of $S_m$ where order matters, that is, if $a \neq b$ then $a + b$ is different from $b + a$. As an example, if $S_m = \{1,2\}$ then $C(3) = 3$ since $3 = 1 + 1 + 1 = 1 + 2 = 2 + 1$.

It is, however, possible to obtain a one-parameter recurrence relation, using inclusion exclusion: $$ C(N) = \sum_{\emptyset \neq A \subseteq S_m} (-1)^{|A|+1} C(N-\Sigma A), $$ where $\Sigma A$ is the sum of elements in $A$. For example, if $S_m = \{3,4,5\}$, then the recurrence is $$ C(N) = C(N-3)+C(N-4)+C(N-5)-C(N-7)-C(N-8)-C(N-9)+C(N-12). $$ The initial values are $$ C(0) = 1, C(1) = C(2) = 0, C(3) = \cdots = C(7) = 1, C(8) = \cdots = C(11) = 2, $$ or in table format: $$ \begin{array}{c|ccccccccccc} N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\\hline C(N) & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 \end{array} $$