Factoradic

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 origins of the term 'factoradic' are obscure.

Definition

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

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

Examples

The first twenty-four factoradic numbers are

For another example, the biggest number that could be represented with six digits would be 5₅4₄3₃2₂1₁0₀ which equals 719 in decimal:

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

Clearly the next factoradic number after 5₅4₄3₃2₂1₁0₀ is 1₆0₅0₄0₃0₂0₁0₀. 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:

Failed to parse (Missing texvc executable; please see math/README to configure.): \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 10₁₀0₉0₈0₇0₆0₅0₄0₃0₂0₁0₀ while 11! is 1₁₁0₁₀0₉0₈0₇0₆0₅0₄0₃0₂0₁0₀. 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 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.

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

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 4₆0₅4₄1₃0₂0₁0₀ (equal to 2982₁₀) pick out the digits in the 2982nd permutation of (0,1,2,3,4,5,6) — (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))

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.
• James McCaffrey, Using Permutations in .NET for Improved Systems Security, MSDN.

See also

• Combinadic
• Factorial

External links

• Laisant, C.- A., Sur la numération factorielle, application aux permutations. Bulletin de la Société Mathématique de France, 16 (1888), p. 176-183 (in French)
• "A permutation representation that knows what 'Eulerian' means", by Roberto Mantaci and Fanja Rakotondrajao. (PDF) Description and references for Lehmer codes
• 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.de:Fakultätsbasiertes Zahlensystem

id:Faktoradik nl:Faculteitssysteem