Factorádico

Factorádico

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

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
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 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:

$\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 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.

Permutaciones

Hay una relación natural entre los enteros 0, ..., n! − 1 (or 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 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)

Referencias

• 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, http://msdn2.microsoft.com/en-us/library/aa302371.aspx 

.

• Laisant, Charles-Ange (1888), "Sur la numération factorielle, application aux permutations" (en French), Bulletin de la Société Mathématique de France 16: 176–183, http://www.numdam.org/item?id=BSMF_1888__16__176_0 

.

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), "A permutation representation that knows what “Eulerian” means", Discrete Mathematics and Theoretical Computer Science 4: 101–108, http://www.dmtcs.org/volumes/abstracts/pdfpapers/dm040203.pdf 

.

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

Enlaces externos

• A Lehmer code calculator

Véase también

• Factorial
• Combinádico

Obtenido de "Factor%C3%A1dico"