How many ways to make change using specific amounts.

Question

I am trying to figure out a recurrence relation or any kind of formula really that returns the number of ways to calculate a specific amount $n$ using only $3, 4, 5$. So for $8$ you can do either $4+4$ or $5+3$. I know it's related to Partitioning and the coin change problem, but I can't figure out how to do it for these or any specific amounts.

Answer 1

Hello and welcome to math.stackexchange. Your question is about restricted partitions and is best analyzed using generating functions.

Specifically, if $T$ is a finite set of positive integers and $a_n$ is the number of ways to write $n$ as a sum of integers from $T$ (repetitions allowed), one considers the power series $$ g_T(x) = \sum_{n=0}^\infty a_n x^n \,. $$ In your case, $T = \{3,4,5\}$ and therefore
$$ g_T(x) = x^3 + x^4 + x^5 + x^6 + x^7 + 2x^8 + 2x^9 + 2x^{10} + 2x^{11} + 3x^{12} + \dots $$ It turns out that $$ g_T(x) = \prod_{k \in T} \frac{1}{1-x^k} $$ which allows the rapid computation of all $a_n$. For example $a_{200} = 354$, so there are exactly 354 ways to write 200 as sum of multiples of 3, 4, 5, see this Wolfram Alpha computation . For details, looks at the Wikipedia article on generating functions and partitions.