Factorial number system
The factorial number system, also known as the factoradic, is a mixed radix numeral system for representing natural numbers in which the place values are successive factorials (1!, 2!, 3!, and so on), and the digit in the position weighted by k! ranges from 0 to k.[1] Every positive integer has a unique representation in this system as n = \sum_{k=1}^{m} d_k \cdot k!, where $0 \leq d_k \leq k and d_m \neq 0, with the 0! place (value 1) often omitted as its digit is always 0.[2] For example, the number 2020 in factorial base is written as 2 4 4 0 2 0 (meaning $2 \cdot 6! + 4 \cdot 5! + 4 \cdot 4! + 0 \cdot 3! + 2 \cdot 2! + 0 \cdot 1!).[2]
The system was first introduced by Georg Cantor in 1869 as a way to express natural numbers using factorial bases, providing a canonical form for integers.[1] In 1888, Charles-Ange Laisant extended its application to permutations, demonstrating a bijection between the numbers from 0 to n! − 1 in factorial representation and the elements of the symmetric group Sn, which corresponds to all permutations of n objects in lexicographic order.[3] This connection, often via the Lehmer code, allows the factorial system to encode permutations uniquely, where the digits indicate the positions of elements in the permutation.[1]
Key properties include the uniqueness of representations, proven by induction and the pigeonhole principle, ensuring no two distinct digit sequences yield the same number within the bounds of the digits.[2] The maximum value representable with digits up to k! is (k+1)! − 1, matching the count of permutations of k+1 elements.[4] Notable applications leverage this structure for combinatorial optimization, such as generating permutations sequentially to solve the traveling salesman problem (TSP), and in cryptography for error-detecting codes due to "forbidden" digit combinations that enhance noise resistance.[4] The system also extends to fractional values in the unit interval and has been generalized to other polyadic bases.[4]
Basic Concepts
Historical Background
The factorial number system originated in the late 19th century as a specialized numeral system designed for enumerating permutations. It was first introduced by Georg Cantor in 1869 as a way to express natural numbers using factorial bases.[1] The term "numération factorielle" and its application to permutations were first described by French mathematician Charles-Ange Laisant in his 1888 paper, where he demonstrated a bijection between numbers in factorial representation and permutations in lexicographic order.[3] Laisant's work focused on representing integers using factorial bases to systematically classify permutations based on their inversion counts, enabling a direct and unique mapping between numbers and permutation arrangements.[3]
The initial motivation behind this system was to adapt traditional positional numeral systems to the combinatorial structure of permutations, avoiding redundancy and facilitating efficient enumeration without exhaustive listing. By assigning each permutation a unique factorial representation, Laisant demonstrated applications in calculating determinants and ranking arrangements, such as mapping the 24 permutations of four objects to integers from 0 to 23. This approach provided a compact tool for combinatorial analysis at a time when manual computation of large permutation sets was prevalent.[3]
In the 20th century, the factorial number system evolved through advancements in combinatorial mathematics, particularly in the development of algorithms for permutation generation and indexing. It gained formalization in works addressing efficient permutation enumeration, such as those exploring mixed-radix representations for computational purposes. This progression built on Laisant's foundation, integrating the system into broader studies of combinatorial structures and algorithmic efficiency.[5]
Today, it connects to modern combinatorial applications, including algorithmic generation of permutations in computer science.[5]
Definition and Notation
The factorial number system, also known as the factoradic system, is a positional numeral system that represents positive integers using factorials as place values. In this system, the position weights increase from right to left, with the rightmost position (index 1) having weight $1!, the next (index 2) having weight $2!, and the k-th position having weight k!.[2][6]
It operates as a mixed radix system, where the radix for the k-th position (from the right) is k+1, meaning the digit a_k in that position satisfies $0 \leq a_k \leq k. This varying radix structure distinguishes it from fixed-base systems like decimal or binary, allowing each position to accommodate a number of possible digits equal to one more than its index.[2][7]
The value n of a number in this system is given by the equation
n = \sum_{k=1}^m a_k \cdot k!,
where m is the highest position needed, a_m \neq 0, and the digits satisfy the constraints above; the $0! position is typically omitted as it always holds a_0 = [0](/page/0). Standard notation writes the representation as the sequence a_m a_{m-1} \cdots a_2 a_1 (without separators or a leading zero position), directly corresponding to the summation. This system, introduced by Cantor in 1869 and applied to permutations by Laisant in 1888, provides a unique representation for natural numbers.[3][2][6][1]
Examples and Properties
Illustrative Examples
To illustrate the factorial number system, consider the representations of small non-negative integers, where each place value corresponds to a factorial (1! for the units place, 2! for the next, and so on), and the digit in the position for k! is constrained to range from 0 to k.[8]
The system provides a unique representation for each integer, with a one-to-one mapping to decimal numbers up to $3! = 6. The table below lists these representations, omitting the trailing 0! term (which is conventionally 0 for integers and equals 1 in value but carries no additional information).[9]
| Decimal | Factorial Representation |
|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 20 |
| 5 | 21 |
| 6 | 100 |
Key Properties
The factorial number system, also known as the factoradic system, possesses several fundamental mathematical properties that distinguish it from fixed-base numeral systems. One key attribute is the uniqueness of representation: every natural number has a unique factoradic representation without leading zeros, where a number n is expressed as n = \sum_{k=1}^m a_k \cdot k! with $0 \leq a_k \leq k and a_m \neq 0. This uniqueness is established through a greedy algorithm that selects the largest possible digit a_k at each step while respecting the digit bounds, ensuring no two distinct sequences yield the same value, as proven by contradiction using the bounded coefficients.[2]
Complementing this is the system's completeness, which guarantees that every natural number can be represented exactly. Specifically, all integers from 0 to (m+1)! - 1 are precisely representable using at most m digits, with the total count of such representations equaling (m+1)!, achieved via the pigeonhole principle and induction on the factorial bases.[2] For illustration, the number 5 is represented as $2:1 (i.e., $2 \cdot 2! + 1 \cdot 1!), fitting within the bounds for two digits.[2]
A distinctive number-theoretic property involves prime numbers: all primes greater than 3 terminate in either \dots 0:1 or \dots 2:1 in their factoradic representation, serving as a unique identifier modulo 6 (with $0:1 for primes congruent to 1 mod 6 and $2:1 for those congruent to 5 mod 6). This pattern stems from the divisibility properties enforced by the factorial bases, excluding other low-digit endings for composites.[9]
Finally, the system's rigid digit limits confer strong noise resistance, enabling high-probability error detection in transmitted representations. For an 8-digit factoradic number, the probability of detecting an error (assuming uniform distribution and single-digit corruption leading to invalid bounds) reaches up to 0.998, far surpassing many fixed-base systems due to the constrained valid sequences.[7]
Conversion Methods
Encoding (Decimal to Factoradic)
To convert a non-negative integer n to its factoradic representation, employ a greedy algorithm that identifies digits starting from the highest factorial place value. Determine the largest integer k such that k! \leq n; the digit a_k is then \lfloor n / k! \rfloor, which satisfies $0 \leq a_k \leq k. Update n to the remainder n \mod k! and repeat the process for (k-1)! down to $1!, yielding digits a_k a_{k-1} \dots a_1.[7]
This method ensures each digit adheres to the positional constraints of the factorial base, where the place value for a_j is j! and the maximum digit value is j. For illustration, apply the steps to n = 21:
- The largest k is 3, as $3! = 6 \leq 21 < 24 = 4!.
- a_3 = \lfloor 21 / 6 \rfloor = 3, remainder $21 \mod 6 = 3.
- For $2!, a_2 = \lfloor 3 / 2 \rfloor = 1, remainder $3 \mod 2 = 1.
- For $1!, a_1 = \lfloor 1 / 1 \rfloor = 1, remainder $1 \mod 1 = 0.
The resulting factoradic representation is $311_! (digits for positions 3, 2, 1).[7]
The following pseudocode outlines the algorithm:
function decimal_to_factoradic(n):
if n == 0:
return [] // empty or [0] representation
digits = []
k = 1
while [factorial](/page/Factorial)(k) <= n:
k += 1
k -= 1 // largest k with k! <= n
while k >= 1:
fact_k = [factorial](/page/Factorial)(k)
a_k = floor(n / fact_k)
digits.append(a_k) // prepend if building MSB first
n = n % fact_k
k -= 1
return digits // e.g., [3, 1, 1] for n=21
function decimal_to_factoradic(n):
if n == 0:
return [] // empty or [0] representation
digits = []
k = 1
while [factorial](/page/Factorial)(k) <= n:
k += 1
k -= 1 // largest k with k! <= n
while k >= 1:
fact_k = [factorial](/page/Factorial)(k)
a_k = floor(n / fact_k)
digits.append(a_k) // prepend if building MSB first
n = n % fact_k
k -= 1
return digits // e.g., [3, 1, 1] for n=21
Precomputing factorials up to a reasonable k (e.g., via dynamic programming) optimizes repeated calls, as factorials grow rapidly.[7]
For the edge case n = [0](/page/0), the representation consists of no digits or a single zero, as there are no non-zero coefficients needed. If n < 1! (i.e., n = [0](/page/0)), the process terminates immediately with the zero representation. This algorithm produces a unique factoradic form for every non-negative integer.[7]
Decoding (Factoradic to Decimal)
To convert a number from its factoradic representation back to decimal, evaluate the positional sum where each digit is multiplied by the factorial of its position index, starting from the rightmost digit as position 1 (corresponding to $1!).[9]
The factoradic representation is typically written as a sequence of digits a_m : a_{m-1} : \dots : a_1, where the leftmost digit a_m is the coefficient for m! and the rightmost a_1 for $1!; the $0! place (always 0) is omitted. The digits satisfy $0 \leq a_k \leq k for each position k. The decimal equivalent n is computed as
n = \sum_{k=1}^m a_k \cdot k!
To perform the decoding, follow these steps:
- Identify the positions: Assign the rightmost digit to $1!, the next to the left to $2!, and so on, up to the leftmost digit for m!.
- Compute each term: Multiply each digit by the factorial of its position (e.g., for the representation 3:2:1:0, treat it as a_3=3 for $3!, a_2=2 for $2!, a_1=1 for $1!, and a_0=0 for $0!, yielding $3 \times 6 + 2 \times 2 + 1 \times 1 + 0 \times 1 = 18 + 4 + 1 + 0 = 23).[9]
- Sum the terms to obtain n.
Trailing zeros in the $0! place are always omitted in standard notation, as a_0 = 0 by definition, ensuring unique representations without redundancy. Leading zeros do not appear, as the highest digit a_m is chosen such that $1 \leq a_m \leq m.
For example, consider the factoradic number 3:1:1, corresponding to positions $3!, $2!, and $1!:
n = 3 \times 3! + 1 \times 2! + 1 \times 1! = 3 \times 6 + 1 \times 2 + 1 \times 1 = 18 + 2 + 1 = 21.
This summation directly yields the decimal value, leveraging the mixed-radix structure of the system.[9]
Applications in Combinatorics
Relation to Permutations
The factorial number system establishes a bijection between the integers from 0 to m! - 1 and the m! permutations of a set of m distinct elements, ordered lexicographically. This mapping, first described by Charles-Ange Laisant in 1888, allows each integer n in this range to uniquely correspond to one permutation, facilitating systematic enumeration and indexing of all possible arrangements.[11]
In this representation, the factoradic digits of n, denoted as n = a_{m-1} \cdot (m-1)! + \cdots + a_1 \cdot 1! + a_0 \cdot 0! where $0 \leq a_k \leq k, directly indicate selections from the remaining elements at each step. Specifically, the digit a_k specifies the position (0-based index) of the element to choose for the (m-k)-th position in the permutation, from the list of unused elements sorted in increasing order. This process builds the permutation sequentially: begin with the full sorted list of elements, select the a_{m-1}-th remaining element for the first position, remove it, then select the a_{m-2}-th from the updated list for the second position, and continue until all positions are filled.[12]
To illustrate, consider m=4 and n=21, with elements \{1, 2, 3, 4\} and factoradic representation $21 = 3 \cdot 3! + 1 \cdot 2! + 1 \cdot 1! + 0 \cdot 0!, so digits a_3=3, a_2=1, a_1=1, a_0=0. Start with available list [1, 2, 3, 4]: select index 3 (element 4) for the first position, leaving [1, 2, 3]; select index 1 (element 2) for the second, leaving [1, 3]; select index 1 (element 3) for the third, leaving {{grok:render&&&type=render_inline_citation&&&citation_id=1&&&citation_type=wikipedia}}; select index 0 (element 1) for the last. The resulting permutation is $4, 2, 3, 1, which is the 21st (0-based) in lexicographic order.[13]
This bijection enables efficient generation and traversal of all m! permutations without redundancy or omission, by incrementing n from 0 to m! - 1 and converting each to its corresponding permutation via the digit-based selection algorithm. Such indexing is particularly useful in combinatorial algorithms requiring ordered access to permutations, as it avoids explicit storage of all arrangements.[14]
Lehmer Codes
The Lehmer code encodes a permutation of n elements using the factorial number system, where each digit corresponds to the number of inversions involving the element at a specific position. Specifically, for a permutation \pi = (\pi_1, \pi_2, \dots, \pi_n), the digits a_k (for k = 1 to n) are defined such that a_k counts the number of positions j < k where \pi_j > \pi_k, representing the larger elements to the left of \pi_k. These digits satisfy $0 \leq a_k < k, ensuring a unique factoradic representation.
The sequence of these inversion counts forms the Lehmer code, often written in reverse order (from a_n to a_1) to align with the factorial bases from highest to lowest place value. For a permutation \pi, the code is computed by iterating through each position k and tallying the qualifying left inversions, yielding the factoradic digits directly. This construction establishes a bijection between permutations and factoradic numbers from 0 to n! - 1.[15]
The Lehmer code of a permutation corresponds precisely to its index in the lexicographic ordering of all permutations, where the factoradic value gives the position starting from 0.
For example, consider the permutation \pi = (3, 1, 4, 2) of \{1, 2, 3, 4\}:
- At position 1 (\pi_1 = 3): 0 larger elements to the left.
- At position 2 (\pi_2 = 1): 1 larger element (3 > 1).
- At position 3 (\pi_3 = 4): 0 larger elements (3 < 4, 1 < 4).
- At position 4 (\pi_4 = 2): 2 larger elements (3 > 2, 4 > 2).
The inversion counts are thus 0, 1, 0, 2 from positions 1 to 4. The Lehmer code, listed as digits from highest to lowest base, is 2:0:1:0, equivalent to the factoradic number $2 \cdot 3! + 0 \cdot 2! + 1 \cdot 1! + 0 \cdot 0! = 13, confirming its rank in lexicographic order.
This encoding compresses permutation information into a compact sequence of small integers, facilitating efficient ranking (assigning a unique index) and unranking (generating the permutation from an index) operations without needing to store or generate the full sequence of elements.[16]
Further Extensions
Fractional Values
The factorial number system extends naturally to real numbers by incorporating a fractional part beyond the radix point, where the place values are defined using reciprocals of factorials starting from 2!. Specifically, the k-th fractional position corresponds to the weight 1/(k+1)!, for k = 1, 2, 3, ..., since negative factorials are undefined in the standard sense. A real number is thus represented as an integer part n (in factorial base) followed by the radix point and digits b_1 b_2 b_3 \dots, yielding the value
x = n + \sum_{k=1}^{\infty} \frac{b_k}{(k+1)!},
where each digit satisfies $0 \leq b_k \leq k. This variable upper bound on digits mirrors the integer part's structure but adapts to the decreasing place values for convergence.[17]
Rational numbers in this system exhibit behaviors analogous to those in fixed-base representations like decimal. If the denominator of a reduced rational fraction divides some factorial m!, its representation terminates after at most m fractional digits, as the remaining places can be zero. Other rationals possess non-terminating expansions, which are typically infinite and may repeat periodically, reflecting the system's ability to approximate any real through the factorial series.[17]
For instance, the rational 1/3 admits the terminating representation 0:0 2, computed via the greedy algorithm: multiplying 1/3 by 2 yields a fractional part less than 1 (digit b_1 = 0), then multiplying the remainder by 3 gives exactly 2 (digit b_2 = 2), with all subsequent digits zero. The value is
\frac{0}{2!} + \frac{2}{3!} = \frac{2}{6} = \frac{1}{3}.
This example illustrates convergence and exactness for terminating cases.[17]
Uniqueness of representations follows from the digit constraints: irrationals have a single infinite expansion, while rationals have dual forms—one finite and one infinite (e.g., ending in a tail of maximum digits, akin to 0.4999\dots = 0.5 in decimal). By convention, preferring the terminating form when available ensures a unique representation for every real number, avoiding ambiguities inherent in fixed-base systems.[17]
Modern Applications
The factorial number system enables robust error detection and noise-resistant coding due to its strict digit constraints, where each position d_k satisfies $0 \leq d_k \leq k, making invalid representations easily identifiable as errors. This property allows for high detection rates in data transmission; for instance, in an 8-digit factorial code, the probability of detecting an error introduced by noise is approximately 99.8%, as only valid permutations correspond to legitimate codes while the vast majority of altered sequences are forbidden. Such coding schemes integrate error correction with permutation-based recovery, providing comprehensive protection against transmission errors in noisy channels.[7]
In cryptography, the system supports noise-immune encryption through factorial-based ciphers that leverage permutation indexing for secure key generation. Permutations derived from factorial representations serve as keys, decomposed into disjoint cycles to ensure unique factorization and resistance to unauthorized decryption, even in insecure environments without dedicated key exchange channels. For example, a cryptosystem based on the symmetric group S_n encodes messages as permutations via the factorial system, encrypts them using powers of a generator permutation, and decrypts with private exponents, offering a bijection between integers and permutations for efficient, secure operations. These methods combine confidentiality with inherent error tolerance, suitable for applications in secure communications.[7][18][6]
The factorial number system facilitates efficient enumeration in optimization problems, such as the traveling salesman problem (TSP), by enabling sequential generation of permutations without exhaustive brute-force search. This approach systematically indexes routes as factorial numbers, allowing targeted evaluation of promising paths and outperforming traditional methods in scalability for combinatorial routing tasks. In computer science, it simplifies interval searches over permutation spaces, supports universal solvers for broader combinatorial problems by providing a natural ranking mechanism, and aids in representing and querying ranked data structures like ordered lists or trees.[7]
Recent developments, including a 2024 study on mixed-base factorial systems, highlight enhanced applications in secure communications and algorithmic efficiency, with factorial numbers enabling compression ratios up to 1.745 for short sequences and improved noise resistance in applied sciences. These advances underscore the system's growing role in integrating combinatorial encoding with practical computational challenges.[7]