Factorial number system

From Wikipedia, the free encyclopedia
  (Redirected from Factoradic)
Jump to: navigation, search

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

Definition[edit]

The factorial number system is a mixed radix numeral system: the i-th digit from the right has base i, which means that the digit must be strictly less than i, and that (taking into account the bases of the less significant digits) its value to be multiplied by (i − 1)! (its place value).

Radix 8 7 6 5 4 3 2 1
Place value 7! 6! 5! 4! 3! 2! 1! 0!
Place value in decimal 5040 720 120 24 6 2 1 1
Highest digit allowed 7 6 5 4 3 2 1 0

From this it follows that the rightmost digit is always 0, the second can be 0 or 1, the third 0, 1 or 2, and so on (sequence A124252 in the OEIS). The factorial number system is sometimes defined with the 0! place omitted because it is always zero (sequence A007623 in the OEIS).

In this article, a factorial number representation will be flagged by a subscript "!", so for instance 341010! stands for 354413021100, whose value is

  • = 3×5! + 4×4! + 1×3! + 0×2! + 1×1! + 0×0! 
  • = ((((3×5 + 4)×4 + 1)×3 + 0)×2 + 1)×1 + 0
  • =  46310.

(Note that the place value is one less than the radix position, which is why these equations begin with 5!.)

General properties of mixed radix number systems also apply to the factorial number system. For instance, one can convert a number into factorial representation producing digits from right to left, by repeatedly dividing the number by the place values (1, 2, 3, ...), taking the remainder as digits, and continuing with the integer quotient, until this quotient becomes 0.

For example, 46310 can be transformed into a factorial representation by these successive divisions:

  • 463 ÷ 1 = 463, remainder 0
  • 463 ÷ 2 = 231, remainder 1
  • 231 ÷ 3 = 77, remainder 0
  • 77 ÷ 4 = 19, remainder 1
  • 19 ÷ 5 = 3, remainder 4
  • 3 ÷ 6 = 0, remainder 3

The process terminates when the quotient reaches zero. Reading the remainders backward gives 341010!.

In principle, this system may be extended to represent fractional numbers, though rather than the natural extension of place values (−1)!, (−2)!, etc., which are undefined, the symmetric choice of radix values n = 0, 1, 2, 3, 4, etc. after the point may be used instead. Again, the 0 and 1 places may be omitted as these are always zero. The corresponding place values are therefore 1/1, 1/1, 1/2, 1/6, 1/24, ..., 1/n!, etc.

Examples[edit]

The following sortable table shows the 24 permutations of four elements with different inversion related vectors. The left and right inversion counts and (the latter often called Lehmer code) are particularly eligible to be interpreted as factorial numbers. gives the permutation's position in reverse colexicographic order (the default order of this table), and the latter the position in lexicographic order (both counted from 0).

Sorting by a column that has the omissible 0 on the right makes the factorial numbers in that column correspond to the index numbers in the immovable column on the left. The small columns are reflections of the columns next to them, and can be used to bring those in colexicographic order. The rightmost column shows the digit sums of the factorial numbers (OEISA034968 in the tables default order).

The factorial numbers of a given length form a permutohedron when ordered by the bitwise relation

These are the right inversion counts (aka Lehmer codes) of the permutations of four elements.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p-b #
0 4-el perm matrix 00.svg 1234 4321 0000 0000 0000 0000 4-el perm invset 00.svg 0000 0000 0
1 4-el perm matrix 01.svg 2134 4312 1000 0001 0010 0100 4-el perm invset 01.svg 1000 0001 1
2 4-el perm matrix 02.svg 1324 4231 0100 0010 0100 0010 4-el perm invset 02.svg 0100 0010 1
3 4-el perm matrix 03.svg 3124 4213 1100 0011 0110 0110 4-el perm invset 03.svg 2000 0002 2
4 4-el perm matrix 04.svg 2314 4132 2000 0002 0200 0020 4-el perm invset 04.svg 1100 0011 2
5 4-el perm matrix 05.svg 3214 4123 2100 0012 0210 0120 4-el perm invset 05.svg 2100 0012 3
6 4-el perm matrix 06.svg 1243 3421 0010 0100 1000 0001 4-el perm invset 06.svg 0010 0100 1
7 4-el perm matrix 07.svg 2143 3412 1010 0101 1010 0101 4-el perm invset 07.svg 1010 0101 2
8 4-el perm matrix 08.svg 1423 3241 0110 0110 1100 0011 4-el perm invset 08.svg 0200 0020 2
9 4-el perm matrix 09.svg 4123 3214 1110 0111 1110 0111 4-el perm invset 09.svg 3000 0003 3
10 4-el perm matrix 10.svg 2413 3142 2010 0102 1200 0021 4-el perm invset 10.svg 1200 0021 3
11 4-el perm matrix 11.svg 4213 3124 2110 0112 1210 0121 4-el perm invset 11.svg 3100 0013 4
12 4-el perm matrix 12.svg 1342 2431 0200 0020 2000 0002 4-el perm invset 12.svg 0110 0110 2
13 4-el perm matrix 13.svg 3142 2413 1200 0021 2010 0102 4-el perm invset 13.svg 2010 0102 3
14 4-el perm matrix 14.svg 1432 2341 0210 0120 2100 0012 4-el perm invset 14.svg 0210 0120 3
15 4-el perm matrix 15.svg 4132 2314 1210 0121 2110 0112 4-el perm invset 15.svg 3010 0103 4
16 4-el perm matrix 16.svg 3412 2143 2200 0022 2200 0022 4-el perm invset 16.svg 2200 0022 4
17 4-el perm matrix 17.svg 4312 2134 2210 0122 2210 0122 4-el perm invset 17.svg 3200 0023 5
18 4-el perm matrix 18.svg 2341 1432 3000 0003 3000 0003 4-el perm invset 18.svg 1110 0111 3
19 4-el perm matrix 19.svg 3241 1423 3100 0013 3010 0103 4-el perm invset 19.svg 2110 0112 4
20 4-el perm matrix 20.svg 2431 1342 3010 0103 3100 0013 4-el perm invset 20.svg 1210 0121 4
21 4-el perm matrix 21.svg 4231 1324 3110 0113 3110 0113 4-el perm invset 21.svg 3110 0113 5
22 4-el perm matrix 22.svg 3421 1243 3200 0023 3200 0023 4-el perm invset 22.svg 2210 0122 5
23 4-el perm matrix 23.svg 4321 1234 3210 0123 3210 0123 4-el perm invset 23.svg 3210 0123 6

For another example, the greatest number that could be represented with six digits would be 543210! which equals 719 in decimal:

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

Clearly the next factorial number representation after 543210! is 1000000! which designates 6! = 72010, the place value for the radix-7 digit. So the former number, and its summed out expression above, is equal to:

6! − 1.

The factorial number system provides a unique representation for each natural number, with the given restriction on the "digits" used. 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, or simply by noticing that  : subsequent terms cancel each other, leaving the first and last term (see Telescoping series)

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" greater than 9. The smallest such example is the number 10 × 10! = 3628800010, which may be written A0000000000!, but not 100000000000! which denotes 11! = 3991680010. Thus using letters A–Z to denote digits 10, 11, 12, ..., 35 as in other base-N make the largest representable number 36! − 1 = 37199332678990121746799944815083519999999910. For arbitrarily greater numbers one has to choose a base for representing individual digits, say decimal, and provide a separating mark between them (for instance by subscripting each digit by its base, also given in decimal, like 24031201, this number also can be written as 2:0:1:0). In fact the factorial number system itself is not truly a numeral system in the sense of providing a representation for all natural numbers using only a finite alphabet of symbols.

Permutations[edit]

There is a natural mapping between the integers 0, ..., n! − 1 (or equivalently the numbers with n digits in factorial representation) 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 inversion table). For example, with n = 3, such a mapping is

decimal factorial permutation
010 000! (0,1,2)
110 010! (0,2,1)
210 100! (1,0,2)
310 110! (1,2,0)
410 200! (2,0,1)
510 210! (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 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 4041000! (equal to 298210) pick out the digits in (4,0,6,2,1,3,5), the 2982nd permutation of the numbers 0 through 6.

                                 4041000! → (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)

A natural index for the group direct product of two permutation groups is the concatenation of two factoradic numbers, with two subscript "!"s.

           concatenated
 decimal   factoradics            permutation pair
    010     000!000!           ((0,1,2),(0,1,2))
    110     000!010!           ((0,1,2),(0,2,1))
               ...
    510     000!210!           ((0,1,2),(2,1,0))
    610     010!000!           ((0,2,1),(0,1,2))
    710     010!010!           ((0,2,1),(0,2,1))
               ...
   2210     110!200!           ((1,2,0),(2,0,1))
               ...
   3410     210!200!           ((2,1,0),(2,0,1))
   3510     210!210!           ((2,1,0),(2,1,0))

Fractional values[edit]

Unlike single radix systems whose place values are basen for both positive and negative integral n, the factorial number base cannot be extended to negative place values as these would be (−1)!, (−2)! and so on, and these values are undefined. (see factorial)

One possible extension is therefore to use 1/0!, 1/1!, 1/2!, 1/3!, ..., 1/n! etc. instead, possibly omitting the 1/0! and 1/1! places which are always zero.

With this method, all rational numbers have a terminating expansion, whose length in 'digits' is less than or equal to the denominator of the rational number represented. This may be proven by considering that there exists a factorial for any integer and therefore the denominator divides into its own factorial even if it does not divide into any smaller factorial.

By necessity, therefore, the factoradic expansion of the reciprocal of a prime has a length of exactly that prime (less one if the 1/1! place is omitted). It can also be proven that the last 'digit' or term of the representation of a rational with prime denominator is equal to the difference between the numerator and the prime denominator.

There is also a non-terminating equivalent for every rational number akin to the fact that in decimal 0.24999... = 0.25 = 1/4 and 0.999... = 1, etc., which can be created by reducing the final term by 1 and then filling in the remaining infinite number of terms with the highest value possible for the radix of that position.

In the following selection of examples, spaces are used to separate the place values, otherwise represented in decimal. The rational numbers on the left are also in decimal:

There are also a small number of constants that have patterned representations with this method:

See also[edit]

References[edit]

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

External links[edit]