Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

I am looking for a formula or at least something to use when trying to compute how many ways I can make change for an amount.

Example: there are $3$ ways to give change for $4$ if you have coins with denomination $1$ and $2$: $1+1+1+1, 1+1+2, 2+2$.

What formula should I use?

share|cite|improve this question

marked as duplicate by draks ..., Nick Peterson, T. Bongers, Hagen von Eitzen, Dan Rust Sep 1 '13 at 22:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

This problem is called integer Partitioning. There is a recursive formula to list all possible partitions of an integer. Given a number of 4 you could generate the following sets of values:


3 1

2 2

2 1 1

1 1 1 1

Please refer to Wiki-Partitions for details. Unfortunately, it is not a trivial calculation.

There is another problem related to this that is called Money Changing Problem or Change Making Problem , where you'd be interested in specific values rather than getting all possible values. For example changing Five Dollars in a country where there is no 4 dollar notes or coins.

For such problems you may use R, Mathmatica, etc.

share|cite|improve this answer
The question text clearly shows that this is Making Change rather than Partitions: "you have coins with denomination 1 and 2" – AakashM Sep 28 '12 at 8:41
@AakashM, you may have a point. I don't have a simple formula for this though. – NoChance Sep 28 '12 at 9:04

The formula to use is to find the coefficient of $X^a$ (where $a$ is your amount) in the expansion as a power series in $X$ of $$ \frac1{(1-X^{d_1})(1-X^{d_2})\cdots(1-X^{d_n})} $$ where $d_1,d_2,\ldots,d_n$ are the denominations of your coins. In principle this is just an algebraic reformulation that does not help you at all: finding the coefficient in the straightforward way (writing each $\frac1{1-X^{d_i}}$ as a geometric series and multiplying out) merely gives you the combinatorial problem you started with. However, as I explained in this answer to a related question, you can actually perform these multiplications very easily without even expanding each $\frac1{1-X^{d_i}}$ in the first place, by a simple loop updating a sequence of coefficients of your current power series (truncated after the term that interests you).

share|cite|improve this answer

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