# Recurrence relation and permutations

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!

• Number of ways to give back 20 cents using 2,4,5 cent pieces scales to the problem of giving back a dollar with dimes, quarters, and 20 cent pieces. – Roddy MacPhee Dec 9 '19 at 0:41
• I am not sure what you mean by this can you please elaborate? – David smith Dec 9 '19 at 0:42
• $20\cdot 5=100;5\cdot5=25;4\cdot 5=20;2\cdot 5=10$ – Roddy MacPhee Dec 9 '19 at 0:46
• I still don't really know where you are telling me to go with this. This is to help calculate the possible number of permutations correct? @RoddyMacPhee – David smith Dec 9 '19 at 0:51
• The recurrence in $1.$ is incorrect, because of the problem you mention in $3.$ I don't understand $2$. What is $a_n$? Let $g(n)$ be the number of ways to make $n$ cents of postage using only $4$- and $6$-cent stamps. Then $f(n)=g(n)+f(n-2)$ – saulspatz Dec 9 '19 at 1:20

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)

• This problem must be able to be solved with a recurrence relation. My professor would not write a trick question. @Mathew daly – David smith Dec 9 '19 at 1:37
• But, the solution above is also correct. – Alexandre Frias Dec 9 '19 at 4:21

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

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.

• Thanks for the upvote ( not sure why, it was basic logic) – Roddy MacPhee Dec 9 '19 at 2:41