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
-
1What is the trouble? – 2012-11-12
-
0I know you have to set the initial conditions so that S0 = 3, and S1 = 7. But I do not know how to set up the equation after that. – 2012-11-12
-
0Let us set up the reverse recurrence scheme: $S_{n}=S_{n-7}+S_{n-3}$. Your set up makes little sense as $0,1$ cents has no choice at all - they are impossible. – 2012-11-12
-
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.
-
0So for all n>= 7, Sn = 7+S(n-7) and for all n>=3, Sn = 3+S(n-3)? How would that work for n= 4? You can't have use a 3 cent stamp and then have .01$ of another. – 2012-11-12
-
1Actually, I did not see the part where you say that the order does not matter. However, for the ordered case, the relation would be for $n \geq 7, S_n = S_{n-7} + S_{n-3}$. – 2012-11-12
-
0Sorry, I edited the original question. Order does matter – 2012-11-12
-
0No, $S(n) = S(n-3) + S(n-7)$ for $n\ge 7$. Smaller than that you do by hand. Note however that $S(0)=1$. And I guess this is ordered, because the choice in the recursion (take 3 or 7) fixes the value of the first stamp, etc. – 2012-11-12
-
0Can you work out why this is true? – 2012-11-12
-
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