combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

mixed radix Mixed radix numeral systems are non-standard positional numeral systems in which the numerical base varies from position to position. Such numerical representation applies when a quantity is expressed using a sequence of units that are each a m ...

numeral system A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner. The same sequence of symbo ...

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...

factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \ ...

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...

Lehmer code In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for numbering permutations and is an example of an inversion ...

inversion Inversion or inversions may refer to: Arts * , a French gay magazine (1924/1925) * ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas * Inversion (music), a term with various meanings in music theory and musical set theory * ...

lexicographical order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...

Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance o ...

portmanteau A portmanteau word, or portmanteau (, ) is a blend of words

Definition

The factorial number system is a

mixed radix Mixed radix numeral systems are non-standard positional numeral systems in which the numerical base varies from position to position. Such numerical representation applies when a quantity is expressed using a sequence of units that are each a m ...

numeral system A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner. The same sequence of symbo ...

: 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 is to be multiplied by ! (its place value). 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 . The factorial number system is sometimes defined with the 0! place omitted because it is always zero . In this article, a factorial number representation will be flagged by a subscript "!", so for instance 3:4:1:0:1:0_! stands for 3₅4₄1₃0₂1₁0₀, 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 : 463₁₀. (The place value is the factorial of one less than the radix position, which is why the equation begins with 5! for a 6-digit factoradic number.) 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 radix (1, 2, 3, ...), taking the remainder as digits, and continuing with the

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

quotient, until this

quotient In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...

becomes 0. For example, 463₁₀ can be transformed into a factorial representation by these successive divisions: The process terminates when the quotient reaches zero. Reading the remainders backward gives 3:4:1:0:1:0_!. 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

The following sortable table shows the 24 permutations of four elements with different

inversion Inversion or inversions may refer to: Arts * , a French gay magazine (1924/1925) * ''Inversion'' (artwork), a 2005 temporary sculpture in Houston, Texas * Inversion (music), a term with various meanings in music theory and musical set theory * ...

related vectors. The left and right inversion counts

l

and

r

(the latter often called

Lehmer code In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for numbering permutations and is an example of an inversion ...

) are particularly eligible to be interpreted as factorial numbers.

l

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 ( in the tables default order). Symmetric group 4; permutohedron 3D; Lehmer codes

Symmetric group 4; permutohedron 3D; Lehmer codes

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

decimal The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...

: :5×5! + 4×4! + 3x3! + 2×2! + 1×1! + 0×0!. Clearly the next factorial number representation after 5:4:3:2:1:0_! is 1:0:0:0:0:0:0_! which designates 6! = 720₁₀, 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: :

\sum_^n  =  - 1.

This can be easily proved with

mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...

, or simply by noticing that

\forall i, i\cdot i!=(i+1-1)\cdot i!=(i+1)!-i!

: subsequent terms cancel each other, leaving the first and last term (see Telescoping series) However, when using

Arabic numeral Arabic numerals are the ten numerical digits: , , , , , , , , and . They are the most commonly used symbols to write decimal numbers. They are also used for writing numbers in other systems such as octal, and for writing identifiers such as ...

s 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! = 36,288,000₁₀, which may be written A0000000000_!=10:0:0:0:0:0:0:0:0:0:0_!, but not 100000000000_! = 1:0:0:0:0:0:0:0:0:0:0:0_! which denotes 11! = 39,916,800₁₀. Thus using letters A–Z to denote digits 10, 11, 12, ..., 35 as in other base-N make the largest representable number 36 × 36! − 1. 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 2₄0₃1₂0₁, this number also can be written as 2:0:1:0_!). In fact the factorial number system itself is not truly a

numeral system A numeral system (or system of numeration) is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner. The same sequence of symbo ...

in the sense of providing a representation for all natural numbers using only a finite alphabet of symbols, as it requires an additional separation mark.

Permutations

There is a natural mapping between the

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

s (or equivalently the numbers with ''n'' digits in factorial representation) and

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...

s of ''n'' elements in lexicographical order, when the integers are expressed in factoradic form. This mapping has been termed the

Lehmer code In mathematics and in particular in combinatorics, the Lehmer code is a particular way to encode each possible permutation of a sequence of ''n'' numbers. It is an instance of a scheme for numbering permutations and is an example of an inversion ...

(or inversion table). For example, with , such a mapping is In each case, calculating the permutation proceeds by using the leftmost factoradic digit (here, 0, 1, or 2) as the first permutation digit, then removing it from the list of choices (0, 1, and 2). Think of this new list of choices as zero indexed, and use each successive factoradic digit to choose from its remaining elements. 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. Let's say we want the 2982nd permutation of the numbers 0 through 6. The number 2982 is 4:0:4:1:0:0:0_! in factoradic, and that number picks out digits (4,0,6,2,1,3,5) in turn, via indexing a dwindling ordered set of digits and picking out each digit from the set at each turn: 4:0:4:1:0:0:0_! ─► (4,0,6,2,1,3,5) factoradic: 4 : 0 : 4 : 1 : 0 : 0 : 0_! ├─┬─┬─┬─┐ │ ├─┬─┬─┬─┐ ├─┐ │ │ │ sets: (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 group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...

s is the

concatenation In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...

of two factoradic numbers, with two subscript "!"s. concatenated decimal factoradics permutation pair 0₁₀ 0:0:0_!0:0:0_! ((0,1,2),(0,1,2)) 1₁₀ 0:0:0_!0:1:0_! ((0,1,2),(0,2,1)) ... 5₁₀ 0:0:0_!2:1:0_! ((0,1,2),(2,1,0)) 6₁₀ 0:1:0_!0:0:0_! ((0,2,1),(0,1,2)) 7₁₀ 0:1:0_!0:1:0_! ((0,2,1),(0,2,1)) ... 22₁₀ 1:1:0_!2:0:0_! ((1,2,0),(2,0,1)) ... 34₁₀ 2:1:0_!2:0:0_! ((2,1,0),(2,0,1)) 35₁₀ 2:1:0_!2:1:0_! ((2,1,0),(2,1,0))

Fractional values

Unlike single radix systems whose place values are ''base''ⁿ 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 In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \ ...

) 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). Other terms are given as the sequenc
A046021
on the OEIS. 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: *

1/2 = 0.0\ 1_!

*

1/3 = 0.0\ 0\ 2_!

*

2/3 = 0.0\ 1\ 1_!

*

1/4 = 0.0\ 0\ 1\ 2_!

*

3/4 = 0.0\ 1\ 1\ 2_!

*

1/5 = 0.0\ 0\ 1\ 0\ 4_!

*

1/6 = 0.0\ 0\ 1_!

*

5/6 = 0.0\ 1\ 2_!

*

1/7 = 0.0\ 0\ 0\ 3\ 2\ 0\ 6_!

*

1/8 = 0.0\ 0\ 0\ 3_!

*

1/9 = 0.0\ 0\ 0\ 2\ 3\ 2_!

*

1/10 = 0.0\ 0\ 0\ 2\ 2_!

*

1/11 \ \ = 0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_!

*

2/11 \ \ = 0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_!

*

9/11 \ \ = 0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_!

*

10/11 = 0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9 \ 1_!

*

1/12 \ \ = 0.0\ 0\ 0\ 2_!

*

5/12 \ \ = 0.0\ 0\ 2\ 2_!

*

7/12 \ \ = 0.0\ 1\ 0\ 2_!

*

11/12 = 0.0\ 1\ 2\ 2_!

*

1/15 = 0.0\ 0\ 0\ 1\ 3_!

*

1/16 = 0.0\ 0\ 0\ 1\ 2\ 3_!

*

1/18 = 0.0\ 0\ 0\ 1\ 1\ 4_!

*

1/20 = 0.0\ 0\ 0\ 1\ 1_!

*

1/24 = 0.0\ 0\ 0\ 1_!

*

1/30 = 0.0\ 0\ 0\ 0\ 4_!

*

1/36 = 0.0\ 0\ 0\ 0\ 3\ 2_!

*

1/60 = 0.0\ 0\ 0\ 0\ 2_!

*

1/72 = 0.0\ 0\ 0\ 0\ 1\ 4_!

*

1/120 = 0.0\ 0\ 0\ 0\ 1_!

*

1/144 = 0.0\ 0\ 0\ 0\ 0\ 5_!

*

1/240 = 0.0\ 0\ 0\ 0\ 0\ 3_!

*

1/360 = 0.0\ 0\ 0\ 0\ 0\ 2_!

*

1/720 = 0.0\ 0\ 0\ 0\ 0\ 1_!

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

e = 1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1..._!

*

e^ = 0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E..._!

*

\sin(1) = 0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E..._!

*

\cos(1) = 0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0..._!

*

\sinh(1) = 1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0..._!

*

\cosh(1) = 1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1..._!

References

*. *{{cite book , last = Arndt , first = Jörg , title = Matters Computational: Ideas, Algorithms, Source Code , pages = 232–238 , url = http://www.jjj.de/fxt/#fxtbook , date = 2010

External links

A Lehmer code calculator
Note that their permutation digits start from 1, so mentally reduces o all permutation digits by one to get results equivalent to those on this page.
Factorial number system
Combinatorics Factorial and binomial topics Non-standard positional numeral systems

Definition

Examples

Permutations

Fractional values

See also

References

External links