Factorial number system

In combinatorics, the faculty- based number system is used to create a unique index on permutations.

Definition

The faculty- based number system is the number system that has the first faculties as the basic numbers.

In this number system, the location is quite right is always 0, the second position from the right to 0 or 1, the third is 0, 1 or 2, etc. There is also a variant of the faculty- based number system, in which the right-hand number is omitted, as they are always 0 is.

Example

The number 35 would be written in this number system as follows.

Properties

The sum of successive faculties, multiplied by its index, is always the next Faculty minus one:

Therefore, any number can be represented in this number system and this representation is unique, ie any number can be represented in more than one way.

However, this presupposes an infinite number of characters. The simple combination of decimal digits would be ambiguous for numbers with a " number" that is greater than 9. The smallest example of this is the number 10 × 10!, Advertised 101009080706050403020100 being 11! 11101009080706050403020100 is. Therefore, a single subscript is not enough (as in the decimal system ) for numbers with more than 10 digits.

Application

The faculty- based number system is used (or the equivalent numbers with n digits in the faculty- based number system ) and permutations of n elements in lexicographical order to make a canonical mapping between the integers, where the integers with respect to this number system are presented. This mapping is called a Lehmer code or Lucas -Lehmer code. For example arises with n = 3, the following assignment:

It selects the left-most digit is 0, 1 or 2 themselves as Permutationsziffer from the sorted list ( 0,1,2), and removes itself from the list. The result is a shorter list, wherein the first Permutationsziffer missing. With the second digit, the second Permutationsziffer is selected. Here, the counting starts with 0, the element is removed from the list. The third digit is "0". Since the list contains only one element, it is selected as the final Permutationsziffer.

This process is evident with a longer example. The following are created using the digits from the faculty- based number system 46054413020100 the digits from the permutation ( 4,0,6,2,1,3,5 ).

46054413020100 → ( 4,0,6,2,1,3,5 ) School -based: 46 05 44 13 02 01 00                    | | | | | | |           ( 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) The natural index for the direct sum of two permutations is simply the concatenation.