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 Set of Integers With Nonrepeating Digits
Name: Michael
Status: student	
Age:  N/A
Location: N/A
Country: N/A
Date: 7/9/2005


Question:
I am interested in determining the number of positive integers that do not contain integers that have any repeated digits. Obviously the greatest number in this set would be 9876543210 and then you would start eliminating the numbers like 11; 121; 123452; ...etc How would you calculate this set of non-repeating digits? (and does it contain any interesting properties?) I would appreciate any references to this question as I am fairly sure others have considered it before.



Replies:
What you are asking are the number of possible "permutations" there are of the digits 9,8,...,1,0. These could just as well be labeled A,B,...,J. In a "permutation" order counts, and in the jargon of "permutations" and "combinations" you are asking for the number of "permutations" without replacement. That eliminates the possibility of repeating a digit such as your examples of: 11, 121, 123452, etc. If you choose all 10 digits there are 10 ways to choose the first, 9 ways to choose the second, 8 ways to choose the third,... 1 way to choose the last. That is: 10*9*8*7*...*1 or 10! (that is 10 factorial). The general formula for selecting "n" objects in groups of size "r" is P(n,r) = n! / (n - r)! So you must sum the sequence of possibilities P(10,10) + P(10,9) + ... + P(10,1) = 9,864,100 (recall that 0! = 1! = 1). This counting procedure includes numbers starting with the digit "0". For example "05" or "035768", etc.

With regard to references, a "Google" search on the term(s) "permutations" and/or "combinations" will flood you with sites. You could start with: http://mathforum.org/dr.math/faq/faq.comb.perm.html or http://swid.unl.edu/csce235/main.html

Vince Calder


Michael,

Consider things one digit at a time. First, do numbers that use all ten digits. This will include numbers such as 0123456789. Start with the zero: it can be placed in any of ten places: ten options. Now, consider the one. It can be placed in any of nine remaining places. One place has already been filled by the 0. You now have 10*9=90 options. Then, place the 2 in one of the eight open spaces. This yields 10*9*8 options. This then continues on.

Now, look at using nine digits. First, use 0,1,2,3,4,5,6,7,8. The 9 has been left out. There are nine places to place the 0. There are then eight open spaces for the one. This continues until you have used all nine digits. How many times can you do this? You can drop the 8 instead of the 9. You can drop the 7. You can drop the 6. There are ten sets of 9 digit numbers.

Now, try 8 digits: drop 2 digits at a time. Start with 01234567: The 9 and 8 are dropped. Find the first set: the number of ways to arrange 8 digits. The number of these sets is found as for 9 digits. There are 10 different digits you can use as the first number eliminated. This leaves 9 digits to be the second digit eliminated. One problem then occurs: you have eliminated 9,8 and 8,9. Both give the same result, the same set of eight-digit numbers. As a result, you must divide your answer by two.

Now, work with 7 digits. You drop 3 digits. Find the number of options in the first set of seven digits. Then, find how many sets of seven digits you have. You might think there are 10*9*8 sets of seven digits. Like the eight-digit sets, you will have duplicates. For more information, look up the mathematical terms called Combinations and Permutations for more information.

Kenneth E. Mellendorf
Physics Instructor
Illinois Central College



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