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

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

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

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

-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/
```
Associated Topics:
High School Statistics
Middle School Division