Sistema de numeración factorial

Sistema de numeración en combinatoria

En combinatoria , el sistema de numeración factorial , también llamado factorádico , es un sistema de numeración de base mixta adaptado a la numeración de permutaciones . También se denomina base factorial , aunque los factoriales no funcionan como base , sino como valor posicional de dígitos. Al convertir un número menor que n ! a representación factorial, se obtiene una secuencia de n dígitos que se puede convertir en una permutación de n elementos de forma sencilla, ya sea utilizándolos como código de Lehmer o como representación de tabla de inversión ^[1] ; en el primer caso, el mapa resultante de números enteros a permutaciones de n elementos los enumera en orden lexicográfico . Georg Cantor estudió los sistemas de base mixta generales . ^[2]

El término "sistema de numeración factorial" es utilizado por Knuth , ^[3] mientras que el equivalente francés "numération factorielle" fue utilizado por primera vez en 1888. ^[4] El término "factorádico", que es una combinación de factorial y radix mixto, parece ser de fecha más reciente. ^[5]

Definición

El sistema de numeración factorial es un sistema de numeración de base mixta : el i -ésimo dígito desde la derecha tiene base  i , lo que significa que el dígito debe ser estrictamente menor que i , y que (teniendo en cuenta las bases de los dígitos menos significativos) su valor debe multiplicarse por ( i  − 1) ! (su valor posicional).

De esto se deduce que el dígito más a la derecha siempre es 0, el segundo puede ser 0 o 1, el tercero 0, 1 o 2, y así sucesivamente (secuencia A124252 en la OEIS ). El sistema de numeración factorial a veces se define omitiendo el lugar 0! porque siempre es cero (secuencia A007623 en la OEIS ).

En este artículo, la representación de un número factorial se marcará con un subíndice "!". Además, algunos ejemplos tendrán dígitos delimitados por dos puntos. Por ejemplo, 3:4:1:0:1:0 _! significa

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

= ((((3×5 + 4)×4 + 1)×3 + 0)×2 + 1)×1 + 0

= 463 ₁₀ .

(El valor posicional es el factorial de uno menos que la posición de la base, por eso la ecuación comienza con 5! para un número factorádico de 6 dígitos).

Las propiedades generales de los sistemas de numeración de base mixta también se aplican al sistema de numeración factorial. Por ejemplo, se puede convertir un número en una representación factorial que produzca dígitos de derecha a izquierda, dividiendo repetidamente el número por la base (1, 2, 3, ...), tomando el resto como dígitos y continuando con el cociente entero , hasta que este cociente se convierta en 0.

Por ejemplo, 463 ₁₀ se puede transformar en una representación factorial mediante estas divisiones sucesivas:

El proceso termina cuando el cociente llega a cero. Al leer los restos al revés se obtiene 3:4:1:0:1:0 _! .

En principio, este sistema puede extenderse para representar números racionales , aunque en lugar de la extensión natural de los valores de posición (−1)!, (−2)!, etc., que no están definidos, se puede utilizar la elección simétrica de los valores de base n = 0, 1, 2, 3, 4, etc. después del punto. Nuevamente, los lugares 0 y 1 pueden omitirse ya que estos siempre son cero. Los valores de posición correspondientes son, por lo tanto, 1/1, 1/1, 1/2, 1/6, 1/24, ..., 1/ n !, etc.

Ejemplos

La siguiente tabla ordenable muestra las 24 permutaciones de cuatro elementos con diferentes vectores relacionados con la inversión . Los recuentos de inversión izquierda y derecha y (este último a menudo llamado código de Lehmer ) son particularmente aptos para ser interpretados como números factoriales. da la posición de la permutación en orden colexicográfico inverso (el orden predeterminado de esta tabla), y el último la posición en orden lexicográfico (ambos contados desde 0). ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle l}$

La ordenación por una columna que tiene el 0 omisible a la derecha hace que los números factoriales de esa columna correspondan a los números índice de la columna inamovible de la izquierda. Las columnas pequeñas son reflejos de las columnas que se encuentran junto a ellas y se pueden usar para ordenarlas en orden colexicográfico. La columna más a la derecha muestra las sumas de dígitos de los números factoriales ( OEIS : A034968 en el orden predeterminado de las tablas).

Los números factoriales de una longitud dada forman un permutoedro cuando se ordenan mediante la relación bit a bit . Estos son los conteos de inversión correctos (también conocidos como códigos de Lehmer) de las permutaciones de cuatro elementos. ${\displaystyle \leq }$

Para dar otro ejemplo, el mayor número que se podría representar con seis dígitos sería 543210 _, que equivale a 719 en decimal :

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

Claramente, la siguiente representación factorial de un número después de 5:4:3:2:1:0 _! es 1:0:0:0:0:0:0:0 _!, que designa 6! = 720 ₁₀ , el valor posicional del dígito de base 7. Por lo tanto, el número anterior y su expresión sumatoria anterior son iguales a:

6! − 1.

El sistema de numeración factorial proporciona una representación única para cada número natural, con la restricción dada sobre los "dígitos" utilizados. Ningún número puede representarse de más de una manera porque la suma de los factoriales consecutivos multiplicada por su índice es siempre el factorial siguiente menos uno:

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

Esto se puede demostrar fácilmente con inducción matemática , o simplemente observando que : los términos subsiguientes se cancelan entre sí, dejando el primer y el último término (ver Series telescópicas ). ${\displaystyle \forall i,i\cdot i!=(i+1-1)\cdot i!=(i+1)!-i!}$

Sin embargo, al utilizar números arábigos para escribir los dígitos (y sin incluir los subíndices como en los ejemplos anteriores), su simple concatenación se vuelve ambigua para los números que tienen un "dígito" mayor que 9. El ejemplo más pequeño es el número 10 × 10! = 36,288,000 ₁₀ , que puede escribirse A0000000000 _! =10:0:0:0:0:0:0:0:0:0:0:0 _! , pero no 100000000000 _! = 1:0:0:0:0:0:0:0:0:0:0:0:0 _! que denota 11! = 39,916,800 ₁₀ . Así, utilizando las letras A–Z para denotar los dígitos 10, 11, 12, ..., 35 como en otras bases N, se obtiene el número más grande representable 36 × 36! − 1. Para números arbitrariamente mayores, uno tiene que elegir una base para representar dígitos individuales, digamos decimal, y proporcionar una marca de separación entre ellos (por ejemplo, subíndice cada dígito por su base, también dada en decimal, como 2 ₄ 0 ₃ 1 ₂ 0 ₁ , este número también se puede escribir como 2:0:1:0 _! ). De hecho, el sistema de numeración factorial en sí mismo no es verdaderamente un sistema numeral en el sentido de proporcionar una representación para todos los números naturales usando solo un alfabeto finito de símbolos.

Permutaciones

Existe una correspondencia natural entre los números enteros 0, 1, ...,  n ! − 1 (o equivalentemente los números con n dígitos en representación factorial) y las permutaciones de n elementos en orden lexicográfico , cuando los números enteros se expresan en forma factorádica. Esta correspondencia se ha denominado código de Lehmer (o tabla de inversión). Por ejemplo, con n  = 3 , dicha correspondencia es

En cada caso, el cálculo de la permutación se realiza utilizando el dígito factorádico más a la izquierda (aquí, 0, 1 o 2) como el primer dígito de permutación y luego eliminándolo de la lista de opciones (0, 1 y 2). Piense en esta nueva lista de opciones como indexada a cero y utilice cada dígito factorádico sucesivo para elegir entre sus elementos restantes. Si el segundo dígito factorádico es "0", entonces se selecciona el primer elemento de la lista para el segundo dígito de permutación y luego se elimina de la lista. De manera similar, si el segundo dígito factorádico es "1", se selecciona el segundo y luego se elimina. El dígito factorádico final siempre es "0" y, dado que la lista ahora contiene solo un elemento, se selecciona como el último dígito de permutación.

El proceso puede resultar más claro con un ejemplo más largo. Digamos que queremos la permutación 2982 de los números del 0 al 6. El número 2982 es 4:0:4:1:0:0:0 _! en factorádico, y ese número selecciona los dígitos (4,0,6,2,1,3,5) uno por uno, indexando un conjunto ordenado decreciente de dígitos y seleccionando cada dígito del conjunto en cada turno:

 4:0:4:1:0:0:0 ! ─ ► (4,0,6,2,1,3,5)factorádico: 4 : 0 : 4 : 1 : 0 : 0 : 0 ! ├─┬─┬─┬─┐ │ ├─┬─┬─┬─┐ ├─┐ │ │ │conjuntos: (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)

Un índice natural para el producto directo de dos grupos de permutación es la concatenación de dos números factorádicos, con dos subíndices "!".

 concatenado par de permutaciones factorádicas decimales 0 10 0:0:0 ! 0:0:0 ! ((0,1,2),(0,1,2)) 1 10 0:0:0 ! 0:1:0 ! ((0,1,2),(0,2,1)) ... 5 10 0:0:0 ! 2:1:0 ! ((0,1,2),(2,1,0)) 6 10 0:1:0 ! 0:0:0 ! ((0,2,1),(0,1,2)) 7 10 0:1:0 ! 0:1:0 ! ((0,2,1),(0,2,1)) ... 22 10 1:1:0 ! 2:0:0 ! ((1,2,0),(2,0,1)) ... 34 10 2:1:0 ! 2:0:0 ! ((2,1,0),(2,0,1)) 35 10 2:1:0 ! 2:1:0 ! ((2,1,0),(2,1,0))

Valores fraccionarios

A diferencia de los sistemas de un solo radio cuyos valores de posición son base ⁿ tanto para la integral positiva como para la negativa n , la base del número factorial no se puede extender a valores de posición negativos ya que estos serían (−1)!, (−2)! y así sucesivamente, y estos valores no están definidos (ver factorial ).

Una posible extensión es, por tanto, utilizar 1/0!, 1/1!, 1/2!, 1/3!, ..., 1/ n ! etc., posiblemente omitiendo los lugares 1/0! y 1/1! que siempre son cero.

Con este método, todos los números racionales tienen una expansión terminal, cuya longitud en 'dígitos' es menor o igual que el denominador del número racional representado. Esto se puede demostrar considerando que existe un factorial para cualquier entero y, por lo tanto, el denominador es divisible por su propio factorial aunque no sea divisible por ningún factorial menor.

Por lo tanto, por necesidad, la expansión factorádica del recíproco de un primo tiene una longitud exactamente igual a la de ese primo (menos uno si se omite el lugar 1/1!). Otros términos se dan como la secuencia A046021 en la OEIS. También se puede demostrar que el último 'dígito' o término de la representación de un racional con denominador primo es igual a la diferencia entre el numerador y el denominador primo.

De manera similar a cómo para comprobar la divisibilidad de 4 en base 10 se requieren solo los dos últimos dígitos, para comprobar la divisibilidad de cualquier número en el sistema de numeración factorial se requiere solo observar un número finito de dígitos. Es decir, tiene una regla de divisibilidad para cada número.

También existe un equivalente no terminal para cada número racional, semejante al hecho de que en decimal 0,24999... = 0,25 = 1/4 y 0,999... = 1 , etc., que se puede crear reduciendo el término final en 1 y luego completando el número infinito restante de términos con el mayor valor posible para el radio de esa posición.

En la siguiente selección de ejemplos, se utilizan espacios para separar los valores posicionales, que de otro modo se representan en decimal. Los números racionales de la izquierda también están en decimal:

• ${\displaystyle 1/2=0.0\ 1_{!}}$
• ${\displaystyle 1/3=0.0\ 0\ 2_{!}}$
• ${\displaystyle 2/3=0.0\ 1\ 1_{!}}$
• ${\displaystyle 1/4=0.0\ 0\ 1\ 2_{!}}$
• ${\displaystyle 3/4=0.0\ 1\ 1\ 2_{!}}$
• ${\displaystyle 1/5=0.0\ 0\ 1\ 0\ 4_{!}}$
• ${\displaystyle 1/6=0.0\ 0\ 1_{!}}$
• ${\displaystyle 5/6=0.0\ 1\ 2_{!}}$
• ${\displaystyle 1/7=0.0\ 0\ 0\ 3\ 2\ 0\ 6_{!}}$
• ${\displaystyle 1/8=0.0\ 0\ 0\ 3_{!}}$
• ${\displaystyle 1/9=0.0\ 0\ 0\ 2\ 3\ 2_{!}}$
• ${\displaystyle 1/10=0.0\ 0\ 0\ 2\ 2_{!}}$
• ${\displaystyle 1/11\ \ =0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_{!}}$
• ${\displaystyle 2/11\ \ =0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_{!}}$
• ${\displaystyle 9/11\ \ =0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_{!}}$
• ${\displaystyle 10/11=0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9\ 1_{!}}$
• ${\displaystyle 1/12\ \ =0.0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 5/12\ \ =0.0\ 0\ 2\ 2_{!}}$
• ${\displaystyle 7/12\ \ =0.0\ 1\ 0\ 2_{!}}$
• ${\displaystyle 11/12=0.0\ 1\ 2\ 2_{!}}$
• ${\displaystyle 1/15=0.0\ 0\ 0\ 1\ 3_{!}}$
• ${\displaystyle 1/16=0.0\ 0\ 0\ 1\ 2\ 3_{!}}$
• ${\displaystyle 1/18=0.0\ 0\ 0\ 1\ 1\ 4_{!}}$
• ${\displaystyle 1/20=0.0\ 0\ 0\ 1\ 1_{!}}$
• ${\displaystyle 1/24=0.0\ 0\ 0\ 1_{!}}$
• ${\displaystyle 1/30=0.0\ 0\ 0\ 0\ 4_{!}}$
• ${\displaystyle 1/36=0.0\ 0\ 0\ 0\ 3\ 2_{!}}$
• ${\displaystyle 1/60=0.0\ 0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 1/72=0.0\ 0\ 0\ 0\ 1\ 4_{!}}$
• ${\displaystyle 1/120=0.0\ 0\ 0\ 0\ 1_{!}}$
• ${\displaystyle 1/144=0.0\ 0\ 0\ 0\ 0\ 5_{!}}$
• ${\displaystyle 1/240=0.0\ 0\ 0\ 0\ 0\ 3_{!}}$
• ${\displaystyle 1/360=0.0\ 0\ 0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 1/720=0.0\ 0\ 0\ 0\ 0\ 1_{!}}$

También hay una pequeña cantidad de constantes que tienen representaciones modeladas con este método:

• ${\displaystyle e=1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1..._{!}}$
• ${\displaystyle e^{-1}=0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E..._{!}}$
• ${\displaystyle \sin(1)=0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E..._{!}}$
• ${\displaystyle \cos(1)=0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0..._{!}}$
• ${\displaystyle \sinh(1)=1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0..._{!}}$
• ${\displaystyle \cosh(1)=1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1..._{!}}$

Véase también

• Sistema de numeración combinatoria (también llamado combinadismo)
• Enteros profinitos , que pueden representarse como secuencias de dígitos infinitos en el sistema de numeración factorial
• Algoritmo de Steinhaus-Johnson-Trotter , un algoritmo que genera códigos Gray para el sistema de numeración factorial

Referencias

1. Knuth, DE (1973), "Volumen 3: Ordenación y búsqueda", El arte de la programación informática , Addison-Wesley, pág. 12, ISBN 0-201-89685-0
2. Cantor, G. (1869), Zeitschrift für Mathematik und Physik , vol. 14.
3. Knuth, DE (1997), "Volumen 2: Algoritmos seminuméricos", El arte de la programación informática (3.ª ed.), Addison-Wesley, pág. 192, ISBN 0-201-89684-2.
4. 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.
5. El término "factorádico" aparentemente se introduce en McCaffrey, James (2003), Using Permutations in .NET for Improved Systems Security, Microsoft Developer Network.

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), "Una representación de permutación que sabe lo que significa "euleriano"" (PDF) , Discrete Mathematics and Theoretical Computer Science , 4 : 101–108, archivado desde el original (PDF) el 24 de mayo de 2011 , consultado el 27 de marzo de 2005.
• Arndt, Jörg (2010). Materias computacionales: ideas, algoritmos, código fuente. pp. 232–238.

Enlaces externos

• Una calculadora de código Lehmer Tenga en cuenta que sus dígitos de permutación comienzan en 1, por lo que mentalmente reduce todos los dígitos de permutación en uno para obtener resultados equivalentes a los de esta página.
• Sistema de numeración factorial