Counting Techniques

Date: 12/28/97 at 10:09:37
From: Kate
Subject: Counting Techniques

Problem: Find the number of positive divisors of 17640, inclusive of 
1 and 17640 itself. 

I have no idea how to do this. Please help me. 
Thanks.

Date: 01/03/98 at 09:01:58
From: Doctor Mitteldorf
Subject: Re: Counting Techniques

Hello, Kate - 

Sounds to me like you're taking a course in fundamentals of 
statistics. Counting techniques are useful in building up your 
experience and your arsenal of techniques to apply in statistics 
problems.

Take 17640 and look for numbers that can divide it.  Well, it's 
certainly divisible by 2. So go ahead and divide it by 2, and find 
8820. That's still divisible by 2. How many times can you divide it by 
2?  Keep track as you keep dividing it. When you're done, you may 
notice other numbers that divide it. Since it ends in a zero, it looks 
like it's divisible by 5, for example.  

Eventually, you will have decomposed 17640 into prime numbers. You 
will have an expression that looks something like

     17640 = 2*2*2*2*3*3*5*5*5*7*7*7

This isn't the right number of 2's and 3's and 5's and 7's - you can 
work that out for yourself.

Now you have a decomposition of your number into prime factors, how
does that help you count the number of divisors?  Well, let's consider 
a recipe for a divisor: You can make a divisor by multiplying prime 
factors together. You can take any combination you want, and it will 
still be a divisor. 

I won't do 17640 for you, but I'll do 504. 504 consists of 3 two's, 
two 3's, and a 7. (504=2*2*2 * 3*3 * 7) Then your recipe would be 
this:

     - Take any number of 2's, 0,1,2 or 3.
     - Take any number of 3's, 0 1 or 2.
     - Either take the lone 7 or leave it.

You can make a divisor for 504 in any combination of ways. The first
line above gives you 4 possibilities, the second line 3, and the third 
line 2 possibilities. So there are 4*3*2 possibilities, that's 24 
possible divisors. (Have we counted 1?  Have we counted 2?  Have we 
counted 504 itself?)

Please write back with some of your own thinking on the next problem. 
And do let me know what you got when you finished this example for 
17640.

-Doctor Mitteldorf,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 01/04/98 at 03:06:53
From: Kate
Subject: Re: Counting Techniques

Prime factorization of 17640:
2*2*2*3*3*5*7*7 = 17640
2s = 4 possibilities
3s = 3 possibilities
5s = 2 possibilities
7s = 3 possibilities
4*3*2*7 = 72 divisors!

Date: 01/04/98 at 06:13:21
From: Doctor Mitteldorf
Subject: Re: Counting Techniques

Good work!

What do you think about 1 and 17640? Are they included in your 72? 
 
-Doctor Mitteldorf,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/29/97 at 02:03:10
From: Kate
Subject: Counting

Find the no. of odd integers between 2000 and 7000 which do not have 
repeated digits.

Date: 12/29/97 at 14:58:09
From: Doctor Mitteldorf
Subject: Re: Counting

Dear Kate,

I'm going to interpret "no repeated digits" to mean that no two
consecutive digits can be repeated; in other words, 2101 counts, but
2113 doesn't.

Let's see:  The first digit can be 2, 3, 4, 5 or 6 - that's 5 
possibilities.  

The last digit can be 1, 3, 5, 7, or 9 - that's 5 
possibilities.  

And the middle digits can be 0..9, for 10 possibilities each.  

Multiplying all these together there are 5*10*10*5 = 2500 odd numbers 
between 2000 and 7000.

Let's count the ones that have the first two digits the same: there
are 250 of these, starting with 22xx for 50, 33xx for 50, etc. How 
many have the second and third digits the same? also 250, this time 
5*10*5. And 250 more have the last two digits the same. So we have 
750 exceptions, and we're down to 1750.

But we've double-counted some of the exceptions. We double-counted all 
the ones that are 222x and 333x and 444x and 555x and 666x, since we 
excluded them once for having the first two digits the same and once
for having the 2d and 3d digits the same. So that's 25 we double-
counted that have to be added back. Similarly, there are 25 more of 
the form x111, x333, x555, x777 and x999 that have to be added back. 
And 25 more of the form xxyy, where the first two digits match and the 
last two digits match. So we add back 75 and we're back up to 1825.

One more correction:  in our double-count correction, we've also done 
some double-counting - triple counting, actually. We have added back 
3333 three times, once because it was a 333x number and once because 
it was an x333 number and once because it was an xxyy number. Same 
story with 5555. So we need to correct the add-backs by taking away 
two extra times 3333 was counted and two of the extra times 5555 was 
counted. That's a total of 4 add-backs to remove, bringing us down to 
1821.

This reasoning gets us to 1821, and I hope it illustrates for you one
way to think about this kind of question. But 1821 is not the right 
answer - I've written a computer program to count explicitly, and that 
comes out to 1823, which I'm convinced IS the right answer. So 
somewhere in my reasoning, I believe that I missed by 2. I'm going to 
leave this for you to figure out (please tell me if you do!) or for 
another Doctor Math to give us a hand.

-Doctor Mitteldorf,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/29/97 at 18:07:30
From: Doctor Mitteldorf
Subject: Re: Counting

Hi, Kate -

Here's an addendum to my other answer.  I was concerned about the 
difference between 1821 and 1823.  The discrepancy has do to with 
those two numbers 3333 and 5555.

When they were excluded, they were excluded 3 times each - once 
because they were 33xx, once because they were x33x, and once because 
they were xx33. Then when they were added back, they were added back 
three times. We need to just re-exclude them once each to make the 
computation whole; that is, subtract 2 from 1825 to get 1823. This is 
the right answer.

-Doctor Mitteldorf,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 01/01/98 at 03:34:10
From: Kate
Subject: Re: Counting

Dr. Math,

My teacher says that "no repeated digits" means none of the digits is 
used twice, wherever they may be located in the number. That means 
2010 does not count either. How may I solve the problem with this 
constraint?

Kate

Date: 01/01/98 at 07:05:05
From: Doctor Mitteldorf
Subject: Re: Counting

Dear Kate,
 
Why don't you try working this out, applying the method I described
before. It's a little simpler with your teacher's definition of 
"repeated digit." 

Start with 5 possibilities for the first digit (2,3,4,5,6), 10 for the 
second and third digits and 5 for the fourth (1,3,5,7,9). Once you've 
chosen the first digit, there are 9 possibilities for the second that
don't duplicate; then there are 8 possibilities for the third that 
don't duplicate either of the other two, so we have 5*9*8 
possibilities going into the fourth digit... but then things get 
complicated, because there are only 5 possibilities to begin with for 
the 4th digit, and whether we're constrained further depends on what 
we used in the first three.

So we could go back and do things in a different order:  The first 
digit, then the fourth, then the other two.  There are two numbers 
overlapping between the list of possibilities for the first and fourth
digits.  If there were no overlapping numbers, then we'd have 5*5 = 25
possibilities for the first and fourth together; if all 5 overlapped, 
we'd have 5*4 = 20 possibilities that don't repeat.  As it is, we have 
5 possibilities for the fourth digit if the first is chosen as 2, 4, 
or 6 and 4 possibilities for the fourth if the first is chosen as 3 
or 5.  So for allowed combinations of first and fourth, we have 
3*5 + 2*4 = 23.

In any case, we have 8 remaining possibilities for the second digit 
and 7 remaining for the third, so the total I get is 23*8*7 = 1288.  
A computer count gives the same.
   
-Doctor Mitteldorf,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/