0
$\begingroup$

In how many ways can we select five coins from a collection of 10 consisting of one penny, one nickel, one dime, one quarter, one half-dollar, and 5 (identical) Dollars?


I think the answer is the number of the nonnegative solutions to the following equation: $$a_1+a_2+a_3+a_4+a_5+a_6=5$$ $$0\le a_i \le 1 \;\;\;\text{for}\;\;\;1\le i\le5$$ $$0\le a_6 \le 5$$

The answer is given by $2^5$.

I have two questions:

Does the equation give the answer?

If yes, then how to solve it, and if no then why?

An answer has been already given at this site, but my question is different.

$\endgroup$
2
  • $\begingroup$ Yes, the question is equivalent to the question of counting the number of non-negative solutions to your system with the given constraints. How to utilize this? The easiest is to use generating functions and look at the coefficient of $(1+x)^5(1+x+x^2+x^3+x^4+x^5)$ which you plug into a calculator or recognize the symmetry of the problem, relating it to the binomial theorem and seeing it will be $2^5$. Otherwise, it is far easier in my opinion to recognize you can take any subset of the five smaller coins and fill out the remaining positions with the dollar coins, giving $2^5$ ways. $\endgroup$
    – JMoravitz
    Oct 18, 2020 at 14:01
  • $\begingroup$ If you insist on trying to solve the question of the number of non-negative solutions to the system without generating functions and without appealing to logic like I had... you could feasibly use stars-and-bars and inclusion-exclusion, however this is going to be incredibly tedious and is not recommended. $\endgroup$
    – JMoravitz
    Oct 18, 2020 at 14:02

2 Answers 2

1
$\begingroup$

As we need to choose $5$ coins from $10$ coins where $5$ are distinct coins and $5$ are identical coins, either all $5$ coins can come all from identical set (zero from distinct set) or all from distinct set, and all combinations in between. That simply means it is $2^5$ ways (two possibilities for each distinct coin = "chosen" or "not chosen").

But if this is not intuitive enough, we can also say that

Number of combinations in which no ($0$) distinct coin is chosen = ${5 \choose 0}$

Number of combinations in which $1$ distinct coin is chosen = ${5 \choose 1}$

Number of combinations in which $2$ distinct coins are chosen = ${5 \choose 2}$

...

Number of combinations in which all $5$ distinct coins are chosen = ${5 \choose 5}$

Total number of possibilities $ = {5 \choose 0} + {5 \choose 1} + {5 \choose 2} + {5 \choose 3} + {5 \choose 4} + {5 \choose 5} = 2^5 = 32$

$\endgroup$
1
$\begingroup$

Let $S$ be the set of coins excluding the dollars.

Then $|S|=5$, so $S$ has exactly $2^5$ subsets.

For each subset of $S$ there is a unique $5$-tuple $(x_1,...,x_5)$ with $$ 0\le x_1+x_2+x_3+x_4+x_5\le 5 $$ where $x_1,...,x_5\in\{0,1\}$, hence by letting $$ x_6=5-(x_1+x_2+x_3+x_4+x_5) $$ we get a unique $6$-tuple $(x_1,...,x_6)$ satisfying the required conditions.

Conversely, for each $6$-tuple $(x_1,...,x_6)$ satisfying the required conditions, the $5$-tuple $(x_1,...,x_5)$ satisfies $$ 0\le x_1+x_2+x_3+x_4+x_5\le 5 $$ with $x_1,...,x_5\in\{0,1\}$, which corresponds to a unique subset of $S$.

From the one-to-one correspondence it follows that the answer is $2^5$.

$\endgroup$
1
  • $\begingroup$ @45465: Your posted question didn't specify a generating functions approach. My solution shows how the number of solutions to your equation-based interpretation is the same as the number of subsets of a $5$ element set. $\endgroup$
    – quasi
    Oct 18, 2020 at 16:16

You must log in to answer this question.