Making Change for a Dollar (and other number partitioning problems)

Question

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted below:

The answer to our problem (293) is the coefficient of $x^{100}$ in the reciprocal of the following:

$(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100})$

But I must be missing something, as I can't figure out how they get from that to $293$. Any help on this would be appreciated.

Answer 1

You should be able to compute it using a Partial Fraction representation (involving complex numbers). For instance see this previous answer: Minimum multi-subset sum to a target.

Note, this partial fraction expansion needs to be calculated only one time. Once you have that, you can compute the way to make change for an arbitrary amount pretty quickly.

In this case, I doubt they really did that for finding the coefficient of $x^{100}$. It is probably quicker to just multiply out, ignoring the terms which would not contribute to the coefficient of $x^{100}$. Or you could try computing the partial fraction representation of only some of the terms and then multiply out.

Note, if you are multiplying out to find the coefficient of $x^{100}$, it would be easier not to go to the reciprocal, which arises from considering an infinite number of terms.

You just need to multiply out

$$ (\sum_{j=0}^{100} x^j)\ (\sum_{j=0}^{20} x^{5j})\ (\sum_{j=0}^{10} x^{10j})\ (\sum_{j=0}^{4} x^{25j})\ (1 + x^{100})$$

which would amount to enumerating the different ways to make the change (and in fact is the the way we come up with the generating function in the first place).

You could potentially do other things, like computing the $100^{th}$ derivative at $0$, or computing a contour integral of the generating function divided by $x^{100}$, but I doubt they went that route either.

Hope that helps.

Answer 2

You "just" have to follow the prescription: find the formal power series (no need to think about convergence) that is defined and check the number that multiplies x^100. There's a reason I put just in quotes. There is no obvious route to 293 that I can see. Mathematica can do it with just one command, but I can't get Alpha to do it.

Answer 3

We can ease the calculation by noting that the number of ways of changing 100 equals the number of ways of representing the numbers less than or equal to $100$ as the sum of the numbers $5, 10, 25, 50$ and $100$, since the pennies can make up any remaining difference.

Noting that all these number are divisible by $5$ we can conclude that the number of ways of representing $100$ in units of $1, 5, 10, 25, 50$ and $100$ is the sum of the coefficients up to and including the term in $x^{20}$ in the expansion of

$$ \frac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})} . $$

Answer 4

I think you calculate $[x^{100}](1-x)^{100}(1-x^5)^{20}(1-x^{10})^{10}(1-x^{25})^4(1-x^{50})^2(1-x^{100})$, but that calculation seems to be brute force.

Answer 5

Calculating coefficient before $x^{100}$ can be done quite easy and quickly in this situation. I will show it for coins 5,10,20,50, because the idea is relevant and that will be faster. Denote:

$\displaystyle P_5(x)=\frac{1}{1-x^5}=1+x^5 P_5(x)$ (multiply by denominator)- generating function for changing money only with 5 cents

$\displaystyle P_{5,10}(x)=\frac{P_5(x)}{1-x^{10}}=P_5(x)+x^{10}P_{5,10}(x)$ - for changing with coins 5,10, and so on..

$P_{5,10,20}(x)=P_{5,10}(x)+x^{20}P_{5,10,20}(x)$

$P_{5,10,20,50}(x)=P_{5,10,20}(x)+x^{50}P_{5,10,20,50}(x)$

We are looking for sequence $p_n$, where $P_{5,10,20,50}(x)=\sum_{n}p_n x^n$. Denote: $P_5(x)=\sum_{n}q_n x^n, \ P_{5,10}(x)=\sum_{n}r_n x^n, \ P_{5,10,20}(x)=\sum_{n}s_n x^n$, and by the relations with generating functions above, it follows:

$$q_n=1, \ r_n=q_n+r_{n-10}, \ s_n=r_n+s_{n-20}, \ p_n=s_n+p_{n-50}$$ so it takes 5 minutes to calculate $p_n$ fo small $n$, which is an answer. For bigger $n$ maybe better will be to solve this system of recurrences (because I'm not sure about complexity of finding $p_n$ from these recurrences, but it is unsatisfying I think) and derive closed form formula for $p_n$ but for now I can't do it.

Answer 6

For the record, I'll copy a snippet form this answer to a question that was closed as a duplicate to this question, as it explains exactly how to compute the given coefficient explicitly, which is really the same as the method given in the answer by ray in a more algorithmic formulation. I just give the procedure here, for more explanations see the answer linked to.

Let $c$ denote an array of $101$ integers indexed from $0$ to $100$.

• Initialise your array so that $c[0]=1$ and $c[i]=0$ for all $i>0$.
• For $k=1,5,10,25,50,100$ (in any order) do:
  • for $i=0,1,\ldots,100-k$ (in this order) do:
    • add $c[i]$ to $c[i+k]$.
• Now $c[100]$ gives your answer.

This computation gives you the coefficient of $x^{100}$ in the power series for $1/((1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})(1-x^{100}))$, which equals $293$.