Generating function and currency

Question

We assume that we have a country's currency that contains three coins worth 1, 3, and 4. How many ways can we get an amount of $n$ using these three pieces? In others words what is the number of partitions of $n$ into $1, 3$, and $4$?

What is the answer if $n=10$?

Is there a formula for the expression of $a_n$ in the general case of $n$? This is equivalent to find the number $a_n$ of positives integers $(a,b,c)$ solution of equation $a+3b+4c=n$, with $n$ positive integer. It well known that the number is the coefficient $a_n$ of $x^n$ in the generating function $\left(1+x+x^2+x^3+\ldots\right)\left(1+x^3+x^6+x^9+\ldots\right)\left(1+x^4+x^8+x^{12}+\ldots\right)\dots$

What are the calculation methods?

Answer 1

Thank you Gerry Myerson

I find the sequence $a_n$ for the G.f.: $$\frac{1}{(1-x)(1-x^3)(1-x^4)}$$

$1, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15, 17, 18, 20, 22, 24, 26, 28, 30, 33, 35, 37, 40, 43, 45, 48, 51, 54, 57, 60, 63, 67, 70, 73, 77, 81, 84, 88, 92, 96, 100, 104, 108, 113, 117, 121, 126, 131, 135, 140, 145, 150, 155, 160, 165, 171, 176, 181, 187, 193, 198…$ Then $a_{10}=8$

And the formula $a_n=\lfloor(\frac{n^2}{24}+\frac{n}{3}+1)\rfloor$

We can verify in this formula $a_{10}=\lfloor(\frac{100}{24}+\frac{10}{3}+1)\rfloor=4+3+1=8$

That means, there are 8 ways to get an amount of 10 using coins worth 1, 3, and 4.

We can count the different ways: $(10,0,0);(7,1,0);(6,0,1);(4,2,0);(3,1,1);(2,0,2);(1,3,0); (0,2,1)$.

The set of all those triplets is the solution set of the equation $a+3b+4c=10$, $a,b$ and $c$ are positive integers.

Very nice application of generating functions, isn't it?