Combinations of Coins

Date: 1/28/96 at 20:50:9
From: Anonymous
Subject: math problem about coins

If I had 6 coins in my pocket, how many combinations can I have?

Date: 1/31/96 at 17:40:34
From: Doctor Syd
Subject: Re: math problem about coins

Hello!

I'm glad you wrote.  There are a couple of different ways to 
approach your problem, and there are also a couple of ways to 
interpret it. So, to avoid confusion, let's talk about 
interpretations. You could ask two questions about combinations of 
6 coins in your pocket. First, you could ask how many combinations 
can you have so that that the total amount of money you have is 
different for each combination. Or, second, you could ask simply 
how many combinations you can have, regardless of what the sum of 
the values of the coins is.  

The second question is easier and more general, and that is the 
one I will use.  Maybe you can try yourself to work out the first 
question!  

Now, let's assume that there are 5 different coins (the penny, the 
nickel, the dime, the quarter, and the half-dollar).  So, how many 
different combinations of these 5 types of things can we have if 
we want to end up with 6 different objects?  We could ask this 
question about lots of different objects...not just coins.  It is 
the same as the question, how many ways can we arrange 5 different 
types of flowers in a bunch if we want our bunch to contain 6 
flowers, and repetition of flowers is allowed?  You can make up 
lots of different situations where this method will work!

Okay, so how do we solve it?  One way to solve it is pretty slick 
because the same method can be used for other problems that are 
very complicated... using this method we set up something called a 
generating function that is related to the problem.  If you are 
curious, feel free to write back about this.  

A simpler approach to the problem is the following:  Since we are 
looking at combinations (not permuatations), order of the coins is 
unimportant.  So, for our purposes, having 5 nickels and a dime is 
no different from having a dime and 5 nickels, right?  Let us 
impose our own order on the problem and count the number of ways 
we can have 6 coins when pennies come first, then nickels, then 
dimes, then quarters, and finally half-dollars.  This may seem to 
contradict what I just said - that order is unimportant.  But, if 
you think about it for a little bit it may become clear.  If we 
count the number of combinations with the order described above, 
we will have gotten all of the combinations possible.  For 
example, the combination of 3 nickels, a quarter, and 2 dimes will 
appear in our ordered combination as 3 nickels, 2 dimes, and one 
quarter.  Conversely, every combination can be represented by one 
of our ordered combinations.  

Okay, so now think about sitting at a cash drawer and picking out 
6 coins so that you begin with coins of the smallest value and end 
with the coins of the biggest value.  You will make 4 different 
"changes":  1st you will change from picking pennies to picking 
nickels; 2nd you will change from picking nickels to picking 
dimes; 3rd you will change from picking dimes to picking quarters; 
and fourth you will change from picking quarters to picking half-
dollars.  Now, it may happen that in between the changes  you will 
not choose any coins...thus, if you don't choose anything between 
the 1st and 2nd change, you have, in essence, not chosen any 
nickels.  Also, it may happen that you don't even pick any 
pennies.  In this case the first change comes before you even 
start picking coins.  It is easiest to understand this concept 
with a
diagram:

  _ | _ _ | _ || _ _

Here the horizontal lines stand for coins, and the vertical lines 
stand for the changes...Thus the above diagram represents the 
combination consisting of one penny (that's the first horiz. 
line), 2 nickels (those are after the first vert. line), one dime, 
and 2 half-dollars.  The above diagram suggests that the number of 
combinations of coins will be the number of different ways we can 
combine 4 vertical lines and 6 horizontal lines in the above 
diagram.  Think of each line (both horiz. and vert. lines) as a 
place holder of sorts.  There are a total of 10 places.  Let's 
label them 1, 2, 3, ..., 10.  Now from the diagram we can see the 
each arrangement of lines is determined by where the four vertical 
lines are.  In other words, if we know which places the vertical 
lines are in, we can tell where the horizontal lines will be...in 
the empty spaces!!  So, in how many ways can we place the 4 lines 
in the 10 spots?  Mathematicians who have studied combinatorics 
(how you count the number of ways to do things), will spout out 
that this is just "10 choose 4."  This is written,  
     (10)
     ( 4) (sort of!  Notation with the computer is necessarily 
clumsy, but the symbol basically looks like a fraction without the 
dividing bar, and with parentheses enclosing it.)

and is equal to 10!/4!6!.

I don't know if you are familiar with this concept of "n choose 
m."  Basically, "10 choose 4" is the number of ways to choose 4 
elements from a set of 10 elements.  It is equivalent to our 
problem, since the number of ways to put the 4 lines in the 10 
spaces is the number of ways to choose 4 of the 10 spaces in which 
to put the vertical lines.  I won't go into the reasons for the 
formula for "10 choose 4" now, but if you are curious, feel free 
to write back.  

So, what all this tells us is that the number of ways to put the 4 
vertical lines in the diagram is 10 choose 4.  Thus, the number of 
ways to choose 6 coins is also 10 choose 4.  A pretty surprising 
answer, if you've not seen it before!!  

I hope this helps some.  If you are confused by anything I said, 
please do feel free to write back.

-Doctor Syd,  The Math Forum