How many ways can you pay $100 when the order in which you pay the coins matters?

Question

Suppose there is a vending machine where you have to pay $100. You have an unlimited amount of 1 dollar, 2 dollar and 5 dollar coins. How many ways can you pay when the order in which you pay the coins does not matter? Also, find the ways when the order matters.

Using generating functions, I solved the first part, i.e., we need to find the coefficient of $x^{100}$ in $$(1+x + x^2 + \dots)(1+x^2 +x^4+ \dots)(1+x^5+x^{10}+\dots).$$

However, I am stuck in the second part. How do we maintain the order while finding the number of ways?

Answer 1

You could use the recursion $$f(n)=f(n-1)+f(n-2)+f(n-5)$$

Answer 2

You have the Diophantine equation $a + 2b + 5c = 100$, and you have already found out the number of solutions.

If a,b,c, are distinct for each solution, the number of ways could be found out as $\dfrac{(a+b+c)!}{a!b!c!}$, but they may not always be distinct

You can't have $a = b = c$ (why ?) but you can have $a=b,\; a=c,\; b=c$

These can be ferreted out (they will not be many), and the usual correction for permutations with repeated elements be made.

Answer 3

Since you were happy with your generating function solution to the first question, let me explain a generating function approach to the second question.

The first question, without the money changing context, asks for the number of integer partitions of 100 using parts 1, 2, 5. Let $a(n)$ be the number of such partitions of $n$. Then $$ \sum_{n=0}^\infty a(n)x^n = \frac{1}{(1-x)(1-x^2)(1-x^5)}$$ which expands as you said.

The second question is about integer compositions, where "order matters." Write $b(n)$ for the number of compositions of $n$ using parts 1, 2, 5. Then $$ \sum_{n=0}^\infty b(n)x^n = \frac{1}{1-x-x^2-x^5}= 1 + (x+x^2+x^5) + (x+x^2+x^5)^2 + (x+x^2+x^5)^3 + \cdots$$ and you want the coefficient of $x^{100}$ in that expansion. Here, for instance, $(x+x^2+x^5)^2$ accounts for all the compositions of two numbers with parts from $\{1, 2, 5\}$.

You can see how this matches the recurrence provided by Empy2. The corresponding sequence is A079971 in the On-Line Encyclopedia of Integer Sequences where someone has worked out a direct formula which is a double-sum of binomial coefficients.