Associated Topics || Dr. Math Home || Search Dr. Math

### 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,
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

- 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
ACCD
ACDD

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
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
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search