Phone Numbers With Duplicate DigitsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/