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

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. • What is the coefficient of$x^{10}$in the Taylor series at the origin of $$\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\frac{1}{1-x^5}$$ ? Oct 30, 2017 at 15:59 • I will tell you even more: due to the triple pole at$x=1$, the number of ways for changing$n$dollars approaches$\frac{(n+1)(n+7)}{20}$for large values of$n$. Oct 30, 2017 at 16:02 • It should take about 1 minute to "brute force" through all of the solutions. Oct 30, 2017 at 16:04 • For a typesetting note, if you want a dollar sign to appear as an actual dollar sign, put a slash in front of it like \$, otherwise it will be used to initiate in-line mathmode. Oct 30, 2017 at 16:04
• Is it same as searching for coefficient of $x^{10}$ in $(1+x+x^2+x^5)^{10}$? still no improvement. Oct 30, 2017 at 16:05

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

• I understood your first solution.I can understand the second solution that you have posted using generating functions upto the point where you have started using coefficient of operator $[x^n]$. I don't understand how this operator works. Please elaborate a little about this operator. Oct 30, 2017 at 17:38