 |
 |
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
| |
Update: June 2012
|
|
