Added to Favorites

Popular Searches

Definitions

Nearby Words

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.

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 .

decimal | factoradic |

1_{10}
| 1_{1}0_{0} |

2_{10}
| 1_{2}0_{1}0_{0} |

3_{10}
| 1_{2}1_{1}0_{0} |

4_{10}
| 2_{2}0_{1}0_{0} |

5_{10}
| 2_{2}1_{1}0_{0} |

6_{10}
| 1_{3}0_{2}0_{1}0_{0} |

7_{10}
| 1_{3}0_{2}1_{1}0_{0} |

8_{10}
| 1_{3}1_{2}0_{1}0_{0} |

9_{10}
| 1_{3}1_{2}1_{1}0_{0} |

10_{10}
| 1_{3}2_{2}0_{1}0_{0} |

11_{10}
| 1_{3}2_{2}1_{1}0_{0} |

12_{10}
| 2_{3}0_{2}0_{1}0_{0} |

13_{10}
| 2_{3}0_{2}1_{1}0_{0} |

14_{10}
| 2_{3}1_{2}0_{1}0_{0} |

15_{10}
| 2_{3}1_{2}1_{1}0_{0} |

16_{10}
| 2_{3}2_{2}0_{1}0_{0} |

17_{10}
| 2_{3}2_{2}1_{1}0_{0} |

18_{10}
| 3_{3}0_{2}0_{1}0_{0} |

19_{10}
| 3_{3}0_{2}1_{1}0_{0} |

20_{10}
| 3_{3}1_{2}0_{1}0_{0} |

21_{10}
| 3_{3}1_{2}1_{1}0_{0} |

22_{10}
| 3_{3}2_{2}0_{1}0_{0} |

23_{10}
| 3_{3}2_{2}1_{1}0_{0} |

For another example, the biggest number that could be represented with six digits would be
5_{5}4_{4}3_{3}2_{2}1_{1}0_{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_{5}4_{4}3_{3}2_{2}1_{1}0_{0} is 1_{6}0_{5}0_{4}0_{3}0_{2}0_{1}0_{0}. 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\}\; \{icdot\; i!\}\; =\; \{(n+1)!\}\; -\; 1.$

This can be easily proved with mathematical induction.

However, when using arabic numerals to write the digits (and not including the subscripts as in the above examples), their simple concatenation becomes ambiguous for numbers having a "digit" bigger than 9. The smallest such example is the number 10×10!, written 10_{10}0_{9}0_{8}0_{7}0_{6}0_{5}0_{4}0_{3}0_{2}0_{1}0_{0}
while 11! is 1_{11}0_{10}0_{9}0_{8}0_{7}0_{6}0_{5}0_{4}0_{3}0_{2}0_{1}0_{0}.
Thus adding a single subscript to denote notation in the factoriadic system (as 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.

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_{10}
| 0_{2}0_{1}0_{0}
| (0,1,2) |

1_{10}
| 0_{2}1_{1}0_{0}
| (0,2,1) |

2_{10}
| 1_{2}0_{1}0_{0}
| (1,0,2) |

3_{10}
| 1_{2}1_{1}0_{0}
| (1,2,0) |

4_{10}
| 2_{2}0_{1}0_{0}
| (2,0,1) |

5_{10}
| 2_{2}1_{1}0_{0}
| (2,1,0) |

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_{6}0_{5}4_{4}1_{3}0_{2}0_{1}0_{0} (equal to 2982_{10}) pick out the digits in the 2982nd permutation of (0,1,2,3,4,5,6) — (4,0,6,2,1,3,5).

4_{6}0_{5}4_{4}1_{3}0_{2}0_{1}0_{0}→ (4,0,6,2,1,3,5)

factoradic: 4_{6}0_{5}4_{4}1_{3}0_{2}0_{1}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_{10}0_{2}0_{1}0_{0}0_{2}0_{1}0_{0}((0,1,2),(0,1,2))

1_{10}0_{2}0_{1}0_{0}0_{2}1_{1}0_{0}((0,1,2),(0,2,1))

...

5_{10}0_{2}0_{1}0_{0}2_{2}1_{1}0_{0}((0,1,2),(2,1,0))

6_{10}0_{2}1_{1}0_{0}0_{2}0_{1}0_{0}((0,2,1),(0,1,2))

7_{10}0_{2}1_{1}0_{0}0_{2}1_{1}0_{0}((0,2,1),(0,2,1))

...

22_{10}1_{2}1_{1}0_{0}2_{2}0_{1}0_{0}((1,2,0),(2,0,1))

...

34_{10}2_{2}1_{1}0_{0}2_{2}0_{1}0_{0}((2,1,0),(2,0,1))

35_{10}2_{2}1_{1}0_{0}2_{2}1_{1}0_{0}((2,1,0),(2,1,0))

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

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday October 08, 2008 at 05:06:08 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday October 08, 2008 at 05:06:08 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.