Factoradic

From Wikipedia, the free encyclopedia

Jump to: navigation, search
Numeral systems by culture
Hindu-Arabic numerals
Western Arabic
Eastern Arabic
Indian family		 Khmer
Mongolian
Thai
East Asian numerals
Chinese
Counting rods
Japanese		 Korean
Suzhou
Alphabetic numerals
Abjad
Armenian
Āryabhaṭa
Cyrillic		 Ge'ez
Greek (Ionian)
Hebrew
Other systems
Attic
Babylonian
Brahmi
Egyptian
Etruscan		 Inuit
Mayan
Roman
Urnfield
List of numeral system topics
Positional systems by base
Decimal (10)
2, 4, 8, 16, 32, 64
1, 3, 6, 9, 12, 20, 24, 30, 36, 60, more…
v • d • e

In combinatorics, factoradic is a specially constructed number system. Factoradics provide a lexicographical index for permutations, so they have potential application to computer security. The idea of the factoradic is closely linked to that of the Lehmer code. An article by James D. McCaffrey documents the factoradic index for permutations with supporting code written in C#, acknowledging Peter Cameron as having made the original suggestion. The term 'factoradic' is a portmanteau of factorial and mixed radix.

Contents

[edit] Definition

Factoradic is a factorial-based mixed radix numeral system: the i-th digit, counting from right, is to be multiplied by i!

radix: 7 6 5 4 3 2 1 0
place value: 7! 6! 5! 4! 3! 2! 1! 0!
in decimal: 5040 720 120 24 6 2 1 1

In this numbering system, the rightmost digit is always 0, the second 0, or 1, the third 0, 1 or 2 and so on. There also exists a variant of the Factoradic system where the rightmost number is omitted because it is always zero (sequence A007623 in OEIS).

[edit] Examples

Here are the first twenty-three factoradic numbers:

decimal factoradic
110 1100
210 120100
310 121100
410 220100
510 221100
610 13020100
710 13021100
810 13120100
910 13121100
1010 13220100
1110 13221100
1210 23020100
1310 23021100
1410 23120100
1510 23121100
1610 23220100
1710 23221100
1810 33020100
1910 33021100
2010 33120100
2110 33121100
2210 33220100
2310 33221100

For another example, the biggest number that could be represented with six digits would be 554433221100 which equals 719 in decimal:

5×5! + 4×4! + 3×3! + 2×2! + 1×1! + 0×0!.

Clearly the next factoradic number after 554433221100 is 16050403020100. This is equal to 6!, the place value for the radix 7 digit. So the previous number, and its summed out expression above, is equal to:

6! − 1.

The factoradic numbering system is unambiguous. No number can be represented in more than one way because the sum of consecutive factorials multiplied by their index is always the next factorial minus one:

\sum_{i=0}^{n} {i\cdot i!} = {(n+1)!} - 1.

This can be easily proved with mathematical induction.

However, when using arabic numerals to write the digits (and not including the subscripts as in the above examples), their simple concatenation becomes ambiguous for numbers having a "digit" bigger than 9. The smallest such example is the number 10×10!, written 101009080706050403020100 while 11! is 11101009080706050403020100. Thus adding a single subscript to denote notation in the factoradic system (as done for the base-10 notation above) is not possible for numbers with more than 10 digits without relying heavily on the visual cue that it is a subscript (indeed, one notices right away that for 10×10!, there is no subscript between the leftmost non-subscript "1" character and the non-subscript "0" character immediately to its right whereas there is for 11!). Using letters A-Z to denote digits 10,...,35 as in other base-N systems raises this limit to 36! − 1.

[edit] Permutations

There is a natural mapping between the integers 0, ..., n! − 1 (or equivalently the factoradic numbers with n digits) and permutations of n elements in lexicographical order, when the integers are expressed in factoradic form. This mapping has been termed the Lehmer code or Lucas-Lehmer code (inversion table). For example, with n = 3, such a mapping is

decimal factoradic permutation
010 020100 (0,1,2)
110 021100 (0,2,1)
210 120100 (1,0,2)
310 121100 (1,2,0)
410 220100 (2,0,1)
510 221100 (2,1,0)

The leftmost factoradic digit 0, 1, or 2 is chosen as the first permutation digit from the ordered list (0,1,2) and is removed from the list. Think of this new list as zero indexed and each successive digit dictates which of the remaining elements is to be chosen. If the second factoradic digit is "0" then the first element of the list is selected for the second permutation digit which and is then removed from the list. Similarly if the second factoradic digit is "1", the second is selected and then removed. The final factoradic digit is always "0", and since the list now contains only one element it is selected as the last permutation digit.

The process may become clearer with a longer example. For example, here is how the digits in the factoradic 46054413020100 (equal to 298210) pick out the digits in (4,0,6,2,1,3,5), the 2982nd permutation of the numbers 0 through 6.

                                 46054413020100 → (4,0,6,2,1,3,5)
factoradic:  46         05                       44       13         02         01       00
             |          |                        |        |          |          |        |
    (0,1,2,3,4,5,6) -> (0,1,2,3,5,6) -> (1,2,3,5,6) -> (1,2,3,5) -> (1,3,5) -> (3,5) -> (5)
             |          |                        |        |          |          |        |
permutation:(4,         0,                       6,       2,         1,         3,       5)

Of course the natural index for the group direct product of two permutation groups is just the factoradics for the two groups joined using concatenation.

           concatenated
 decimal   factoradics            permutation pair
    010     020100020100           ((0,1,2),(0,1,2))
    110     020100021100           ((0,1,2),(0,2,1))
               ...
    510     020100221100           ((0,1,2),(2,1,0))
    610     021100020100           ((0,2,1),(0,1,2))
    710     021100021100           ((0,2,1),(0,2,1))
               ...
   2210     121100220100           ((1,2,0),(2,0,1))
               ...
   3410     221100220100           ((2,1,0),(2,0,1))
   3510     221100221100           ((2,1,0),(2,1,0))

[edit] References

  • Knuth, Donald (1997), "Volume 2: Seminumerical Algorithms", The Art of Computer Programming (3rd ed.), Addison-Wesley, pp. 65–66, ISBN 0-201-89684-2 .

[edit] See also

[edit] External links

  • A Lehmer code calculator Note that their permutation digits start from 1, so mentally reduce all permutation digits by one to get results equivalent to the ones on this page.
Retrieved from "http://en.wikipedia.org/wiki/Factoradic"
Personal tools