Choosing Computer DisksDate: 12/01/2001 at 16:43:48 From: Julie Herrmann Subject: In how many ways can you choose... Dr. Math, Here is a problem I have been trying to figure out. I don't know if I have thought about it correctly. A bin of computer disks contain a supply of disks from 4 different manufacturers. In how many ways can you choose 6 disks from the bin? First I thought it was just a simple problem. 6! = 720. But now I am thinking more along the lines of 6 choose 4. But I am not sure. 6! __________ = 15? 4!2! Any help would be appreciated. Thanks, Julie Date: 12/01/2001 at 17:22:06 From: Doctor Mitteldorf Subject: Re: In how many ways can you choose... Hi, Julie- Here's a principle to learn NOW, when you're just starting to work with probability: Each problem belongs to itself, and the best way to understand it is to analyze it on its own terms, from the ground up. If you start thinking this way, not only will you have a good foundation for all that you will learn in probability and statistics, but you'll be a step ahead of most adults who (if they think about statistics at all) just try to pick a formula and run with it. So here's an example of what I mean. Think: Pick one disk from the bin. There are 4 ways to do it. Pick another disk. There are 4 possibilities for this one, times 4 for the first, so that's a total of 16 possibilities. But wait: it doesn't matter what order you picked them in. That means we double-counted the possibilities. For example, AB should count the same as BA, but in counting 16 we counted them separately. So maybe there are only 8 ways to choose 2 disks. But wait: one more thing. Sure, AB is the same as BA, and we double- counted that; but we didn't double-count AA or BB, because these are the same "frontward or backward." So, out of the 16, there were 12 that we needed to divide by 2, and 4 that were right as they were. 12/2 + 4 = 10 possibilities. We can list them: AA BB CC DD AB AC AD BC BD CD. For 3 disks, we can think in terms of 3 categories: all the same (AAA, BBB, CCC, DDD); two different (AAB, ABB, AAC, ACC, etc. How many of these are there?); and all three different (ABC, ABD, ACD, BCD for 4 total.) The total number I get for 3 disks is 20 possibilities. Can you list them? I'm going to ask you to do 4 on your own. That's the next step. Actually listing them all is a good exercise, and will give you ideas about ways to categorize and count them. For 5, there may be more than you'll want to list, but you'll have more experience in how to categorize them; and if you get 5, 6 should be easy... I'd like you to go through this exercise and write back to me with the results. You should be able to think all the way through to the answer for 6, if you have some time to spend and your concentration is good. If you write back, I'll share a shortcut with you that works for bigger numbers. But it's a hard shortcut to understand, and you may not like it at all - it may just seem like hocus-pocus. It's hard enough that I doubt your teacher expects you to come up with it on your own. - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/ Date: 12/01/2001 at 22:20:57 From: Julie Herrmann Subject: Re: How many ways Dr. Mitteldorf, I think I have all of the ways for 4 listed, but I am not sure. Here goes: AAAA AABB ABBB BBBB BBCC BCCC CCCC DDDD AAAB AABC ABBC BBBC BBCD BCCD CCCD DDDC AAAC AABD ABBD BBBD BBDD BCDD CCDD AAAC AACC ABCC AACD ABCD AADD ACCC ACCD ACDD ADDD I think those ways added up equal 34. Thank you for your help. At this rate, I think I would like to know that formula before I go crazy. Thanks again, Julie Date: 12/02/2001 at 07:10:35 From: Doctor Mitteldorf Subject: Re: How many ways Hi, Julie - Good work with this. I think you've come up with a good system for making sure you have them all. I see 33 combinations here, not 34. 33 isn't so many to list, is it? How long did it take you? Anyway, hold on to your hat, here goes the explanation of the formula. Suppose, for 6, you had one sample that was AAABDD. It's part of our new system to put the letters in alphabetical order, as you did for almost all of yours in your list. Now I'm going to add separators in the list, to show where the letters change: AAA|B||DD (Notice there are two separators together, which shows there aren't any C's.) Once you've got the letters in alphabetical order and the separators in place, you can tell what the letters are without writing A and B: OOO|O||OO This is our new expression for AAABDD. But why did we go to the trouble of inventing a new system? It's because now we have 6 O's and 3 separators, and they can be placed in any order. And every ordering of these 6 O's and 3 separators corresponds to exactly one way to choose 6 disks. Practice for a few examples to see what I mean: AAAAAB = OOOOO|O|| ABCCCD = ? CCCCCC = ? ABBCCD = ? ACCDDD = ? So now we have a new problem, which is really the same as the old problem: how many ways can these 9 symbols be arranged - 6 Os and 3 |s ? Suppose all 9 symbols were different. Then the ways of arranging them would be 9!. You probably have seen the reason why: You have 9 choices for the first one. Then there are only 8 symbols left for the second, so you have 9*8 ways to choose the first two. Then there are 7 choices for the next symbol, etc. This gives 9*8*7*6*5*4*3*2*1 ways to arrange 9 DIFFERENT symbols. But the symbols are not all different. All 3 separators are the same. And this means that an expression that might be written OOOXOYZOO is the same as OOOXOZYOO, and that's the same as OOOZOXYOO and OOOZOYXOO and OOOYOXZOO and OOOYOZXOO. All 6 of these were counted separately in our 9! arrangements. But they're really all equal to OOO|O||OO. So we need to divide 9! by 6. The 6 came from the different orderings of the letters XYZ. Even though they were scattered through the other letters, there are 3 letters and 3! ways of arranging them. That's where the 6 comes from. Maybe you can guess by now that the same reasoning goes for the 6 O's. All the ways to arrange 6 DIFFERENT letters were counted separately, but since they're all O's they shouldn't be counted as different. So we need to divide by 6! Our answer 9! was overcounted by 6! and it was also overcounted by 3!. This gives our final answer: 9! --------- = 84 6! 3! This is the formula you asked for - it's the number of ways to select 6 CD's when there are 4 possibilities for each CD. You might notice that this is the same as C(9,3). It's not just a coincidence. There's another way to think about expressions like OOO|O||OO that makes it clearer. C(9,3) is the number of ways to choose 3 things out of 9. There are 9 symbols in our expression. Which 3 of them are going to be the separators? There are C(9,3) ways to answer, and that's another explanation why our answer came out to C(9,3). ------------- So now that you understand the formula, you should be able to apply it to 4 disks. What should the count be for ways to choose 4 disks? You got 33 (or maybe 34, but you left one out when you were writing them for me). What was missing from your list? - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/ Date: 07/25/2003 at 11:40:35 From: Katherine Subject: Choosing Computer Disks This is not really a question, but an addendum. Thanks for the insight re: the Choosing Computer Disks question. I was trying to do it for 6 by hand and going a bit crazy before I found your answer. Afterward, I realized that with numbers that are larger, it makes it easier to keep track of the count of each A, B, C... That is, for picking 6 disks of three types, there are only 7 different ways to add three non-negative numbers to equal 6. The twenty-eight final combinations are easy to arrive at once you get the 7 rows: 6 0 0 -- 0 6 0 -- 0 0 6 5 1 0 -- 0 5 1 -- 1 5 0 -- 5 0 1 -- 1 0 5 -- 0 1 5 4 2 0 -- 4 0 2 -- 0 4 2 -- 2 4 0 -- 2 0 4 -- 0 2 4 4 1 1 -- 1 4 1 -- 1 1 4 3 2 1 -- 3 1 2 -- 2 3 1 -- 1 3 2 -- 1 2 3 -- 2 1 3 2 2 2 3 3 0 -- 3 0 3 -- 0 3 3 This seems to work pretty well if you still need to list all of the combinations in addition to knowing the total from the formula. Thanks for having such a useful website! Katherine |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/