Factorial number system

Part of a series on
Numeral systems
Place-value notation
Hindu–Arabic numerals
East Asian systems
Contemporary
Historic
Other systems
Ancient
Post-classical
Contemporary
By radix/base
Common radices/bases
Non-standard radices/bases
Sign-value notation
Non-alphabetic
Alphabetic
List of numeral systems

In combinatorics, the factorial number system, also called factoradic, is a mixed radix numeral system adapted to numbering permutations. It is also called factorial base, although factorials do not function as base, but as place value of digits. By converting a number less than n! to factorial representation, one obtains a sequence of n digits that can be converted to a permutation of n elements in a straightforward way, either using them as Lehmer code or as inversion table[1] representation; in the former case the resulting map from integers to permutations of n elements lists them in lexicographical order. General mixed radix systems were studied by Georg Cantor.[2]

The term "factorial number system" is used by Knuth,[3] while the French equivalent "numération factorielle" was first used in 1888.[4] The term "factoradic", which is a portmanteau of factorial and mixed radix, appears to be of more recent date.[5]

  1. ^ Knuth, D. E. (1973), "Volume 3: Sorting and Searching", The Art of Computer Programming, Addison-Wesley, p. 12, ISBN 0-201-89685-0
  2. ^ Cantor, G. (1869), Zeitschrift für Mathematik und Physik, vol. 14.
  3. ^ Knuth, D. E. (1997), "Volume 2: Seminumerical Algorithms", The Art of Computer Programming (3rd ed.), Addison-Wesley, p. 192, ISBN 0-201-89684-2.
  4. ^ Laisant, Charles-Ange (1888), "Sur la numération factorielle, application aux permutations", Bulletin de la Société Mathématique de France (in French), 16: 176–183.
  5. ^ The term "factoradic" is apparently introduced in McCaffrey, James (2003), Using Permutations in .NET for Improved Systems Security, Microsoft Developer Network.