Recurrence relation and permutations

Question

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:

1. Recurrence relation: $f(n) = f(n - 2) + f(n-4) + f(n-5)$

2. 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$.

3. 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!

Answer 1

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

1, 0, 1, 0, 2, 1, 2, 1, 3, 2, 4, 2, 5, 3, 6, 4, 7, 5, 8, 6, 10, 7, 11, 8, 13, 10, 14, 11, 16, 13, 18, 14, 20, 16, 22, 18, 24, 20, 26, 22, 29, 24, 31, 26, 34, 29, 36, 31, 39, 34, 42, 36, 45, 39, 48, 42, 51, 45, 54, 48, 58, 51

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

(10,0,0), (8,1,0), (6,2,0), (4,3,0), (2,4,0), (0,5,0)
(5,0,2), (3,1,2), (1,2,2)
(0,0,4)

Answer 2

I suppose that you are talking about "The Coin Change Problem" which is a classical combinatorial problem.

Let $f(m, n)$ be the number of ways to give a change equal to $n$ using the coins $v_1, v_2, ..., v_m$. Note that

• If you have 0 coins, there is no way to give any change.
• If you need to give a change equal to 0, you can give an empty set of coins.
• And for $n<0$, it is a degenerated case.

$$f(0,n)=0 \forall n\geq 1,\quad f(m,0)=1 \forall m , \quad f(m,n)=0 \forall n<0$$

You can count the total ways to give a change $n$ dividing your solution into two disjoint sets whose union forms the total number:

• $f(m-1,n)$ without to use the coins $v_m$
• $f(m, n-v_m)$ the number of ways to give a change equal to $n-v_m$ (because you can complete this idea using one more coin $v_m$)

$$f(m, n)=f(m-1, n)+ f(m, n-v_m)$$

Answer 3

For the 20 cent case ( having tried PARI GP on a similar case before), you can easily list them all:

1) four 5 cent pieces (1 permutation)

2) two 5 cent pieces, five 2 cent pieces (21 permutations)

3) two 5 cent pieces, one 4 cent piece, three 2 cent pieces (60 permutations)

4) two 5 cent pieces, two 4 cent pieces, one 2 cent piece (30 permutations)

5) ten 2 cent pieces(1 permutation)

6) one 4 cent piece, eight 2 cent pieces ( 9 permutations)

7) two 4 cent pieces, six 2 cent pieces ( 28 permutations)

8) three 4 cent pieces, four 2 cent pieces ( 35 permutations)

9) four 4 cent pieces, two 2 cent pieces ( 15 permutations)

10) five 4 cent pieces (1 permutation)

2 has 1 permutation, 4 has 2, 5 has 1, 6 has 3, 7 has 2, 8 has 5, 9 has 4 ...

There are a few patterns to consider:

• the next even number has at least as many as the previous, plus the sum of the ceilings of the odd number of 2 partitions ( divide by 2 replacing with 4s as you go), plus the ceilings even number of 2 partitions ( each pair can be replaced by a 4 in both the latter including the 2 you add on in the middle ones).

• Odd numbers relate to the previous multiple of 5 with the same as above for the 2s and 4s.