# Stamp Problem Homework

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.

-

1
What is the trouble? – user32240 Nov 12 '12 at 0:56
I 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. – MKZ Nov 12 '12 at 0:58
Let 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. – user32240 Nov 12 '12 at 1:01
Note: order does not matter. Hence e.g. $S_{10}=1 \neq 2=S_3+S_7$. – Douglas S. Stones Nov 12 '12 at 1:03

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

-
So 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. – MKZ Nov 12 '12 at 1:04

1
Actually, 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}$. – beauby Nov 12 '12 at 1:06
Sorry, I edited the original question. Order does matter – MKZ Nov 12 '12 at 1:08
No, $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. – Hendrik Jan Nov 12 '12 at 1:11
Can you work out why this is true? – MKZ Nov 12 '12 at 1:19
show 1 more comment
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9574071168899536, "perplexity_flag": "middle"}