# How To Find the Generating Function of the Following Problem

I need to find the generating function of the following problem:

$d_n$ (for every natural number $n$) is the number of combinations to put coins into an automatic machine whereas the sum of the coins is $n$. There are coins of 1,10 and 25 cents and the amount of each coin is not limited.

While I can find the generating function when the order in which the coins are put into the machine doesn't matter, I don't have any idea in the case when the order do matter.

I know that it can be solved with exponential generating functions, but I wonder if there is any solution with "regular" generating functions.

• I don't think you need EGF's here. If the order of coins doesn't matter, you can first choose how many 1-cent coins you want, then the number of 10-cent coins, then the number of 25-cent coins. If the order of coins does matter, then you have an infinite sequence of choices - at each step, choose 1- or 10- or 25-cent coins. – Jair Taylor Jun 24 '17 at 9:07

$$d_n=[x^n]\sum_{k=1}^\infty(x+x^{10}+x^{25})^k=[x^n]\frac{x+x^{10}+x^{25}}{1-(x+x^{10}+x^{25})}$$
count the ordered ways to put coins in the machine up to $n$.
• your answer is correct, since \eqalign{ & \left( {x^{\,1} + x^{\,10} + x^{\,25} } \right)\left( {x^{\,1} + x^{\,10} + x^{\,25} } \right) = \cr & = x^{\,1} x^{\,1} + x^{\,1} x^{\,10} + x^{\,1} x^{\,25} + \cr & + x^{\,10} x^{\,1} + x^{\,10} x^{\,10} + x^{\,10} x^{\,25} + \cr & x^{\,25} x^{\,1} + x^{\,25} x^{\,10} + x^{\,25} x^{\,25} \cr} and that counts either $(10,1)$ and $(1,10)$. – G Cab Jun 24 '17 at 18:50