Factoradic
Encyclopedia
In combinatorics
, the factorial number system, also called factoradic, is a mixed radix
numeral system
adapted to numbering permutation
s. It is also called factorial base, although factorial
s 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 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
.
The term "factorial number system" is used by Knuth,
while the French equivalent "numération factorielle" was first used in 1888. The term "factoradic", which is a portmanteau of factorial and mixed radix, appears to be of more recent date.
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 ! (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 rightmost digit omitted, because it is always zero . In this article a factorial number representation will be flagged by a subscript "!", so for instance 341010! stands for 364514031201, whose value is ((((3×5 + 4)×4 + 1)×3 + 0)×2 + 1)×1 + 0 = 46310.
General properties of mixed radix number systems apply to the factorial number system as well. 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. One could in principle extend the system to deal with fractional numbers by choosing base values for the positions after the "decimal" point, but the natural extension by values 0, −1, −2, ... is not an option. The symmetric choice of base values 1, 2, 3, ... after the point would be possible, with corresponding place values , but it is not distinguished by any particular mathematical properties (except that the number e
takes the form 10.011111...).
The table on the left shows permutations, and inversion vectors (which are reflected factorial numbers) below them. Another column shows the inversion sets. The digit sums of the inversion vectors (or factorial numbers) and the cardinalities of the inversion sets are equal (and have the same parity as the permutation). They form the sequence .
For another example, the greatest number that could be represented with six digits would be 543210! which equals 719 in decimal
:
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:
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
.
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, ..., 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). 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.
between the integer
s 0, ..., n! − 1 (or equivalently the numbers with n digits in factorial representation) and permutation
s 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
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 group
s 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))
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, the factorial number system, also called factoradic, is a mixed radix
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 multiple of the next smaller one, but not by the same...
numeral system
Numeral system
A numeral system is a writing system for expressing numbers, that is a mathematical notation for representing numbers of a given set, using graphemes or symbols in a consistent manner....
adapted to numbering permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s. It is also called factorial base, although factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
s 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
Lehmer code
In mathematics and in particular in combinatorics, the terms inversion table and Lehmer code refer to ways to encode any permutation of n by a sequence of n numbers in manner that makes evident the fact that there aresuch permutations...
or as inversion table 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
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
.
The term "factorial number system" is used by Knuth,
while the French equivalent "numération factorielle" was first used in 1888. The term "factoradic", which is a portmanteau of factorial and mixed radix, appears to be of more recent date.
Definition
The factorial number system is a mixed radixMixed 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 multiple of the next smaller one, but not by the same...
numeral system
Numeral system
A numeral system is a writing system for expressing numbers, that is a mathematical notation for representing numbers of a given set, using graphemes or symbols in a consistent manner....
: 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 ! (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. The factorial number system is sometimes defined with the rightmost digit omitted, because it is always zero . In this article a factorial number representation will be flagged by a subscript "!", so for instance 341010! stands for 364514031201, whose value is ((((3×5 + 4)×4 + 1)×3 + 0)×2 + 1)×1 + 0 = 46310.
General properties of mixed radix number systems apply to the factorial number system as well. 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
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
quotient, until this quotient
Quotient
In mathematics, a quotient is the result of division. For example, when dividing 6 by 3, the quotient is 2, while 6 is called the dividend, and 3 the divisor. The quotient further is expressed as the number of times the divisor divides into the dividend e.g. The quotient of 6 and 2 is also 3.A...
becomes 0. One could in principle extend the system to deal with fractional numbers by choosing base values for the positions after the "decimal" point, but the natural extension by values 0, −1, −2, ... is not an option. The symmetric choice of base values 1, 2, 3, ... after the point would be possible, with corresponding place values , but it is not distinguished by any particular mathematical properties (except that the number e
E (mathematical constant)
The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...
takes the form 10.011111...).
Examples
Here are the first twenty-four numbers, counting from zero.The table on the left shows permutations, and inversion vectors (which are reflected factorial numbers) below them. Another column shows the inversion sets. The digit sums of the inversion vectors (or factorial numbers) and the cardinalities of the inversion sets are equal (and have the same parity as the permutation). They form the sequence .
EWLINE
|
For another example, the greatest number that could be represented with six digits would be 543210! which equals 719 in decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
:
- 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
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
.
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, ..., 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). In fact the factorial number system itself is not truly a numeral system
Numeral system
A numeral system is a writing system for expressing numbers, that is a mathematical notation for representing numbers of a given set, using graphemes or symbols in a consistent manner....
in the sense of providing a representation for all natural numbers using only a finite alphabet of symbols.
Permutations
There is a natural mappingFunction (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
between the integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s 0, ..., n! − 1 (or equivalently the numbers with n digits in factorial representation) and permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s of n elements in lexicographical order, when the integers are expressed in factoradic form. This mapping has been termed the Lehmer code
Lehmer code
In mathematics and in particular in combinatorics, the terms inversion table and Lehmer code refer to ways to encode any permutation of n by a sequence of n numbers in manner that makes evident the fact that there aresuch permutations...
(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 group
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 ; the relationship is often written as...
s is the concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
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))
See also
- Combinatorial number system (also called combinadics)
- FactorialFactorialIn mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
- Steinhaus–Johnson–Trotter algorithm, an algorithm that generates Gray codeGray codeThe reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code....
s for the factorial number system
External links
- 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 those on this page