Factorádico

El sistema factorádico es un sistema numérico de raíz mixta basado en factoriales en el que el n-ésimo dígito, empezando desde la derecha, debe ser multiplicado por n!

En este sistema numérico, el dígito de más a la derecha es siempre 0, el segundo 0 o 1, el tercero 0,1 o 2 y así sucesivamente. Existe también una variante del sistema factorádico en el que el dígito de más a la derecha es omitido porque es siempre cero ((sucesión A007623 en OEIS)).

Estos son los primeros veintiún números factorádicos:

Cómo otro ejemplo, el número mayor que pueda ser representado con seis dígitos sería 5₅4₄3₃2₂1₁0₀ que equivale a 719 in decimal:

5×5! + 4×4! + 3×3! + 2×2! + 1×1! + 0×0!.

Claramente el siguiente número factorádico después de 5₅4₄3₃2₂1₁0₀ es 1₆0₅0₄0₃0₂0₁0₀, que es igual a 6!. Así que el número anterior y el sumatorio de sus dígitos es igual a:

6! − 1.

El sistema factorádico no deja lugar para la ambigüedad. Ningún número puede ser representado de más de una manera porque la suma consecutiva de los factoriales, multiplicados por su posición es siempre el siguiente factorial menos uno:

${\displaystyle \sum _{i=0}^{n}{i\cdot i!}={(n+1)!}-1.}$

Que puede ser fácilmente probado por inducción matemática.

De cualquier manera, si usamos la numeración arábiga para escribir los dígitos (sin incluir los subíndices como en los ejemplos anteriores), la simple concatenación resulta ambigua para números que tengan un 'dígito' mayor a 9. El ejemplo más pequeño en el que sucede es 10×10!, escrito 10₁₀0₉0₈0₇0₆0₅0₄0₃0₂0₁0₀ mientras que 11! es 1₁₁0₁₀0₉0₈0₇0₆0₅0₄0₃0₂0₁0₀. Por lo que añadir un simple subíndice en notación factorádica (como se hizo para la notación en base-10 anteriormente) no es posible para números con más de 10 dígitos sin especificar claramente que dicho dígito es un subíndice (se puede apreciar que para 10×10!, no hay subíndice entre el no-subíndice de más a la izquierda "1" y el no-subíndice "0" immediatamente a su derecha que es para 11!). Usar letras A-Z para designar los dígitos 10,...,35 como en otros sistemas de base-N eleva este límite hasta 36! − 1.

Hay una relación natural entre los enteros 0, ..., n! − 1 (o de manera equivalente los números factorádicos con n elementos) en orden lexicográfico, cuando los enteros son expresados en forma factorádica. Esta relación ha sido llamada código Lehmer o código Lucas-Lehmer (tabla invertida). Por ejemplo, con n = 3, dicha relación es

El dígito factorádico de más a la izquierda 0,1 o 2 es elegido como el primer dígito de la permutación de la lista ordenada (0,1,2) y es eliminado de la lista. El primer índice de esta nueva lista vale cero y cada dígito sucesivo indica cuales de los siguientes elementos deben ser escogidos. Si el segundo dígito factorádico es "0" entonces el primer elemento de la lista es seleccionado como segundo dígito de la permutación y de nuevo es eliminado de la lista. De forma similar si el segundo dígito factorádico fuera "1", el segundo sería seleccionado y luego eliminado. El dígito factorádico final es siempre "0", y como la lista ahora contiene sólo un elemento éste es seleccionado como el último dígito de la permutación.

El proceso puede resultar más claro con un ejemplo mayor. Por ejemplo, aquí se muestra como los dígitos en el factorádico 4₆0₅4₄1₃0₂0₁0₀ (igual a 2982₁₀) se usan para seleccionar los dígitos (4,0,6,2,1,3,5), la permutación número 2982 de los números de 0 a 6.

                                 46054413020100 → (4,0,6,2,1,3,5)
Factorádico:  46         05                       44       13         02         01       00
             |          |                        |        |          |          |        |
    (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)
             |          |                        |        |          |          |        |
Permutación:(4,         0,                       6,       2,         1,         3,       5)

• Knuth, Donald (1997), «Volume 2: Seminumerical Algorithms», The Art of Computer Programming (3rd edición), Addison-Wesley, pp. 65-66, ISBN 0-201-89684-2..

• McCaffrey, James (2003), Using Permutations in .NET for Improved Systems Security, Microsoft Developer Network..

• Laisant, Charles-Ange (1888), «Sur la numération factorielle, application aux permutations», Bulletin de la Société Mathématique de France (en francés) 16: 176-183..

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), «A permutation representation that knows what “Eulerian” means», Discrete Mathematics and Theoretical Computer Science 4: 101-108, archivado desde el original el 24 de mayo de 2011, consultado el 19 de agosto de 2009..

• Arndt, Jörg (5 de marzo de 2009). Algorithms for Programmers: Ideas and source code (draft). pp. 224-234.

• A Lehmer code calculator

• Factorial
• Combinádico