Information AboutFactoradic |
| CATEGORIES ABOUT FACTORADIC | |
| combinatorics | |
| non-standard positional numeral systems | |
|
In 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. 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: : This can be easily proved with Mathematical Induction . There is a natural Mapping between the Integer s 0, ..., ''n''! − 1 (or equivalently the factoradic numbers with ''n'' digits) and Permutation s 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 |
|
|