2
$\begingroup$

A jar contains quarters, loonies, and toonies. If four coins are selected from the jar, how many unique coin combinations are there? The answers is 15.

The solution: "In this question, we know there are quarters, loonies, and toonies in the jar, but no quantity has been specified! Since no quantity has been specified, and it is possible to select the same type of coin more than once, we can treat the coins as being unlimited. Some of the ways we can choose four coins include: LQTL Another possible combination is QQQL. And another possible combination is TTTT. We need a new type of strategy to deal with this problem. Create a chart to keep track of the number of quarters, loonies, and toonies selected. Draw checkmarks and dividers for LQTL. Draw checkmarks and dividers for QQQL. And draw checkmarks and dividers for TTTT. Notice that we can represent each combination as an arrangement of four identical checkmarks and two identical dividers. We can arrange the four identical checkmarks and two identical dividers in: 6!/(4!2!) = 15 ways."

I did not understand 6! and 4!2!.

Thanks

$\endgroup$
  • 1
    $\begingroup$ 6! means 6x5x4x3x2x1 and 4! = 4x3x2x1 and 2! = 2x1. What I don't understand is what the heck "checkmarks" and "dividers" are and how we are supposed to use "Draw checkmarks and dividers for LQTL". What the heck does that mean? $\endgroup$ – fleablood Jun 5 '17 at 0:34
  • $\begingroup$ What do you mean by unique coin combinations?. These QQQL and LQQQ are the same combination or not? $\endgroup$ – JoseA132 Jun 5 '17 at 0:39
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) $\endgroup$ – JMoravitz Jun 5 '17 at 0:41
4
$\begingroup$

As the cited solution suggests, we approach via stars and bars... that is, we describe every way of selecting coins as a sequence of stars and bars (or as they suggest, checkmarks and dividers, I will continue calling them stars and bars for the remainder of this post.)

One can (and should) prove that the set of possible selections of 4 coins of 3 categories is in direct bijection with (and therefore has the same number of elements as) the set of sequences of 4 stars and 2 bars.

We can describe the bijection with words as:

$$\underbrace{~~~~~~~~~~~~~~~~~~~~~~~}_{\text{stars here represent loonies}}\mid \underbrace{~~~~~~~~~~~~~~~~~~~~~~~}_{\text{stars here represent quarters}}\mid\underbrace{~~~~~~~~~~~~~~~~~~~~~~}_{\text{stars here represent toonies}}$$

For example, the sequence $\star\star\mid\star\mid\star$ represents the selection being two loonies, one quarter, and one toonie.

The sequence $\mid\mid\star\star\star\star$ on the other hand will represent our selection being just four toonies and none of the other coins.

Note: This method treats all ways of selecting a particular arrangement of coins as the same so long as the number of each type of coin is the same between the two arrangements, that is to say we treat TQQQ to be the same arrangement as QQQT.

If you did want to treat those two as being different arrangements, approach instead directly via multiplication principle getting instead an answer of $3^4=81$, not $15$.

So, we have the number of arrangements will be the number of sequences of four stars and two bars, which we should know by earlier example can be counted via binomial coefficients as $\binom{6}{2}=\frac{6!}{4!2!}=15$

$\endgroup$
  • 2
    $\begingroup$ Very nice and clear explanation. $\endgroup$ – fleablood Jun 5 '17 at 1:04
  • $\begingroup$ This is one of the clearest stars and bars explanations I've ever read...and boy have I tried to make sense of this for quite some time. Thank you very much. I used to avoid the stars and bars approach, favoring the equation instead. I'm now able to rederive it with ease. Can't thank you enough <3 $\endgroup$ – AleksandrH Jul 13 '17 at 22:28
1
$\begingroup$

Okay. Took me while.

Basically you arrange the coins in order, quarters, loonies, and toonies and you make a check for each coin. When a coin switches value you put a divider.

So example if you have QQLT, you write $\checkmark\checkmark|\checkmark|\checkmark$ meaning two quarters (check, check) we switch to loonies (divider), one loony (check), we switch to toonies (divider), a final toonie (check).

Likewise for QTTT, you write $\checkmark||\checkmark\checkmark\checkmark$. That is one loonie (check), switc to loonie (divide), switch to toonie (divide), three toonies (check, check, check) and $LLLL$ would be $|\checkmark\checkmark\checkmark\checkmark|$ etc.

So how many ways are there to do this. You have six things. $a=\checkmark,b=\checkmark,c=\checkmark,d=\checkmark,e=|,f=|$ which may be checks or dividers. There are $6!= 720$ ways to put six things in order. But of those $720$ ways, whatever order the four checkmarks are, are considered the same. That is QLLT = $a\checkmark, e|, b\checkmark, c\checkmark, f|,d\checkmark$ is the exact same thing as QLLT $d\checkmark, f, a\checkmark,b\checkmark, e|, c\checkmark$

So there are $4!= 24$ ways to plays the checkmarks that are considered exactly the samme and $2! = 2$ ways to place the dividers that are considered exactly the same.

So the total way to do the if $\frac {6!}{4!2!} = \frac {1*2*3*4*5*6}{(1*2*3*4)*(1*2)} = \frac {5*6}{1*2} = 15$.

That are:

QQQQ = $\checkmark\checkmark\checkmark\checkmark||$

QQQL = $\checkmark\checkmark\checkmark|\checkmark|$

QQLL = $\checkmark\checkmark|\checkmark\checkmark|$

QLLL = $\checkmark|\checkmark\checkmark\checkmark|$

LLLL = $|\checkmark\checkmark\checkmark\checkmark|$

QQQT = $\checkmark\checkmark\checkmark||\checkmark$

QQLT = $\checkmark\checkmark|\checkmark|\checkmark$

QLLT = $\checkmark|\checkmark\checkmark|\checkmark$

LLLT = $|\checkmark\checkmark\checkmark|\checkmark$

QQTT =$\checkmark\checkmark||\checkmark\checkmark$

QLTT = $\checkmark|\checkmark|\checkmark\checkmark$

LLTT = $|\checkmark\checkmark|\checkmark\checkmark$

QTTT = $\checkmark||\checkmark\checkmark\checkmark$

LTTT = $|\checkmark|\checkmark\checkmark\checkmark$

TTTT = $||\checkmark\checkmark\checkmark\checkmark$

$\endgroup$
  • $\begingroup$ Thank you! It is so well explained. $\endgroup$ – Julia Benson Jun 5 '17 at 1:16
  • $\begingroup$ Thank you for saying so. To be honest though, I think I like how JMoravitz explained it better. I hope between the two of these it's fairly clear. $\endgroup$ – fleablood Jun 5 '17 at 2:01
  • $\begingroup$ Both explanations are really good. I could not do better. Thank you! $\endgroup$ – Julia Benson Jun 6 '17 at 2:38

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.