Suppose that you have a large supply of $3$ and $7$ cent stamps. Write a recurrence relation and initial conditions for the number $S_n$ of different ways in which n cents worth of stamps can be attached to an envelope if the order in which the stamps are attached does matter.
Stamp Problem Homework
-
0Note: order does not matter. Hence e.g. $S_{10}=1 \neq 2=S_3+S_7$. – 2012-11-12
2 Answers
The ordered case, as previously noted, satisfies the recurrence $S_{\mathrm{ord}}(n)=S_{\mathrm{ord}}(n-3)+S_{\mathrm{ord}}(n-7).$
For the unordered case, I give the following hint:
Hint (since this is flagged as homework): We can adjust this recurrence to account for the "order is not important" by adding in a correction term to account for overcounting. So, we have $S(n)=S(n-3)+S(n-7)-[???].$ There's quite an elegant reason for this, and I don't want to spoil this for you.
The initial conditions are merely bookkeeping (they can be counted by hand, once you know the depth of the recurrence).
If you want to put $n$ cents worth of stamps, you can either put one $7$ cent stamp and $n-7$ cents worth of stamps (i.e. $S_{n-7}$), provided that $n \geq 7$, or one $3$ cent stamp and $n-3$ cents worth of stamps (i.e. $S_{n-3}$), provided that $n \geq 3$. As far as initial conditions are concerned, you just have to analyse what is going on for $n < 7$, which should be fairly easy.
-
0@MKZ: Choosing an ordered sequence is the same as choosing the first element, and then choosing the rest. The thing is, here, you want to count the sequences of 3 and 7's that add up to $n$, so once you chose the first element $k$, you need to count the sequences that add up to $n-k$. Is it clearer ? – 2012-11-12