assume you have coins with face value "1", "4", and "8".
How many ways are there to make change for a given amount X, using exactly Z coins in total?
my initial idea was to use generating functions, e.g.
$$ 1*a + 4*b + 8*c = X$$
$$a+b+c = Z$$
so
$$a = Z-b-c$$
$$1*(Z-b-c) + 4*b + 8*c = N$$
$$3b + 7c = N-Z$$
The total number of integer solutions of which (ignoring Z – the shift could be applied later on) I believe could be expressed via a power series as
$$\frac{1}{(1-x^3)(1-x^7)}$$
unfortunately, this doesn't have any non-negativity constraint for a though, so would include impossible combinations (a negative amount of coin 1).
Is there any way to express this problem in a generating function that takes this constraint into account? Is there maybe even a more elegant way to solve the underlying question, without generating functions at all?
Thanks!
Best Answer
Let's use linear algebra. If we take the matrix
$$A = \begin{pmatrix}1 & 4 & 8 \\ 1 & 1 & 1\end{pmatrix}$$ we want to solve $$Ax = \begin{pmatrix}X \\ Z\end{pmatrix}.$$
Now if this system has a solution at all, then the set of all solutions is described by the kernel of $A$. This kernel has dimension one (over $\mathbb{Q}$, for example), so there is a vector $v \in \mathbb{Q}^3$ such that every solution has the form $x_0 + rv$ with $r \in \mathbb{Q}$, where $x_0$ is an abitrary solution. Can you compute $v$? Can you find a vector $v$ only containing integers and, if possible, coprime ones?
This vector is what lulu was asking for in the comments: How to change one valid solution to another one.
Now assume we have one solution $(a,b,c)$. We can chose $r \in \mathbb{Q}$ to get all rational solutions as $(a,b,c) + rv$. As both $(a,b,c)$ and $v$ are integer vectors, with the entries of $v$ being coprime, and we also want integer solutions, we get them all by chosing $r \in \mathbb{Z}$.
This allows you to enumerate all integer solutions. Then all that is left is checking which of them have all three entries non-negative. The actual counting depends on $N$ and $Z$, of course. If you are looking for a closed formula that works for all $N$ and $Z$, I'm not sure if that is easy/possible (but I wouldn't mind being proven wrong on that, of course).