Finding combination using generating function

Question

Q. Find the no of ways of inserting r dolllars using 1 dollar, 2 dollar and 5 dollar tokens,when order doesn't matter and when order doesn't matter. Ans. When order doesn't matter.. $(1+x+x^2+x^3+..)(1+x^2+x^4+..)(1+x^5+x^{10}+..)$ Coefficient of $x^r$ in above generating function. I clearly understand this. But I don't understand the process when order matters. Please somebody explain how (and why) to approach when order matters.

Answer 1

Order Does Not Matter

If the order doesn't matter, then the coefficient of $x^n$ in $$ \begin{align} &\overbrace{\left(1+x+x^2+x^3+\dots\right)}^{\text{exponent = number of $\$1$}}\overbrace{\left(1+x^2+x^4+x^6+\dots\right)}^{\text{exponent = 2 $\times$ number of $\$2$}}\overbrace{\left(1+x^5+x^{10}+x^{15}+\dots\right)}^{\text{exponent = 5 $\times$ number of $\$5$}}\\ &=\bbox[5px,border:2px solid #C0A000]{\frac1{1-x}\frac1{1-x^2}\frac1{1-x^5}}\\ &\small=1+x+2x^2+2x^3+3x^4+4x^5+5x^6+6x^7+7x^8+8x^9+10x^{10}+11x^{11}+13x^{12}\\ &\small\,+14x^{13}+16x^{14}+18x^{15}+20x^{16}+22x^{17}+24x^{18}+26x^{19}+29x^{20}+\dots \end{align} $$ is the number of ways to choose ones, twos, and fives that sum to $n$.

For example, suppose $n=12$. The case of $3$ $\$1$ tokens and $2$ $\$2$ tokens and $1$ $\$5$ token is counted by the $x^3$ term from the first sum times the $x^4$ term from the second sum times the $x^5$ term from the third sum.

Since the denominator of the generating function is $1-x-x^2+x^3-x^5+x^6+x^7-x^8$, the recursion for the coefficients is $$ a_n=a_{n-1}+a_{n-2}-a_{n-3}+a_{n-5}-a_{n-6}-a_{n-7}+a_{n-8} $$

---

Order Matters

If the order matters, break down the generating function into the sum of the generating functions for a given number of tokens: $$ \begin{align} &1+\overbrace{\left(x+x^2+x^5\right)\!\vphantom{\left(x^2\right)^2}}^{\text{one token}}+\overbrace{\left(x+x^2+x^5\right)^2}^{\text{two tokens}}+\overbrace{\left(x+x^2+x^5\right)^3}^{\text{three tokens}}+\dots\\ &=\bbox[5px,border:2px solid #C0A000]{\frac1{1-\left(x+x^2+x^5\right)}}\\ &=1+x+2x^2+3x^3+5x^4+9x^5+15x^6+26x^7+44x^8+75x^9\\ &\,+128x^{10}+218x^{11}+372x^{12}+634x^{13}+1081x^{14}+1843x^{15}+\dots \end{align} $$ Under the six tokens term, we would have a product like $$ \small\left(x+x^2+x^5\right)\left(x+x^2+x^5\right)\left(x+x^2+x^5\right)\left(x+x^2+x^5\right)\left(x+x^2+x^5\right)\left(x+x^2+x^5\right) $$ There is now a term to specify each possible ordering of the tokens. Using the example above, one such term for $3$ $\$1$ tokens and $2$ $\$2$ tokens and $1$ $\$5$ token would be $$ \small\overbrace{\left(x\color{#C0C0C0}{+x^2+x^5}\right)}^{\$1}\overbrace{\left(\color{#C0C0C0}{x+}x^2\color{#C0C0C0}{+x^5}\right)}^{\$2}\overbrace{\left(\color{#C0C0C0}{x+x^2+}x^5\right)}^{\$5}\overbrace{\left(x\color{#C0C0C0}{+x^2+x^5}\right)}^{\$1}\overbrace{\left(x\color{#C0C0C0}{+x^2+x^5}\right)}^{\$1}\overbrace{\left(\color{#C0C0C0}{x+}x^2\color{#C0C0C0}{+x^5}\right)}^{\$2} $$ Since the denominator of the generating function is $1-x-x^2-x^5$, the recursion for the coefficients is $$ a_n=a_{n-1}+a_{n-2}+a_{n-5} $$

Answer 2

When order does matter, the contents of the $k$-th bracket will be the possibilities for the $k$-th token to be inserted, which are $1,2$ or $5$ dollars regardless of $k$.

So a first guess for the generating function that respects order is

$$g(x)=(x+x^2+x^5)\times(x+x^2+x^5)\times(x+x^2+x^5)\times\cdots$$

but this has the problem that the degree of any term in the product is infinite.

But we know that at least $4$ and at most $19$ tokens can be used to make up the amount.

So

$$\begin{align} g(x)&=\sum_{k=4}^{19}{(x+x^2+x^5)^k} \\ &=(x+x^2+x^5)^4\cdot\sum_{k=0}^{15}{(x+x^2+x^5)^k} \\[2ex] &=(x+x^2+x^5)^4\cdot\frac{(x+x^2+x^5)^{16}-1}{x+x^2+x^5-1} \end{align}$$