There only exist 2 cent, 4 cent and 5 cent stamps. Provide a recurrence relation and the initial conditions to the number of ways to create $n$ cents in postage. I want to see the recurrence relation and the initial conditions. Also, calculate the number of permutations to come up with 20 cents in postage.
PLEASE DO NOT EDIT MY QUESTION THIS IS HOW IT IS ASKED
I have been struggling with this problem this is what I have come up with so far:
-
Recurrence relation: $f(n) = f(n – 2) + f(n-4) + f(n-5)$
-
Initial conditions: $a_0 = 1$ because you cant make 1 cent with 2, 4, 5 but you can make everything that comes after it. Then $a_1 = 2, a_2 = 4, a_3 = 5$.
-
permutations: $P(20,2) + P(20,4) + P(20,5) – overlap$. I am not sure how to calculate the overlap.
If anyone can give me some insight on my three steps it will be much appreciated!
Best Answer
Let's say that you set $$f(1)=f(3)=0,\,f(2)=f(5)=1,\ f(4)=2\\f(n)=f(n-2)+f(n-4)+f(n-5)\quad\text{if }n\ge6$$
Then $f(7)=f(2)+f(5)=2$, which corresponds to the stamps $2+5$ and $5+2$. That's fine if you actually want to distinguish between ordered sums (like if you were interested in the order in which stamps were placed on an envelope to add up to $7$ cents. But it probably isn't.
The problem can't actually be solved with a recurrence relation, not even a non-linear one. $^{\color{blue}{\text{[citation needed]}}}$ What you need to do is to check out the last chapter of your combinatorics textbook, which will talk about generating functions. Here is a thread that talks about the canonical problem of this genre, which is counting the $293$ ways to make change for a dollar from coins with values of $1,5,10,25,50,$ and $100$ cents. In the case of your problem, the solution is the coefficient of $x^{20}$ in the polynomial $$\frac1{(1-x^2)(1-x^4)(1-x^5)}$$
This sequence is OEIS A025802, and the values from $f(0)$ through $f(61)$ are
So f(20)=10. If $(x,y,z)$ represents buying $x$ 2-cent stamps, $y$ 4-cent stamps, and $z$ 5-cent stamps, the ten different arrangements are