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

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 4

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

In this particular case there is a trick that will save time and memory, exploiting the fact that all values of $k$ except $k=1$ are divisible by$~5$. Since we are free to choose the order of the$~k$, we can keep $k=1$ for the end, and observe that only the values $c[i]$ with $i$ divisible by$~5$ will be nonzero when we get to the final loop instance for $k=1$. But then we might as well set up the initial loops to compute only them (so do only those $i$ in the inner loop that are divisible by $5$). Also the final loop for $k=1$ is just computing the sum of all entries into $c[100]$, so we might as well take only the sum of the nonzero entries. Thus one gets a procedure that involves only the $21$ multiples of $5$ up to $100$, and can be done even by hand.

I'll add that this is not the asymptotically fastest method to compute coefficient of $x^n$ in the given series for large $n$. It can be done in a constant number of arithmetic operations by making the denominator a power of the least common multiple of the factors written, which in this case would be the sixth power of $1-x^{100}$ as it is divisible by the other factors, for instance $1-x^{100}=(1-x^{25})(1+x^{25}+x^{50}+x^{75})$. The quotients involved to transform all factors into this least common multiple must of course also be multiplied into the numerator to keep the expression equivalent. The numerator now is a polynomial that can be explicitly computed once and for all, and this is to be multiplied by a negative power, here $(1-x^{100})^{-6}$, whose coefficients can be computed (on demand!) using binomial coefficients. To find the coefficient in the result of a single monomial $x^n$ requires multiplying each of the fixed number of the coefficients in the numerator factor by one coefficient from the denominator factor and adding up; all this gives a constant number of operations. This requires more preparation and programming to be done then the method sketched above, which for value like $n=100$ does not really pay off. However, if the question were how many ways there are to make change for a billion (in the sense of thousand million) dollars, using only the same coins (supposing enough existed), one would have $n=10^{11}$ and the correct coefficient 13333333398333333445333333413833333354500000001 for that case would have been hard to compute differently. Bonus question, explain why there are so many repeated digits in this coefficient.