0

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

Vaios Argiropoulos
  • 143
  • What have you tried? We can help you better once we know exactly where you're stuck ^_^ – HallaSurvivor Nov 15 '20 at 03:22
  • @HallaSurvivor If it was given to us that there is exactly k positions for the stamps we could write $(x^3 + x^4 + x^20 )^k$ as a generating function and $x^n$ would have given us our desired number. The problem is that we don't know the exact number of stamps. – Vaios Argiropoulos Nov 15 '20 at 07:21

1 Answers1

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 ^_^

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87