Factoradic

From Wikipedia, the free encyclopedia

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 Roman	Babylonian Egyptian Mayan
List of numeral system topics
Positional systems by base
Decimal (10)
2, 4, 8, 16, 32, 64, 128
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.

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 Factoradiac system where the rightmost number is omitted because it is always zero.

The first twenty-four factoradic numbers are

decimal	factoradic
1₁₀	1₁0₀
2₁₀	1₂0₁0₀
3₁₀	1₂1₁0₀
4₁₀	2₂0₁0₀
5₁₀	2₂1₁0₀
6₁₀	1₃0₂0₁0₀
7₁₀	1₃0₂1₁0₀
8₁₀	1₃1₂0₁0₀
9₁₀	1₃1₂1₁0₀
10₁₀	1₃2₂0₁0₀
11₁₀	1₃2₂1₁0₀
12₁₀	2₃0₂0₁0₀
13₁₀	2₃0₂1₁0₀
14₁₀	2₃1₂0₁0₀
15₁₀	2₃1₂1₁0₀
16₁₀	2₃2₂0₁0₀
17₁₀	2₃2₂1₁0₀
18₁₀	3₃0₂0₁0₀
19₁₀	3₃0₂1₁0₀
20₁₀	3₃1₂0₁0₀
21₁₀	3₃1₂1₁0₀
22₁₀	3₃2₂0₁0₀
23₁₀	3₃2₂1₁0₀

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:

$\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
0₁₀	0₂0₁0₀	(0,1,2)
1₁₀	0₂1₁0₀	(0,2,1)
2₁₀	1₂0₁0₀	(1,0,2)
3₁₀	1₂1₁0₀	(1,2,0)
4₁₀	2₂0₁0₀	(2,0,1)
5₁₀	2₂1₁0₀	(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 4₆0₅4₄1₃0₂0₁0₀ pick out the digits in the permutation (4,0,6,2,1,3,5).

                                 4₆0₅4₄1₃0₂0₁0₀ → (4,0,6,2,1,3,5)
factoradic:  4₆         0₅                       4₄       1₃         0₂         0₁       0₀
             |          |                        |        |          |          |        |
    (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
    0₁₀     0₂0₁0₀0₂0₁0₀           ((0,1,2),(0,1,2))
    1₁₀     0₂0₁0₀0₂1₁0₀           ((0,1,2),(0,2,1))
               ...
    5₁₀     0₂0₁0₀2₂1₁0₀           ((0,1,2),(2,1,0))
    6₁₀     0₂1₁0₀0₂0₁0₀           ((0,2,1),(0,1,2))
    7₁₀     0₂1₁0₀0₂1₁0₀           ((0,2,1),(0,2,1))
               ...
   22₁₀     1₂1₁0₀2₂0₁0₀           ((1,2,0),(2,0,1))
               ...
   34₁₀     2₂1₁0₀2₂0₁0₀           ((2,1,0),(2,0,1))
   35₁₀     2₂1₁0₀2₂1₁0₀           ((2,1,0),(2,1,0))