Department of Energy Argonne National Laboratory Office of Science NEWTON's Homepage NEWTON's Homepage
NEWTON, Ask A Scientist!
NEWTON Home Page NEWTON Teachers Visit Our Archives Ask A Question How To Ask A Question Question of the Week Our Expert Scientists Volunteer at NEWTON! Frequently Asked Questions Referencing NEWTON About NEWTON About Ask A Scientist Education At Argonne Phone Number Permutations
Name: William F.
Status: student	
Age:  N/A
Location: N/A
Country: N/A
Date: N/A 


Question:
What are the odds against two seven digit phone numbers being permutations of each other? More precisely, if neither phone number is specified in advance? And more precisely still, in the early 70's? Back then phone numbers never had a zero or 1 in the first three digits (the exchange). This is I think harder than it looks, because you have to take into account that with repetitions there are going to be fewer than 7! permutations of any randomly selected seven digits.



Replies:
This is a 2-part problem of the number of permutations of digits WITH REPLACEMENT ALLOWED, that is, any digit can appear more than one time. Consider a telephone "number" as: "abc-defg" the three digit exchange 'abc' and the four digit number 'defg'. Most generally: any of the digits:a,b,....,f,g could be 0,1,...,8,9. However, since you are back in the 70's the first three digits: 'a,b,c' are restricted to the selection of the 8 digits 2,3,...,8,9 WITH REPLACEMENT ALLOWED. So that '222' is a perfectly allowed exchange. There are then 8*8*8 =512 possible choices for these three digits 'a,b,c'.

Each of the four remaining numbers: d,e,f,g can be 0,1,2,...,8,9 or ten possible values for each digit d,e,f,g. So there can be 10*10*10*10= 10^4 possible choices since REPLACEMENT is allowed. So, for example, d,e,f,g could be 3333 is O.K.

Now the 512 possible values of 'a,b,c' can be matched with any of the 10^4 possible choices of d,e,f,g. So together there are 512*10^4 = 5.12*10^6 possible phone numbers.

Assuming that each possibility is equally allowed, each number has an equal probability of:
1/[5.12x10^6] = 1.95x10^-7 which is about 2 chances in 10-million, or 200 parts per billion.

In the "real world" the number is smaller because there are other constraints that further DIS-ALLOW certain combinations of either 'a,b,c' or 'd,e,f,g'. For example all: 911-d,e,f,g numbers are probably reserved, and all d,e,f,g = 0000 are also reserved. The more recent addition of "area codes" adds another 512*(5.12x10^6) or ~2.62x10^9 possible numbers if the same constraints apply to area codes as apply to exchange numbers.

ZIP codes are also an example. For a 5-digit ZIP code with no restrictions and REPLACEMENT IS ALLOWED there are 10^5 possible locations, and with the addition of the additional 4-digit extensions gives 10^9 possibilities. It is evident why license plates in many states are combinations of letters and numbers because the alphabet is a base - 26 alpha-numeric. Of course, here too some letter combinations are reserved or dis-allowed for various obvious reasons that some combinations might be socially unacceptable.

Vince Calder


FOLLOW UP QUESTION:

I'm still puzzled about the second part of the question though: what are the odds against a random seven-digit phone number containing the same digits in the same quantities as another one? Obviously if my number is 777-7777 no one else will have a permutation of that number. Whereas if my number is 765-4321, there are 7!-1 other permutations available. So the repeating digits is what makes the problem hard. My thought was to try to figure out the number of repeating digits in the average phone number, and take it from there. Any ideas? --WF


The "simple" task of counting is often not quite so simple. The reason? Often it is not clear "what" is being counted, and there are not any straightforward, plug-in algorithms for determining "how" to count "what" is being counted. The approach used in resources on "counting" seems to be to begin with various "examples" of counting problems -- population sizes, permutations, combinations, probabilities -- and then, in one way or another, say to the student/reader, "Now you see how this goes, try these examples/problems." Consequently, each new counting task becomes a new problem. One filter that can be employed to help with this ad hoc approach is to ask the questions, "What is the sample space being counted?" and "Is what is being counted involve the entire sample space, or does it involve some identifiable sub-set of the sample space?" If the "counting" involves the whole sample space, then the "counting" process involves either multiplicative possibilities or additive possibilities. If the "counting" involves some identifiable sub-set of the sample space, then the "counting" process involves permutations and/or combinations that identify elements of the sample space that all have some property in common.

A second filter that can be employed to assist in the ad hoc process is the question, "Does, or does not, the "counting" process remove elements of the sample space from further consideration?" If the "counting" removes elements of the sample space from further consideration, then the counting involves permutations and/or combinations. If the "counting" process does not remove elements of the sample space from further consideration, then the "counting" process involves all of the elements, all of the time. The "probablility" of an event "P" is, by definition, the reciprocal of the number of elements of the entire set, or of an identifiable sub-set, call it "N", that have some common property. That is P=1/N. The present question can be separated into two parts: 1. How many 3-digit telephone exchanges, abc, are there if the integers a, b, and c can EACH have one of the eight values: 2, 3, 4, ..., 9 with no further restrictions. The signal word here is EACH. That signals that the selection of 'a' or 'b' or 'c' does NOT exclude any other elements from further consideration in the counting process. So 'a' can have eight values: 2, 3, ..., 9. And 'b' and 'c' can have the same eight values. So each of the eight values of 'a' can be followed by eight values of 'b', and each of those eight values of 'b' can be followed by eight values of 'c'. The total number of possible 3-digit exchanges is then: 8 x 8 x 8 = 512. The counting process is: 222, 223, 224, ..., 748, ..., 999. The "odds" of having a particular exchange is P = 1/512. The number of four digit phone numbers, "-defg" is exactly the same except that 'd', 'e', 'f', 'g' can EACH INDEPENDENTLY have one of the ten integer values: 0, 1, 2, ..., 9. The total number of possible 4-digit phone numbers "-defg", starting with: -0000, -0001, -0002, ..., -6825, ..., -9999. So there are 10 x 10 x 10 x 10 = 10^4 four digit integers between "0000" and "9999" with no other restrictions on the counting procedure. Combining that with the 512 possible exchanges gives: 5,120,000 possible phone numbers, each with a probability: P = 1/5,120,000. Permutations and/or combinations do not enter into the counting procedure here because there is no "identifier" that excludes some sub-set of the telephone numbers from the counting process. The verbal statement of this non-exclusion in the inquiry is: "...neither phone number is specified in advance." (except that neither '0' nor '1' can appear in any of the 3-digit exchanges). A similar example is, "How many license plates can be made using two letters followed by a 3-digit number: LM-abcd, with no other restrictions?" For 'L' and 'M' there are 26 possible choices each, and for 'a', 'b', 'c', 'd' there are 10 choices each (digits 0, 1, 2, ..., 9). So there are: 26 x 26 x 10 x 10 x 10 = 676,000 possible license plates.

Vince Calder



Click here to return to the Mathematics Archives

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs

NEWTON AND ASK A SCIENTIST
Educational Programs
Building 360
9700 S. Cass Ave.
Argonne, Illinois
60439-4845, USA
Update: June 2012
Weclome To Newton

Argonne National Laboratory