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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.