2
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ 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}$$ ? $\endgroup$ – Jack D'Aurizio Oct 30 '17 at 15:59
  • $\begingroup$ 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$. $\endgroup$ – Jack D'Aurizio Oct 30 '17 at 16:02
  • $\begingroup$ It should take about 1 minute to "brute force" through all of the solutions. $\endgroup$ – Doug M Oct 30 '17 at 16:04
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Oct 30 '17 at 16:04
  • $\begingroup$ Is it same as searching for coefficient of $x^{10}$ in $(1+x+x^2+x^5)^{10}$? still no improvement. $\endgroup$ – jonsno Oct 30 '17 at 16:05
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Kishan Kumar Oct 30 '17 at 17:38
  • $\begingroup$ @KishanKumar: Explanation added. See also for instance this answer. $\endgroup$ – Markus Scheuer Oct 30 '17 at 17:43
  • $\begingroup$ KishanKumar: You're welcome! $\endgroup$ – Markus Scheuer Oct 30 '17 at 18:13

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.