SEARCH HOME
Math CentralQuandaries & Queries

search

Question from Joe, a parent:

Found a close problem but not quite.
Using digits 0123456789, how can I figure what all the different possibilities would be without repeating any digits?
I know that there are 10! possible answers but how can I figure out what they are?

Joe,

10! is a very large number, so I'm not going to write out all 3628800 possibilities!

This is one way of ordering numbers without repeating digits however:

For the first digit, choose the smallest number: 0
For the second digit, choose the smallest number that is not already in use: 1
etc.
For the ninth digit, you choose the smallest of what's left (8 and 9), so chose 8.
For the tenth digit, you have just the 9 left, so use that.

Thus the first number to write down is 0123456789.

Now for the next number, you back up:
There were two choices for the ninth digit, so now choose the other one: 9.
This means the tenth digit would be an 8.

Thus the second number is 0123456798.

Now back up again: we've gone through all the possibilities that start with 01234567, so we look at the eigth digit choices. They were 7, 8, and 9 and we chose 7, so now choose the "next" value: 8.

That leaves 7 and 9 for the ninth digit, so choose the smaller: 7.

Leaving 9 for the last digit, and so the next number is 0123456879.

Now back up and choose the next possibility for the ninth digit: 9.

This leaves 7 for the last digit, so the next number is 0123456897.

Again we back up to the eight digit and choose the next smallest number we haven't used from its set. Since we used 7 and 8 already, we use 9 this time.

Following the same steps, the next two numbers are 0123456978 and 0123456987.

In summary, we are "holding" the beginning constant and changing the endings until we've exhausted all the permutations of numbers that start with that beginning. Whenever we change a digit, we start a new sequence for all the digits its right.

Here's a complete but smaller example. What are all the possible arrangements of ABCD that don't repeat letters?
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

and as you observed, this is 4! = 24 permutations.

Hope this helps,
Stephen La Rocque.

About Math Central
 

 


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS