How to find the number of solutions for $x_1+2x_2+5x_3=10$?

Question

This is a question taken from Discrete mathematics by Kenneth Rosen:

Find the number of ways to make change for \$100 using \$10, \$20 and \$50 bills.

My approach:

Let number of \$10 notes be $x_1$. Let number of \$20 notes be $x_2$. Let number of \$50 notes be $x_3$.

Then the number of ways is equal to

number of solutions of $10x_1+20x_2+50x_3=100$ and so $x_1+2x_2+5x_3=10$.

Now I don't know how to find the number of solutions to this equation.

Answer 1

first variant

When looking for non-negative integral solutions $x_1,x_2,x_3$ we notice that the possible solutions of $x_3$ in \begin{align*} x_1+2x_2+5x_3=10\tag{1} \end{align*}

are $x_3\in\{0,1,2\}$ since $0\leq 5x_3\leq 10$.

Setting these three values for $x_3$ we consider instead of (1) the three equations \begin{align*} x_1+2x_2&=10\\ x_1+2x_2&=5\\ x_1+2x_2&=0\\ \end{align*}

The first equation has $6$ admissible values $x_2\in\{0,1,2,3,4,5\}$, the second equation has $3$ admissible values $x_2\in\{0,1,2\}$ and the third equation has one admissible value $x_2\in\{0\}$. The value of $x_1$ is then uniquely determined.

The number of admissible solutions of (1) is \begin{align*} \color{blue}{6+3+1=10} \end{align*}

second variant

We follow the comment from @JackDAurizio and use generating functions to find the number of admissible solutions.

Values of $x_3$ represent zero or more multiples of $5$ which can be encoded as \begin{align*} 1+x^5+x^{10}+\cdots=\frac{1}{1-x^5} \end{align*}

We argue similarly when considerung values of $x_1$ and $x_2$. Since the right hand side of (1) is $10$ we look for the coefficient of $x^{10}$ in \begin{align*} \frac{1}{1-x^5}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x} \end{align*}

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series $A(x)$. This way we can write e.g. \begin{align*} [x^n]A(x)=[x^n]\sum_{j=0}^\infty a_jx^j=a_n \end{align*}

We obtain \begin{align*} \color{blue}{[x^{10}]}&\color{blue}{\frac{1}{1-x^5}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x}}\\ &=[x^{10}](1+x^5+x^{10})\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x}\tag{2}\\ &=\left([x^{10}]+[x^5]+[x^0]\right)\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x}\tag{3}\\ &=[x^{10}](1+x^2+x^4+x^6+x^8+x^{10})\cdot\frac{1}{1-x}\\ &\qquad +[x^5](1+x^2+x^4)\frac{1}{1-x}+[x^0]\frac{1}{1-x}\tag{4}\\ &=6+3+1\tag{5}\\ &\color{blue}{=10} \end{align*} showing the number of solutions is $10$.

Comment:

• In (2) we expand $\frac{1}{1-x^5}$ up to $x^{10}$ since other terms do not contribute to $[x^{10}]$.

• In (3) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (4) we expand $\frac{1}{1-x^2}$ similarly as we did in (2).

• In (5) we notice that we could work as we did in (3) and since $\frac{1}{1-x}=1+x+x^2+\cdots$ each term has a contribution of $1$.