Part of a series on |
Numeral systems |
---|
List of numeral systems |
This article needs additional citations for verification .(March 2021) |
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]
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 is to be multiplied by (i − 1)! (its place value).
Radix/Base | 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 "!". In addition, some examples will have digits delimited by a colon. For example, 3:4:1:0:1:0! stands for
(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 quotient, until this quotient becomes 0.
For example, 46310 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 rational 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.
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 ( OEIS: A034968 in the tables default order).
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 5:4:3:2:1:0! is 1:0:0:0:0:0:0! 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, 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! = 36,288,00010, 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,80010. 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 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.
There is a natural mapping between the integers 0, 1, ..., 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 | factoradic | permutation |
---|---|---|
010 | 0:0:0! | (0,1,2) |
110 | 0:1:0! | (0,2,1) |
210 | 1:0:0! | (1,0,2) |
310 | 1:1:0! | (1,2,0) |
410 | 2:0:0! | (2,0,1) |
510 | 2:1:0! | (2,1,0) |
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 direct product of two permutation groups is the concatenation of two factoradic numbers, with two subscript "!"s.
concatenated decimal factoradics permutation pair 010 0:0:0!0:0:0! ((0,1,2),(0,1,2)) 110 0:0:0!0:1:0! ((0,1,2),(0,2,1)) ... 510 0:0:0!2:1:0! ((0,1,2),(2,1,0)) 610 0:1:0!0:0:0! ((0,2,1),(0,1,2)) 710 0:1:0!0:1:0! ((0,2,1),(0,2,1)) ... 2210 1:1:0!2:0:0! ((1,2,0),(2,0,1)) ... 3410 2:1:0!2:0:0! ((2,1,0),(2,0,1)) 3510 2:1:0!2:1:0! ((2,1,0),(2,1,0))
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). Other terms are given as the sequence 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.
Similar to how checking the divisibility of 4 in base 10 requires looking at only the last two digits, checking the divisibility of any number in factorial number system requires looking at only a finite number of digits. That is, it has a divisibility rule for each number.
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:
In mathematics, the factorial of a non-negative integer , denoted by , is the product of all positive integers less than or equal to . The factorial of also equals the product of with the next smaller factorial:
Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division. The result of a multiplication operation is called a product.
A numeral system 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.
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers can be represented by symbols, called numerals; for example, "5" is a numeral that represents the number five. As only a relatively small number of symbols can be memorized, basic numerals are commonly organized in a numeral system, which is an organized way to represent any number. The most common numeral system is the Hindu–Arabic numeral system, which allows for the representation of any non-negative integer using a combination of ten fundamental numeric symbols, called digits. In addition to their use in counting and measuring, numerals are often used for labels, for ordering, and for codes. In common usage, a numeral is not clearly distinguished from the number that it represents.
The octal, or oct for short, is the base-8 positional numeral system, and uses the digits 0 to 7. This is to say that 10octal represents eight and 100octal represents sixty-four. However, English, like most languages, uses a base-10 number system, hence a true octal system might use different vocabulary.
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 process of changing the linear order of an ordered set.
In number theory, given a prime number p, the p-adic numbers form an extension of the rational numbers which is distinct from the real numbers, though with some similar properties; p-adic numbers can be written in a form similar to decimals, but with digits based on a prime number p rather than ten, and extending to the left rather than to the right. Formally, given a prime number p, a p-adic number can be defined as a series
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
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 factor. Such units are common for instance in measuring time; a time of 32 weeks, 5 days, 7 hours, 45 minutes, 15 seconds, and 500 milliseconds might be expressed as a number of minutes in mixed-radix notation as:
... 32, 5, 07, 45; 15, 500 ... ∞, 7, 24, 60; 60, 1000
Positional notation usually denotes the extension to any base of the Hindu–Arabic numeral system. More generally, a positional system is a numeral system in which the contribution of a digit to the value of a number is the value of the digit multiplied by a factor determined by the position of the digit. In early numeral systems, such as Roman numerals, a digit has only one value: I means one, X means ten and C a hundred. In modern positional systems, such as the decimal system, the position of the digit means that its value must be multiplied by some value: in 555, the three identical symbols represent five hundreds, five tens, and five units, respectively, due to their different positions in the digit string.
In computer science, arbitrary-precision arithmetic, also called bignum arithmetic, multiple-precision arithmetic, or sometimes infinite-precision arithmetic, indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most arithmetic logic unit (ALU) hardware, which typically offers between 8 and 64 bits of precision.
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.
In mathematics, and in particular in combinatorics, the combinatorial number system of degree k, also referred to as combinadics, or the Macaulay representation of an integer, is a correspondence between natural numbers N and k-combinations. The combinations are represented as strictly decreasing sequences ck > ... > c2 > c1 ≥ 0 where each ci corresponds to the index of a chosen element in a given k-combination. Distinct numbers correspond to distinct k-combinations, and produce them in lexicographic order. The numbers less than correspond to all k-combinations of {0, 1, ..., n − 1}. The correspondence does not depend on the size n of the set that the k-combinations are taken from, so it can be interpreted as a map from N to the k-combinations taken from N; in this view the correspondence is a bijection.
In mathematics, 0.999... is a notation for the repeating decimal consisting of an unending sequence of 9s after the decimal point. This repeating decimal is a numeral that represents the smallest number no less than every number in the sequence ; that is, the supremum of this sequence. This number is equal to 1. In other words, "0.999..." is not "almost exactly" or "very, very nearly but not quite" 1 – rather, "0.999..." and "1" represent exactly the same number.
Non-standard positional numeral systems here designates numeral systems that may loosely be described as positional systems, but that do not entirely comply with the following description of standard positional systems:
The radix economy of a number in a particular base is the number of digits needed to express it in that base, multiplied by the base. This is one of various proposals that have been made to quantify the relative costs of using different radices in representing numbers, especially in computer systems.
A negative base may be used to construct a non-standard positional numeral system. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative—that is to say, the base b is equal to −r for some natural number r.
A repeating decimal or recurring decimal is a decimal representation of a number whose digits are periodic and the infinitely repeated portion is not zero. It can be shown that a number is rational if and only if its decimal representation is repeating or terminating. For example, the decimal representation of 1/3 becomes periodic just after the decimal point, repeating the single digit "3" forever, i.e. 0.333.... A more complicated example is 3227/555, whose decimal becomes periodic at the second digit following the decimal point and then repeats the sequence "144" forever, i.e. 5.8144144144.... At present, there is no single universally accepted notation or phrasing for repeating decimals. Another example of this is 593/53, which becomes periodic after the decimal point, repeating the 13-digit pattern "1886792452830" forever, i.e. 11.18867924528301886792452830....
The digits of some specific integers permute or shift cyclically when they are multiplied by a number n. Examples are:
In applied mathematics, a bit-reversal permutation is a permutation of a sequence of items, where is a power of two. It is defined by indexing the elements of the sequence by the numbers from to , representing each of these numbers by its binary representation, and mapping each item to the item whose representation has the same bits in the reversed order.