0
$\begingroup$

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}?

$\endgroup$

1 Answer 1

0
$\begingroup$

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} $$

$\endgroup$

Your Answer

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

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