Find the generating function. Put stamps in order and for a specific value.

Question

We have stamps of 3-cent, 4-cent and 20-cent and it is required to put stamps on an envelope of total cost n cents. The order in which we put the stamps does matter. For example for n = 40 the order [3][3][4][3][4][20][3] is different from [3][4][3][3][4][20].

Answer 1

Hint:

You know that $(x^3 + x^4 + x^2)^k$ is the generating function whose $n$th coefficient tells you how many ways there are to make $n$ with exactly $k$ stamps. So if you want to make $n$ with any number of stamps, then that's going to be

(the number of ways to make $n$ with 0 stamps) plus (the number of ways to make $n$ with 1 stamp) plus (the number of ways to make $n$ with 2 stamps) plus (the number of ways to make $n$ with 3 stamps) plus ...

So if $a_{n,k}$ is the coefficient of $x^n$ in $(x^3 + x^4 + x^2)^k$, then you want the coefficient of $x^n$ in the solution, to be $a_n = \sum_k a_{n,k}$.

Do you see how to find this generating function using the $(x^3 + x^4 + x^2)^k$ that you already have?

---

I hope this helps ^_^