Factoradic

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

Definition 
factoradic 
the unique factorial-based mixed radix numeral system 
radix:       ...     8    7    6   5   4   3   2   1
 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 may be 0, the next 0 or 1, the next 0, 1, or 2, and so on. The first twenty-four factoradic numbers starting from zero are 

decimal  factoradic
   0A            01
   1A          1201
   2A        130201
   3A        131201
   4A        230201
   5A        231201
   6A      14030201
   7A      14031201
   8A      14130201
   9A      14131201
  10A      14230201
  11A      14231201
  12A      24030201
  13A      24031201
  14A      24130201
  15A      24131201
  16A      24230201
  17A      24231201
  18A      34030201
  19A      34031201
  20A      34130201
  21A      34131201
  22A      34230201
  23A      34231201

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

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

Clearly the next factoradic number after 564534231201 is 17060504030201. 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.

It might not be clear at first sight but factorial based numbering system is also unambiguous. No number can be represented by more than one way because the sum of respective factorials multiplied by the 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.

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
    0A        030201         (0,1,2)
    1A        031201         (0,2,1)
    2A        130201         (1,0,2)
    3A        131201         (1,2,0)
    4A        230201         (2,0,1)
    5A        231201         (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 47064514030201 pick out the digits in the permutation (4,0,6,2,1,3,5). 

                                 47064514030201 → (4,0,6,2,1,3,5)
 factoradic:  47         06                       45       14         03         02       01
              |          |                        |        |          |          |        |
     (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
     0A     030201030201           ((0,1,2),(0,1,2))
     1A     030201031201           ((0,1,2),(0,2,1))
                ...
     5A     030201231201           ((0,1,2),(2,1,0))
     6A     031201030201           ((0,2,1),(0,1,2))
     7A     031201031201           ((0,2,1),(0,2,1))
                ...
    22A     131201230201           ((1,2,0),(2,0,1))
                ...
    34A     231201230201           ((2,1,0),(2,0,1))
    35A     231201231201           ((2,1,0),(2,1,0))

External links

See also

See also: Factoradic, C Sharp, Combinadic, Combinatorics, Computer security, Concatenation, Decimal, Factorial, Group direct product, Index (mathematics)