View source for Factorial number system

{{short description|Numeral system in combinatorics}}
{{numeral systems}}
{{Refimprove|date=March 2021}}
In [[combinatorics]], the '''factorial number system''' (also known as '''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 [[radix|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 (discrete mathematics)|inversion]] table<ref>{{citation
| last=Knuth | first = D. E. | author-link = Donald Ervin Knuth
| title = [[The Art of Computer Programming]]
| contribution = Volume 3: Sorting and Searching | publisher = Addison-Wesley | year = 1973
| isbn = 0-201-89685-0
| pages = 12}}</ref> representation; in the
former case the resulting map from [[integer]]s to permutations of ''n'' elements lists them in [[lexicographical order]]. General mixed radix systems were studied by [[Georg Cantor]].<ref>{{citation
 | last = Cantor | first = G. | author-link= Georg Cantor
 | title = Zeitschrift für Mathematik und Physik | volume = 14 | year =1869}}.</ref>

The term "factorial number system" is used by [[Donald Knuth|Knuth]],<ref>{{citation
 | last = Knuth | first = D. E. | author-link = Donald Ervin Knuth
 | contribution = Volume 2: Seminumerical Algorithms
 | edition = 3rd
 | isbn = 0-201-89684-2
 | pages = 192
 | publisher = Addison-Wesley
 | title = The Art of Computer Programming
 | year = 1997}}.</ref>
while the French equivalent "numération factorielle" was first used in 1888.<ref>{{citation
 | last = Laisant | first = Charles-Ange | author-link = Charles-Ange Laisant
 | journal = Bulletin de la Société Mathématique de France
 | language = French
 | pages = 176–183
 | title = Sur la numération factorielle, application aux permutations
 | url = http://www.numdam.org/item?id=BSMF_1888__16__176_0
 | volume = 16
 | year = 1888}}.</ref> The term "factoradic", which is a [[portmanteau]] of factorial and mixed radix, appears to be of more recent date.<ref>The term "factoradic" is apparently introduced in {{citation
 | last = McCaffrey | first = James | author-link = James D. McCaffrey
 | publisher = Microsoft Developer Network
 | title = Using Permutations in .NET for Improved Systems Security
 | url = http://msdn2.microsoft.com/en-us/library/aa302371.aspx
 | year = 2003}}.</ref>

== Definition ==

The factorial number system is a [[mixed radix]] [[numeral system]]: the ''i''-th digit from the right has base&nbsp;''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 {{math|(''i''&nbsp;−&thinsp;1)}}! (its place value).

{| class="wikitable" style="text-align:right;"
|-
! {{rh}} | Radix/Base                     
|    8  ||   7  ||   6 ||  5  ||  4 ||  3 ||  2 || 1
|-
! {{rh}} | Place value               
|   7!  ||  6!  ||  5! ||  4! || 3! || 2! || 1! || 0!
|-
! {{rh}} | Place value in decimal   
| 5040 || 720 || 120 || 24 || 6 ||  2 ||  1 || 1
|-
! {{rh}} | 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 {{OEIS|id=A124252}}. The factorial number system is sometimes defined with the 0! place omitted because it is always zero {{OEIS|id=A007623}}.

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<sub>!</sub> stands for

: {{=}} 3×5!&nbsp;+&nbsp;4×4!&nbsp;+&nbsp;1×3!&nbsp;+&nbsp;0×2!&nbsp;+&nbsp;1×1!&nbsp;+&nbsp;0×0!&nbsp;
: {{=}} ((((3×5&nbsp;+&nbsp;4)×4&nbsp;+&nbsp;1)×3&nbsp;+&nbsp;0)×2&nbsp;+&nbsp;1)×1&nbsp;+&nbsp;0
: {{=}} &nbsp;463<sub>10</sub>.

(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, 463<sub>10</sub> can be transformed into a factorial representation by these successive divisions:
{| style="text-align:right;"
|
: 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 3:4:1:0:1:0<sub>!</sub>.

In principle, this system may be extended to represent [[rational number]]s, 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 (discrete mathematics)|inversion]] related vectors. The left and right inversion counts <math>l</math> and <math>r</math> (the latter often called [[Lehmer code]]) are particularly eligible to be interpreted as factorial numbers. <math>l</math> gives the permutation's position in reverse [[colexicographical order|colexicographic]] order (the default order of this table), and the latter the position in [[lexicographical order|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 ({{OEIS2C|A034968}} in the tables default order).

[[File:Symmetric group 4; permutohedron 3D; Lehmer codes.svg|thumb|400px|The factorial numbers of a given length form a [[permutohedron]] when ordered by the bitwise <math>\le</math> relation<br/><br/>These are the right inversion counts (aka Lehmer codes) of the permutations of four elements.]]
{{4-el perm inversions}}

For another example, the greatest number that could be represented with six digits would be 543210<sub>!</sub> which equals 719 in [[decimal]]:
:5×5! + 4×4! + 3x3! + 2×2! + 1×1! + 0×0!.

Clearly the next factorial number representation after 5:4:3:2:1:0<sub>!</sub> is 1:0:0:0:0:0:0<sub>!</sub> which designates 6!&nbsp;=&nbsp;720<sub>10</sub>, 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:
:<math> \sum_{i=0}^n {i\cdot i!} = {(n+1)!} - 1. </math>

This can be easily [[mathematical proof|proved]] with [[mathematical induction]], or simply by noticing that <math>\forall i, i\cdot i!=(i+1-1)\cdot i!=(i+1)!-i!</math>: 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&nbsp;×&nbsp;10!&nbsp;=&nbsp;36,288,000<sub>10</sub>, which may be written A0000000000<sub>!</sub>=10:0:0:0:0:0:0:0:0:0:0<sub>!</sub>, but not 100000000000<sub>!</sub> = 1:0:0:0:0:0:0:0:0:0:0:0<sub>!</sub> which denotes 11! = 39,916,800<sub>10</sub>. Thus using letters A–Z to denote digits 10, 11, 12, ..., 35 as in other base-''N'' make the largest representable number 36&nbsp;×&nbsp;36!&nbsp;−&nbsp;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<sub>4</sub>0<sub>3</sub>1<sub>2</sub>0<sub>1</sub>, this number also can be written as 2:0:1:0<sub>!</sub>). 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 ==

There is a natural [[function (mathematics)|mapping]] between the integers {{math|0,&nbsp;1,&nbsp;...,&nbsp;''n''!&nbsp;−&nbsp;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 {{math|1=''n''&nbsp;=&nbsp;3}}, such a mapping is

{| class="wikitable"
|-
!scope="col"| decimal
!scope="col"| factoradic
!scope="col"| permutation
|-
|0<sub>10</sub>
|0:0:0<sub>!</sub>
|(0,1,2)
|-
|1<sub>10</sub>
|0:1:0<sub>!</sub>
|(0,2,1)
|-
|2<sub>10</sub>
|1:0:0<sub>!</sub>
|(1,0,2)
|-
|3<sub>10</sub>
|1:1:0<sub>!</sub>
|(1,2,0)
|-
|4<sub>10</sub>
|2:0:0<sub>!</sub>
|(2,0,1)
|-
|5<sub>10</sub>
|2:1:0<sub>!</sub>
|(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<sub>!</sub> 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<sub>!</sub>  ─►  (4,0,6,2,1,3,5)
 factoradic: 4              :   0            :   4          :   1        :   0      :   0    :   0<sub>!</sub>
             ├─┬─┬─┬─┐          │                ├─┬─┬─┬─┐      ├─┐          │          │        │
 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 groups|direct product]] of two [[permutation group]]s is the [[concatenation]] of two factoradic numbers, with two subscript "!"s.
            concatenated
  decimal   factoradics        permutation pair
     0<sub>10</sub>     0:0:0<sub>!</sub>0:0:0<sub>!</sub>           ((0,1,2),(0,1,2))
     1<sub>10</sub>     0:0:0<sub>!</sub>0:1:0<sub>!</sub>           ((0,1,2),(0,2,1))
                ...
     5<sub>10</sub>     0:0:0<sub>!</sub>2:1:0<sub>!</sub>           ((0,1,2),(2,1,0))
     6<sub>10</sub>     0:1:0<sub>!</sub>0:0:0<sub>!</sub>           ((0,2,1),(0,1,2))
     7<sub>10</sub>     0:1:0<sub>!</sub>0:1:0<sub>!</sub>           ((0,2,1),(0,2,1))
                ...
    22<sub>10</sub>     1:1:0<sub>!</sub>2:0:0<sub>!</sub>           ((1,2,0),(2,0,1))
                ...
    34<sub>10</sub>     2:1:0<sub>!</sub>2:0:0<sub>!</sub>           ((2,1,0),(2,0,1))
    35<sub>10</sub>     2:1:0<sub>!</sub>2:1:0<sub>!</sub>           ((2,1,0),(2,1,0))

== Fractional values ==

Unlike single radix systems whose place values are ''base''<sup>''n''</sup> 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 number|prime]] has a length of exactly that prime (less one if the 1/1! place is omitted). Other terms are given as the sequence [https://oeis.org/A046021 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...|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:

* <math>1/2 = 0.0\ 1_!</math>
* <math>1/3 = 0.0\ 0\ 2_!</math>
* <math>2/3 = 0.0\ 1\ 1_!</math>
* <math>1/4 = 0.0\ 0\ 1\ 2_!</math>
* <math>3/4 = 0.0\ 1\ 1\ 2_!</math>
* <math>1/5 = 0.0\ 0\ 1\ 0\ 4_!</math>
* <math>1/6 = 0.0\ 0\ 1_!</math>
* <math>5/6 = 0.0\ 1\ 2_!</math>
* <math>1/7 = 0.0\ 0\ 0\ 3\ 2\ 0\ 6_!</math>
* <math>1/8 = 0.0\ 0\ 0\ 3_!</math>
* <math>1/9 = 0.0\ 0\ 0\ 2\ 3\ 2_!</math>
* <math>1/10 = 0.0\ 0\ 0\ 2\ 2_!</math>
* <math>1/11 \ \ = 0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_!</math>
* <math>2/11 \ \ = 0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_!</math>
* <math>9/11 \ \ = 0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_!</math>
* <math>10/11 = 0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9 \ 1_!</math>
* <math>1/12 \ \ = 0.0\ 0\ 0\ 2_!</math>
* <math>5/12 \ \ = 0.0\ 0\ 2\ 2_!</math>
* <math>7/12 \ \ = 0.0\ 1\ 0\ 2_!</math>
* <math>11/12 = 0.0\ 1\ 2\ 2_!</math>
* <math>1/15 = 0.0\ 0\ 0\ 1\ 3_!</math>
* <math>1/16 = 0.0\ 0\ 0\ 1\ 2\ 3_!</math>
* <math>1/18 = 0.0\ 0\ 0\ 1\ 1\ 4_!</math>
* <math>1/20 = 0.0\ 0\ 0\ 1\ 1_!</math>
* <math>1/24 = 0.0\ 0\ 0\ 1_!</math>
* <math>1/30 = 0.0\ 0\ 0\ 0\ 4_!</math>
* <math>1/36 = 0.0\ 0\ 0\ 0\ 3\ 2_!</math>
* <math>1/60 = 0.0\ 0\ 0\ 0\ 2_!</math>
* <math>1/72 = 0.0\ 0\ 0\ 0\ 1\ 4_!</math>
* <math>1/120 = 0.0\ 0\ 0\ 0\ 1_!</math>
* <math>1/144 = 0.0\ 0\ 0\ 0\ 0\ 5_!</math>
* <math>1/240 = 0.0\ 0\ 0\ 0\ 0\ 3_!</math>
* <math>1/360 = 0.0\ 0\ 0\ 0\ 0\ 2_!</math>
* <math>1/720 = 0.0\ 0\ 0\ 0\ 0\ 1_!</math>

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

* <math>e = 1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1..._!</math>
* <math>e^{-1} = 0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E..._!</math>
* <math>\sin(1) = 0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E..._!</math>
* <math>\cos(1) = 0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0..._!</math>
* <math>\sinh(1) = 1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0..._!</math>
* <math>\cosh(1) = 1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1..._!</math>

== See also ==
* [[Combinatorial number system]] (also called combinadics)
* [[Profinite integer]]s, which can be represented as infinite digit sequences in the factorial number system
* [[Steinhaus–Johnson–Trotter algorithm]], an algorithm that generates [[Gray code]]s for the factorial number system

== References ==
<references/>
*{{citation
 | last1 = Mantaci
 | first1 = Roberto
 | last2 = Rakotondrajao
 | first2 = Fanja
 | journal = Discrete Mathematics and Theoretical Computer Science
 | pages = 101–108
 | title = A permutation representation that knows what "Eulerian" means
 | url = http://www.dmtcs.org/volumes/abstracts/pdfpapers/dm040203.pdf
 | volume = 4
 | year = 2001
 | access-date = 2005-03-27
 | archive-url = https://web.archive.org/web/20110524210428/http://www.dmtcs.org/volumes/abstracts/pdfpapers/dm040203.pdf
 | archive-date = 2011-05-24
 | url-status = dead
 }}.
*{{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 ==
* [https://web.archive.org/web/20050115122923/http://www-ang.kfunigraz.ac.at/~fripert/fga/k1lehm.html 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.
* [http://archive.numdam.org/ARCHIVE/BSMF/BSMF_1888__16_/BSMF_1888__16__176_0/BSMF_1888__16__176_0.pdf Factorial number system]

[[Category:Combinatorics]]
[[Category:Factorial and binomial topics]]
[[Category:Non-standard positional numeral systems]]