Factorádico
# Factorádico

En combinatoria, factorádico (del inglés 'factoradic') es un sistema numérico especialmente construido. El sistema factorádico proporciona un índice lexicográfico para permutaciones por lo que tiene potencial aplicación en la seguridad informática. La idea del sistema factorádico está muy ligada al código Lehmer. Un artículo de James D. McCaffrey documenta el índice factorádico para permutaciones con ejemplos de código escrito en C#.

El término 'factorádico' es una combinación en inglés de los términos factorial y raíz mixta ('factorial' and 'mixed radix').

## Definición

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!

| raíz: | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| - | - | - | - | - | - | - | - | - |
| valor: | 7! | 6! | 5! | 4! | 3! | 2! | 1! | 0! |
| en decimal: | 5040 | 720 | 120 | 24 | 6 | 2 | 1 | 1 |

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)).

## Ejemplos

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

| decimal | factorádico |
| - | - |
| $1_{10}$ | $1_10_0$ |
| $2_{10}$ | $1_20_10_0$ |
| $3_{10}$ | $1_21_10_0$ |
| $4_{10}$ | $2_20_10_0$ |
| $5_{10}$ | $2_21_10_0$ |
| $6_{10}$ | $1_30_20_10_0$ |
| $7_{10}$ | $1_30_21_10_0$ |
| $8_{10}$ | $1_31_20_10_0$ |
| $9_{10}$ | $1_31_21_10_0$ |
| $10_{10}$ | $1_32_20_10_0$ |
| $11_{10}$ | $1_32_21_10_0$ |
| $12_{10}$ | $2_30_20_10_0$ |
| $13_{10}$ | $2_30_21_10_0$ |
| $14_{10}$ | $2_31_20_10_0$ |
| $15_{10}$ | $2_31_21_10_0$ |
| $16_{10}$ | $2_32_20_10_0$ |
| $17_{10}$ | $2_32_21_10_0$ |
| $18_{10}$ | $3_30_20_10_0$ |
| $19_{10}$ | $3_30_21_10_0$ |
| $20_{10}$ | $3_31_20_10_0$ |
| $21_{10}$ | $3_31_21_10_0$ |
| $22_{10}$ | $3_32_20_10_0$ |
| $23_{10}$ | $3_32_21_10_0$ |

Cómo otro ejemplo, el número mayor que pueda ser representado con seis dígitos sería $5_54_43_32_21_10_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_54_43_32_21_10_0$ es $1_60_50_40_30_20_10_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:

    $\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_{10}0_90_80_70_60_50_40_30_20_10_0$ mientras que 11! es $1_{11}0_{10}0_90_80_70_60_50_40_30_20_10_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.

## Permutaciones

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

| Decimal | Factorádico | Permutación |
| - | - | - |
| $0_{10}$ | $0_20_10_0$ | (0,1,2) |
| $1_{10}$ | $0_21_10_0$ | (0,2,1) |
| $2_{10}$ | $1_20_10_0$ | (1,0,2) |
| $3_{10}$ | $1_21_10_0$ | (1,2,0) |
| $4_{10}$ | $2_20_10_0$ | (2,0,1) |
| $5_{10}$ | $2_21_10_0$ | (2,1,0) |

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_60_54_41_30_20_10_0$ (igual a $2982_{10})$ 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.

