0
$\begingroup$

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.

  • 0
    Note: order does not matter. Hence e.g. $S_{10}=1 \neq 2=S_3+S_7$.2012-11-12

2 Answers 2

1

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

1

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