Factoradic

From Wikipedia, the free encyclopedia

You have new messages (last change).
Numeral systems by culture
Hindu-Arabic numerals
Western Arabic
Eastern Arabic
Khmer		 Indian family
Brahmi
Thai
East Asian numerals
Chinese
Japanese		 Korean
 
Alphabetic numerals
Abjad
Armenian
Cyrillic
Ge'ez		 Hebrew
Ionian/Greek
Sanskrit
 
Other systems
Attic
Etruscan
Urnfield
Roman		 Babylonian
Egyptian
Mayan
List of numeral system topics
Positional systems by base
Decimal (10)
2, 4, 8, 16, 32, 64
3, 9, 12, 24, 30, 36, 60, more…
v • d • e

In combinatorial mathematics, the factoradic is a specially constructed number. 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. Dr. James D. McCaffrey has posted an article on MSDN documenting the factoradic index for permutations with supporting code written in C#. The origins of the term 'factoradic' are obscure. In his article he acknowledges Dr. Peter Cameron of Queen Mary, University of London, as having made the original suggestion.

Contents

[edit] Definition

factoradic 
the unique factorial-based mixed radix numeral system
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

The first twenty-four factoradic numbers are

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. But 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, using arabic numerals to write the digits, 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 factoriadic system (as it is done for the base-10 notation above) is not possible for numbers with more than 10 digits. Using letters A-Z to denote digits 10,...,35 as in other base-N systems raises this limit to 35×35!

[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)

where the leftmost factoradic digit 0, 1, or 2 selects itself for the first permutation digit from the ordered list (0,1,2) of digits and removes itself from the list, creating a list one shorter missing the first permutation digit. The second factoradic digit if "0" then selects for the second permutation digit the first (0-indexed) digit from the shorter list and removes it, or if "1" selects the second (1-indexed) digit from the shorter list and removes it. The third factoradic digit must be "0", but by now the list is only one item long, so that last remaining item 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 pick out the digits in the permutation (4,0,6,2,1,3,5).

                                 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

  • Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Pages 65–66.

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../f/a/c/Factoradic.html"