Choosing Computer Disks

Date: 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