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 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
1₁₀	1₁0₀
2₁₀	1₂0₁0₀
3₁₀	1₂1₁0₀
4₁₀	2₂0₁0₀
5₁₀	2₂1₁0₀
6₁₀	1₃0₂0₁0₀
7₁₀	1₃0₂1₁0₀
8₁₀	1₃1₂0₁0₀
9₁₀	1₃1₂1₁0₀
10₁₀	1₃2₂0₁0₀
11₁₀	1₃2₂1₁0₀
12₁₀	2₃0₂0₁0₀
13₁₀	2₃0₂1₁0₀
14₁₀	2₃1₂0₁0₀
15₁₀	2₃1₂1₁0₀
16₁₀	2₃2₂0₁0₀
17₁₀	2₃2₂1₁0₀
18₁₀	3₃0₂0₁0₀
19₁₀	3₃0₂1₁0₀
20₁₀	3₃1₂0₁0₀
21₁₀	3₃1₂1₁0₀
22₁₀	3₃2₂0₁0₀
23₁₀	3₃2₂1₁0₀

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

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
0₁₀	0₂0₁0₀	(0,1,2)
1₁₀	0₂1₁0₀	(0,2,1)
2₁₀	1₂0₁0₀	(1,0,2)
3₁₀	1₂1₁0₀	(1,2,0)
4₁₀	2₂0₁0₀	(2,0,1)
5₁₀	2₂1₁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₆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.

                                 4₆0₅4₄1₃0₂0₁0₀ → (4,0,6,2,1,3,5)
Factorádico:  4₆         0₅                       4₄       1₃         0₂         0₁       0₀
             |          |                        |        |          |          |        |
    (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 ..

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.

Enlaces externos editar

A Lehmer code calculator

Véase también editar

Datos: Q995700
Multimedia: Factorial number system / Q995700