Factorádico

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En combinatoria, factorádico (del inglés 'factoradic') es un sistema numérico especialmente construido. El sistema factorádico proporciona un índice lexicografico 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[editar]

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[editar]

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

decimal factorádico
110 1100
210 120100
310 121100
410 220100
510 221100
610 13020100
710 13021100
810 13120100
910 13121100
1010 13220100
1110 13221100
1210 23020100
1310 23021100
1410 23120100
1510 23121100
1610 23220100
1710 23221100
1810 33020100
1910 33021100
2010 33120100
2110 33121100
2210 33220100
2310 33221100

Cómo otro ejemplo, el número mayor que pueda ser representado con seis dígitos sería 554433221100 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 554433221100 es 16050403020100, 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 provado 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 101009080706050403020100 mientras que 11! es 11101009080706050403020100. 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[editar]

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
010 020100 (0,1,2)
110 021100 (0,2,1)
210 120100 (1,0,2)
310 121100 (1,2,0)
410 220100 (2,0,1)
510 221100 (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 46054413020100 (igual a 298210) 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)

Referencias[editar]

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

Enlaces externos[editar]


Véase también[editar]