Coinbinations (2)

Let the numbers of quarters, dimes, nickels and pennies need to make up 1 dollar or 100 cents be $q$ , $d$ , $n$ , and $p$ respectively. Then we have $25q+10d+5n + p = 100$ . And note that $q$ can have 5 values from 0 to 4. For a $q$ , $d$ can take the value from 0 to $\left \lfloor \frac {100-25q}{10} \right \rfloor$ , where $\lfloor \cdot \rfloor$ denotes the floor function . For a $q$ and a $d$ , $n$ can take the value from 0 to $\frac {100-25q-10d}5$ . For a $q$ , a $d$ , and a $n$ , there can be only 1 value of $p$ . Therefore, to find the total number of ways to pay with the four kinds of coin $N$ , we need only to calculate the total number of combinations of $(q, d, n)$ .

$\begin{aligned} N & = \sum_{q=0}^4 \sum_{d=0}^{\left \lfloor \frac {100-25q}{10}\right \rfloor} \left(\frac {100-25q-10d}5 + 1\right) \\ & = \sum_{q=0}^4 \sum_{d=0}^{\lfloor 10-2.5q\rfloor} (21-5q-2d) \\ & = \underbrace{\sum_{d=0}^{10} (21-2d)}_{q=0} + \underbrace{\sum_{d=0}^7 (16-2d)}_{q=1} + \underbrace{\sum_{d=0}^5 (11-2d)}_{q=2} + \underbrace{\sum_{d=0}^2 (6-2d)}_{q=3} + \underbrace{\sum_{d=0}^0 (1-2d)}_{q=4} \\ & = 231 - 110 + 128 - 56 + 66 - 30 + 18 - 6 + 1 - 0 \\ & = \boxed{242} \end{aligned}$

The 'count' column is merely nickels+1 because you can replace any amount of n nickels with 5 pennies in n+1 ways.

The sum of the 'count' column is $\boxed{242}$ . You can add the numbers with clever tricks because there are simple sequences of even or odd numbers.

Sort the cases by the number of pennies used. Since a nickel, a dime and a quarter are all multiples of $0.05, we have that in order to obtain a total of $1.00, a multiple of $0.05 itself, the number of pennies must be divisible by 5.

This means that we can instead consider the number of ways in which $0.00, $0.05, $0.10, ..., $0.95, $1.00 can be made up of nickels, dimes and quarters. Dividing both sides by $0.05 gives us that we can alternatively look at the number of ways in which every number from $0$ to $20$ can be represented as a sum of $1$ 's, $2$ 's and $5$ 's.

Label the number of ways $k$ can be represented as a sum of $1$ 's, $2$ 's and $5$ 's as $N(k)$ . Notice that $N(k-5)$ counts the number of such representations that contain at least one $5$ (one way to think about this: given that a representation contains a $5$ , one can simply write down the number and then choose the other summands for which there are $N(k-5)$ ways by definition). Similarly, $N(k-2)$ counts the number of such representations that contain at least one $2$ . Notice further that $N(k-7)$ counts the number of such representations that contain a $5$ and a $2$ . Hence the number of representations that contain any $5$ 's or $2$ 's is given by $N(k-2)+N(k-5)-N(k-7)$ However, there is only one representation for $k$ which contains no $5$ 's or $2$ 's: namely the one consisting of $k$ $1$ 's. So we obtain the recurrence relation $N(k)=N(k-2)+N(k-5)-N(k-7)+1$ Solving by hand yields

• $N(0)=1$
• $N(1)=1$
• $N(2)=2$
• $N(3)=2$
• $N(4)=3$
• $N(5)=4$
• $N(6)=5$

From here one could either try to solve the difference equation with the given initial conditions (which would include solving a 7th degree polynomial) or just repeatedly apply the recurrence relation to obtain the values of $N(k)$ for $7 \leq k \leq 20$ . Adding all these to the above ones yields the answer $\boxed{242}$ .

The way we will choose our coin combination will be by choosing the number of quarters, then the number of dimes, then nickels, then filling in the remainder with pennies.

For now, let's only consider the coin combinations with $0$ quarters:

For the combinations with $0$ dimes, there are $21$ possible combinations, as there can be any number of nickels between $0$ and $20$ inclusive.

For every extra dime, there will be $2$ fewer possible combinations, as we will only be able to use up to so many nickels.

This means the number of combinations with $0$ quarters is $21+19+17+...+3+1$ . Following the same logic with the others:

From here, we can use the formula for triangle numbers $\frac{n(n+1)}{2}$ to quickly find the total:

For $1$ and $3$ quarters, we would need $2\times\frac{8(8+1)}{2}$ and $2\times\frac{3(3+1)}{2}$ respectively. (Consider $6+4+2 = 2\times(3+2+1)$ .)

For $0$ and $2$ quarters, we need the slightly more complicated $(\frac{21\times22}{2})-(2\times\frac{10\times11}{2})$ and $(\frac{11\times12}{2})-(2\times\frac{5\times6}{2})$ . This gives us:

$121+72+36+12+1=\boxed{242}$

We wish to find the coefficient of the $x^{100}$ in the expansion of the generating function $\left(\dfrac{1}{1-x}\right) \left(\dfrac{1}{1-x^{5}}\right) \left(\dfrac{1}{1-x^{10}}\right) \left(\dfrac{1}{1-x^{25}}\right)$ . Here $x$ is a placeholder variable whose exponent represents an additive value (such as amount of money) and whose coefficient represents the number of combinations. With a computational tool this can be computed as $\boxed{242}$ .

Find coefficient of x^100 = 242 in expansion of product of generating function

{1/(1-x)}{1/(1-x^5)}{1/(1-x^10)}{1/(1-x^25)},

Used WolframAlpha Script

SeriesCoefficient[1/(1 - x)×1/(1 - x^5)×1/(1 - x^10)×1/(1 - x^25), {x, 0, 100}]

Answer=242

Read the following pdf/link for details, hope it helps,

https://arxiv.org/pdf/1406.5213

https://arxiv.org/abs/1406.5213

Another Method

Find number of non-negative solutions (w,x,y,z) to the following Diophantine equation:

w+5x+10y+25z=100.

Python3 program can be written to solve this equation as below:

import array as a

a=a.array('i',[1, 5, 10, 25])

n=100

def diophantine_count(a,n):

"""Computes the number of nonnegative solutions (x) of the linear
Diophantine equation
    a[0] * x[0] + ... a[N-1] * x[N-1] = n

Theory: For natural numbers a[0], a[2], ..., a[N - 1], n, and j,
let p(a, n, j) be the number of nonnegative solutions.

Then one has:
    p(a, m, j) = sum p(a[1:], m - k * a[0], j - 1), where the sum is taken
    over 0 <= k <= floor(m // a[0])

Examples
--------
>>> diophantine_count([3, 2, 1, 1], 47)
3572
>>> diophantine_count([3, 2, 1, 1], 40)
2282
"""
def p(a, m, j):
    if j == 0:
        return int(m == 0)
    else:
        return sum([p(a[1:], m - k * a[0], j - 1)
                    for k in range(1 + m // a[0])])

return p(a, n, len(a))

print(diophantine_count(a,n))

Answer=242

Using Wolfram Mathematica 11..3.

Yes, this could have done in other languages. that support recursion, big integers and memoization of previously computed answer.

Another example of this class of problem: How many ways of making change for a $1000 banknote, including just returning the input, and using combinations of $500, $100, $50, $20, $10, $5, $2, $1, $0.50, $0.25, $0.10, $0.05 and $0.01 bills or coins.