3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Jair Taylor Jun 24 '17 at 9:07
4
$\begingroup$

If Im not wrong I think that the following

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

$\endgroup$
  • 2
    $\begingroup$ 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)$. $\endgroup$ – G Cab Jun 24 '17 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.