Factorial Number System¶

A mixed-radix positional representation with factorial place values and digit bound 0 through i at the i-factorial place, giving every nonnegative integer a unique expansion and a natural rank/unrank bridge to permutations.

Version: v3 · 2026-09-06 · History
Domain-specific #: 1820
Origin domain: mathematics
Subdomain: combinatorial enumeration
Aliases: Factoradic, Factorial base, Factorial representation, Factorial radix system

Core Idea¶

The Factorial Number System, or factoradic representation, is a mixed-radix positional system in which the digit at place (i) has weight (i!) and is restricted to

\[ 0\le a_i\le i. \]

Every nonnegative integer (N) has a unique finite representation

\[ N=\sum_{i=0}^{m}a_i i!. \]

The (0!) digit is necessarily zero; the (1!) digit is 0 or 1; the (2!) digit is 0, 1, or 2; and so on. Thus the successive digit radices are \(1,2,3,\ldots\), not one repeated base. “Factorial base” is conventional shorthand, but factorials are place values and the system is genuinely mixed-radix.^[1]

The bounds fit the place values exactly because

\[ \sum_{i=0}^{m}i\,i!=(m+1)!-1. \]

All lower places at their maximum represent one less than the next place, providing the carry rule and uniqueness. This same digit geometry matches the successive choice counts in a permutation. For (N<n!), the factoradic digits can be read as a Lehmer code to select the (N)-th permutation of (n) ordered elements in lexicographic order.^[2]

Structural Signature¶

The defining roles are:

A nonnegative integer target: the quantity to represent.
Factorial place values: \(0!,1!,2!,\ldots\).
Position-dependent radices: the (i!) coefficient has (i+1) admissible values.
Bounded digits: \(a_i\in\{0,\ldots,i\}\).
Finite support: all sufficiently high digits are zero for an integer.
Evaluation: sum (a_i i!) to recover the integer.
Carry relation: ((i+1)i!=(i+1)!).
Uniqueness: each nonnegative integer has exactly one bounded expansion.
Conversion algorithm: successive division by radices \(1,2,3,\ldots\), recording remainders.
Permutation bridge: the digit bounds equal the sizes of successive remaining-choice sets, enabling rank/unrank.
Notation boundary: multi-digit coefficients require separators or a declared symbol alphabet.

Practical test: verify both the factorial weights and digit bounds. A sum of arbitrary multiples of factorials without the canonical bounds is a factorial series, not necessarily a factorial-number representation.

What It Is Not¶

It is not Decimal or any fixed-radix system. Decimal uses powers (10^i) and the same digit set at every place; factoradic radices increase by position.

It is not a factorial itself, the factorial function, falling/rising factorial notation, or a representation using base (n!). It is not the Lehmer code in every usage. A Lehmer code represents a permutation by inversion counts; the same bounded digit vector can be interpreted numerically as a factoradic, but the code and numeral have different targets.

It is not Permutation. The system ranks and encodes permutations but also represents ordinary nonnegative integers independent of any chosen (n). Nor should a proposed fractional extension be treated as part of the unqualified integer core; negative factorial indices are undefined, so post-radix-point conventions require additional design choices.

Scope of Application¶

The main application is ranking and unranking finite permutations. There are exactly (n!) permutations of (n) distinct elements and exactly (n!) digit vectors satisfying \(0\le a_i\le i\) for \(i=0,\ldots,n-1\). Interpreting the digits as successive indices into a shrinking ordered list gives a bijection between integers \(0,\ldots,n!-1\) and permutations.^[3]

The representation also appears in combinatorial generation, exhaustive search, state indexing for puzzles, compact serialization of orderings, random-permutation selection from an integer rank, and proofs involving mixed-radix enumeration. Arithmetic is possible but less convenient than in fixed radix because carries and digit alphabets change at every place.

Factorial fractions can represent rationals using reciprocal factorial place values under specified conventions, and infinite factorial-series expansions connect to analysis and number theory. Those extensions share weights but require separate uniqueness, termination, and endpoint conventions.

Clarity¶

Indexing conventions cause most confusion. In this draft, (a_i) multiplies (i!) and ranges from 0 through (i). A written digit string \(a_m:a_{m-1}:\cdots:a_0\) therefore has (a_0=0). Some treatments omit the always-zero (0!) place or describe the (i)-th position using one-based indices. Equations should accompany notation.

To convert (N), repeatedly divide by 1, 2, 3, and upward: the remainder on division by (i+1) becomes (a_i), and the quotient continues. Division by 1 yields the forced zero coefficient and can be omitted operationally.

For digits above 9, concatenation is ambiguous. 10:0:... needs separators or symbols. Unlike a fixed finite radix, an unbounded factoradic representation eventually needs arbitrarily large digit labels, so it is a positional representation but not necessarily a finite-alphabet numeral language.

Manages Complexity¶

The system aligns numeric capacity with combinatorial branching. At the first choice of an (n)-element permutation there are (n) possibilities; after one selection there are (n-1); the process continues to one. Factoradic digits have exactly those successive ranges. This removes wasted codes and makes every valid digit vector correspond to one permutation.

Ranking converts an entire ordering into one integer that can be stored, compared, partitioned among workers, sampled, or used as an array index. Unranking reconstructs the ordering without enumerating all preceding permutations. Efficient implementations use balanced trees, Fenwick trees, or specialized linear-time algorithms to avoid repeated linear deletion from a list.^[4]

Abstract Reasoning¶

To represent an integer:

Set the current radix to 1 and current value to (N).
record the remainder under the current radix as the next digit.
replace the value with the quotient and increment the radix.
stop after the quotient becomes zero.
read the digits from most significant to least and verify \(0\le a_i\le i\).

To unrank a permutation of sorted elements:

pad the factoradic to (n) digits.
begin with the ordered list of all (n) elements.
use the most significant Lehmer/factoradic digit as a zero-based index into the remaining list.
remove the selected element and continue with the next digit.
the forced final zero selects the last remaining element.

Uniqueness follows from the carry identity: lower places span exactly (0) through ((m+1)!-1), so the coefficient of ((m+1)!) is determined by Euclidean division.

Knowledge Transfer¶

The mixed-radix method transfers literally to time units, calendar fields, and other systems where successive place capacities differ. The general design principle is to match each digit radix to the branching factor remaining at that stage.

The permutation correspondence transfers to other combinatorial classes only when their recursive counts support an appropriate ranking decomposition. Combinatorial number systems for subsets and Catalan-family rankings use analogous capacity-matched digits but not factorial place values; calling them factoradic would erase their different recurrence.

Examples¶

463. The representation

\[ 3:4:1:0:1:0_!=3\cdot5!+4\cdot4!+1\cdot3!+0\cdot2!+1\cdot1!+0\cdot0!=463. \]

Each coefficient respects its place bound.

Maximum six-digit value. (5:4:3:2:1:0_!=6!-1=719). Adding one carries to (1:0:0:0:0:0:0_!=6!=720).

Permutation of three elements. Ranks 0 through 5 have three-digit factoradics (000,010,100,110,200,210) under unseparated small-digit notation and map to the six lexicographically ordered permutations through successive selection.

Random rank. Uniformly sample an integer from (0) through (n!-1), convert it, and unrank to obtain a uniform permutation if the integer sampler is uniform and the bijection is implemented correctly.

Non-example. Writing \(7=3\cdot2!+1\cdot1!\) uses coefficient 3 at the (2!) place, violating \(a_2\le2\); it is a factorial sum but not canonical factoradic notation.

Structural Tensions¶

Perfect combinatorial fit versus awkward general arithmetic: the system excels at permutations but not everyday addition and multiplication.
Positional notation versus unbounded digit alphabet: higher places admit coefficients above any fixed symbol set.
Numeral versus code: one digit vector can denote an integer rank or a permutation inversion code.
Canonical integer core versus fractional variants: reciprocal factorial conventions require new choices.
Conceptual linearity versus implementation cost: simple successive selection can be quadratic without an indexed data structure.
Fixed ordering versus permutation identity: rank depends on the initial element order and lexicographic convention.

Structural–Framed Character¶

The integer system is fully structural: weights, digit bounds, evaluation, carries, and uniqueness are exact. Framing enters in notation, element ordering for permutation ranking, whether the forced zero place is displayed, and which fractional extension is adopted.

Structural Core vs. Domain Accent¶

The portable core is position-dependent capacity matched to a staged choice process. The domain accent is factorial place value and the exact \(0\ldots i\) digit bound, yielding the (n!) permutation correspondence. Removing those produces generic mixed-radix representation, not the Factorial Number System.

Representation is the proposed immediate parent. The system maps each nonnegative integer to a governed digit string and, under a Lehmer interpretation, maps ranks to permutations while preserving a precise decoding rule. Permutation, Bijectivity, Serialization, and Data Structure are related; Decimal is a fixed-radix sibling.

The prospective queue contains one strict edge to prime:representation. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Factorial Number System Domain-specific

Parents (1) — more general patterns this builds on

Factorial Number System is a kind of Representation Prime

Representation is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

Factorial Number System → Representation → Abstraction

Neighborhood in Abstraction Space¶

Factorial Number System sits in a sparse region of the domain-specific corpus (79^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Factorial function (n!): supplies place values but is not a numeral system.
Fixed base (n!): repeated powers of one base, unlike increasing radices.
Lehmer code: permutation inversion-count code that can be numerically interpreted as factoradic.
Inversion table: related permutation code with convention-dependent orientation.
Combinatorial number system: binomial-coefficient representation used for subsets.
Decimal: fixed radix ten.
Factorial series: may allow coefficient choices outside canonical integer digit bounds.

References¶

[1] Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, ISBN 978-0-201-03804-0. Standard treatment of combinatorial generation and mixed-radix ranking. registry ↩

[2] D. H. Lehmer, “Teaching Combinatorial Tricks to a Computer,” in Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10, American Mathematical Society, 1960, 179–193. registry ↩

[3] Wendy Myrvold and Frank Ruskey, “Ranking and Unranking Permutations in Linear Time,” Information Processing Letters 79(6), 2001, 281–284. DOI 10.1016/S0020-0190(01)00141-7. registry ↩

[4] Jörg Arndt, Matters Computational: Ideas, Algorithms, Source Code, Springer, 2011. DOI 10.1007/978-3-642-14764-7. registry ↩