Phone Numbers With Duplicate Digits

Date: 03/25/2003 at 10:52:26
From: David
Subject: Different possible phone numbers

Someone is trying to remember a phone number but cannot remember 
the whole thing. He remembers 279-XXXX. He also remembers that the 
last 4 numbers must contain a 2 and a 7 and a 9. He only has 2, 7, or 
9 as digits. How many possible completions are there? 

It seems there is an elegant or overall theory to figure this problem 
but I could not think of one. Everyone in our office believes it 
involves factorials but we can not figure out how.

Date: 03/31/2003 at 16:27:02
From: Doctor Ian
Subject: Re: Different possible phone numbers

Hi David, 

We only get to duplicate one digit, so if we ignore order, there are 
only three possible combinations:

  2279
  2779
  2799

There's no way to arrange the digits from one of these combinations to 
get anything in another combination, since we'd have to change one of 
the letters.  

So if we can figure out how many unique arrangements there are in any 
combination, we can triple that to get the total number of possible 
phone numbers.   
  
Since there's nothing special about any of these combinations, let's 
look at the first one:

  2279

Let's pretend for a moment that we can tell the difference between the 
2's. That is, we'll call one of them 2_a, and the other 2_b. Now there 
are 4 choices for the first digit, 3 choices for the second, and so 
on, for a total of

  4 * 3 * 2 * 1 = 12 

                = 4!
  
arrangements. However, note that wherever we can have

  ... 2_a ... 2_b ...   
  
we'll also get

  ... 2_b ... 2_a ...
  
Which means that we have half as many arrangements as if the digits 
were unique, i.e., 4!/2, or 12.
 
So there are 12 unique arrangements of each combination, which gives 
us a total of 36 possible telephone numbers. 

To get a feel for how this generalizes, suppose we need to come up 
with the last five digits, and we know that one of them will appear 
three times, e.g., 27779 or 29722, but not 27279.  
  
Again, let's consider the combination 22279.  Now if the 2's were 
distinct, we'd have 

  5 * 4 * 3 * 2 * 1 = 60

                    = 5!

possible arrangements. But there are 3! ways to arrange the 2's:

  1) ... 2_a ... 2_b ... 2_c ...
  
  2) ... 2_a ... 2_c ... 2_b ...

and so on.  So now the number of unique arrangements of each
combination is

           5 * 4 * 3 * 2 * 1             
  5!/3! = ------------------- = 20
                   3 * 2 * 1

So you're right, it definitely involves factorials. Even when we 
divided by 2, it was really 4!/2!, and not just 4!/2.  

Can you see what would happen if, instead of tripling one digit, we
needed to double two of them?  

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/