4
$\begingroup$

How many ways are there to add the numbers in set $k$ to equal $n$?

For a specific example, consider the following: I have infinite pennies, nickels, dimes, quarters, and loonies (equivalent to 0.01, 0.05, 0.1, 0.25, and 1, for those who are not Canadian). How many unique ways are there to add these numbers to get a loonie?

Some combinations would include:

$1 = 1$

$1 = 0.25 + 0.25 + 0.25 + 0.25$

$1 = 0.25 + 0.25 + 0.25 + 0.1 + 0.1 + 0.05$

And so on.

Several people have suggested the coin problem, though I have yet to find a source that explains this well enough for me to understand it.

$\endgroup$
6
+50
$\begingroup$

The generating function approach is to look for the coefficient of $x^{100}$ in $(1+x+x^2+x^3+\cdots)(1+x^5+x^{10}+x^{15}+\cdots)(1+x^{10}+x^{20}+x^{30}+\cdots)(1+x^{25}+x^{50}+x^{75}+\cdots)(1+x^{100}+x^{200}+x^{300}+\cdots)$

More details, as requested.

Let's imagine multiplying out these (infinite) polynomials, and collecting terms. We will do this from low degree to high degree. The constant term is $1$, which can be obtained only by choosing $1$ from each of the five products. The $x$ term is just $x$, which can only be obtained by choosing $x$ from the first product and $1$ from each of the others. The $x^2$ term is just $x^2$, which can only be obtained by choosing $x^2$ from the first product and $1$ from each of the others. Similarly $x^3, x^4$.

But now the $x^5$ term is $2x^5$ -- one piece comes from choosing $x^5$ from the first product and $1$ from each of the others, and another piece comes from choosing $x^5$ from the second product and $1$ from each of the others. This corresponds directly to the two ways we can make five cents, either with five pennies (and zero nickels, zero dimes, etc.) or with one nickel. Moving on, the coefficient of $x^{10}$ is 4, which comes from $x^{10}\cdot 1\cdot 1\cdot 1\cdot 1 + x^{5}\cdot x^{5}\cdot 1\cdot 1\cdot 1+1\cdot x^{10}\cdot 1\cdot 1\cdot 1+1\cdot 1\cdot x^{10}\cdot 1\cdot 1$. This corresponds to the four possibilities of ten pennies (the tenth term of the penny product), five pennies and one nickel (the fifth term of the penny product and the second term of the nickel product), two nickels (the second term of the nickel product), and one dime (the first term of the dime product).

In all cases choosing $1$ from a product is the same as choosing $x^0$, or the zero-th term from that product, or none of that coin at all.

We may in fact simplify the products because they are geometric series, so we want the coefficient of $x^{100}$ in $$\frac{1}{1-x}\frac{1}{1-x^5}\frac{1}{1-x^{10}}\frac{1}{1-x^{25}}\frac{1}{1-x^{100}}$$

We can feed this into wolframalpha (look for "expansion at zero" and click "more terms" a few times) to find the answer is $243$.

$\endgroup$
  • $\begingroup$ My apologies, but I can't seem to understand what you mean by this; could you possibly elaborate? $\endgroup$ – Cisplatin Apr 25 '13 at 23:53
3
$\begingroup$

You will have luck googling for this with the phrase "coin problem".

I have a few links at this solution which will lead to the general method. There is a Project Euler problem (or maybe several of them) which ask you to compute absurdly large such numbers of ways, but the programs (I found out) can be just a handful of lines.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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