Sistema de números factoriales

Sistema numérico en combinatoria.

En combinatoria , el sistema numérico factorial , también llamado factorádico , es un sistema numérico de base mixta adaptado a permutaciones de numeración . También se le llama base factorial , aunque los factoriales no funcionan como base , sino como valor posicional de dígitos. Al convertir un número menor que n ! para la representación factorial, se obtiene una secuencia de n dígitos que se puede convertir a una permutación de n elementos de forma sencilla, ya sea usá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 generales de bases mixtas . ^[2]

Knuth utiliza el término "sistema numérico factorial" , ^[3] mientras que el equivalente francés "numération factorielle" se utilizó por primera vez en 1888. ^[4] El término "factorádico", que es un acrónimo de base factorial y mixta, parece ser de fecha más reciente. ^[5]

Definición

El sistema numérico factorial es un sistema numérico de base mixta : el i -ésimo dígito de 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 ¡El valor debe multiplicarse por ( i  − 1) ! (su valor posicional).

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

En este artículo, una representación de 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 _! representa

= 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, razón por la cual la ecuación comienza con 5! para un número factorádico de 6 dígitos).

Las propiedades generales de los sistemas numéricos de base mixta también se aplican al sistema numérico factorial. Por ejemplo, se puede convertir un número en una representación factorial produciendo 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 sea 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. Leer los restos al revés da 3:4:1:0:1:0 _! .

En principio, este sistema puede ampliarse para representar números racionales , aunque en lugar de la extensión natural de los valores posicionales (−1)!, (−2)!, etc., que no están definidos, la elección simétrica de valores de base n = 0 En su lugar, se puede utilizar , 1, 2, 3, 4, etc. después del punto. Nuevamente, los lugares 0 y 1 pueden omitirse ya que siempre son cero. Los valores posicionales correspondientes son, por 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 (este último a menudo llamado código de Lehmer ) son particularmente elegibles 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 este último la posición en orden lexicográfico (ambos contados desde 0). ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle l}$

Ordenar por una columna que tiene el 0 omitible 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 adyacentes y se pueden usar para ordenarlas en orden colexicográfico. La columna de 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 determinada forman un permutoedro cuando se ordenan según la relación bit a bit. Estos son los recuentos de inversión correcta (también conocidos como códigos de Lehmer) de las permutaciones de cuatro elementos. ${\displaystyle \leq }$

Para otro ejemplo, ¡el mayor número que podría representarse con seis dígitos sería 543210 _! que es igual a 719 en decimal :

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

¡Claramente la siguiente representación de número factorial después de 5:4:3:2:1:0 _! es 1:0:0:0:0:0:0 _! que designa 6! = 720 ₁₀ , el valor posicional del dígito de base 7. Entonces el número anterior, y su expresión resumida arriba, es igual a:

6! − 1.

El sistema numérico 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 se puede representar de más de una forma porque la suma de factoriales consecutivos multiplicada por su índice es siempre el siguiente factorial 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 Serie telescópica ). ${\displaystyle \forall i,i\cdot i!=(i+1-1)\cdot i!=(i+1)!-i!}$

Sin embargo, cuando se utilizan 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 _! , ¡pero no 100000000000 _! = 1:0:0:0:0:0:0:0:0:0:0:0 _! que denota 11! = 39.916.800 ₁₀ . Por lo tanto, usar las letras A – Z para denotar los dígitos 10, 11, 12, ..., 35 como en otra base N hace que el mayor número representable sea 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 numérico factorial en sí no es verdaderamente un sistema numérico en el sentido de proporcionar una representación de todos los números naturales utilizando sólo 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 permutaciones de n elementos en orden lexicográfico , cuando los números enteros se expresan en forma factorádica. Este mapeo se ha denominado código Lehmer (o tabla de inversión). Por ejemplo, con n  = 3 , tal mapeo 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 primer dígito de la 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 los elementos restantes. Si el segundo dígito factorádico es "0", entonces el primer elemento de la lista se selecciona 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", el segundo se selecciona y luego se elimina. El dígito factorádico final es siempre "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 extenso. Digamos que queremos la permutación número 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 dígitos (4,0,6,2,1,3,5) a su vez, indexando un conjunto ordenado de dígitos cada vez menor 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 permutaciones es la concatenación de dos números factorádicos, con dos subíndices "!".

 concatenado par de permutación de factorádicos 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 base única cuyos valores posicionales son de base ⁿ para integrales n positivas y negativas , la base del número factorial no se puede extender a valores posicionales negativos, ya que serían (−1)!, (−2)! y así sucesivamente, y estos valores no están definidos (ver factorial ).

Por lo tanto, una posible extensión es utilizar 1/0!, 1/1!, 1/2!, 1/3!, ..., 1/ n ! etc. en su lugar, posiblemente omitiendo el 1/0! y 1/1! lugares 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 al denominador del número racional representado. Esto se puede probar considerando que existe un factorial para cualquier número entero y por lo tanto el denominador se divide en su propio factorial incluso si no se divide en ningún factorial más pequeño.

Por lo tanto, por necesidad, la expansión factorádica del recíproco de un primo tiene una longitud exacta de ese primo (menos uno si se omite el lugar 1/1!). Otros términos se dan como la secuencia A046021 en el 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 verificar la divisibilidad de 4 en base 10 requiere mirar solo los dos últimos dígitos, verificar la divisibilidad de cualquier número en el sistema numérico factorial requiere mirar solo un número finito de dígitos. Es decir, tiene una regla de divisibilidad para cada número.

También existe un equivalente no terminante para cada número racional similar 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 por 1 y luego completando el número infinito restante de términos con el valor más alto posible para la base de esa posición.

En la siguiente selección de ejemplos, se utilizan espacios para separar los valores posicionales, que de lo contrario 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..._{!}}$

Ver también

• Sistema numérico combinatorio (también llamado combinadica)
• Enteros profinitos , que se pueden representar como secuencias infinitas de dígitos en el sistema numérico factorial
• Algoritmo Steinhaus-Johnson-Trotter , un algoritmo que genera códigos Gray para el sistema numérico factorial

Referencias

1. Knuth, DE (1973), "Volumen 3: Clasificación y búsqueda", El arte de la programación informática , Addison-Wesley, p. 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. 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), Uso de permutaciones en .NET para mejorar la seguridad de los sistemas, Microsoft Developer Network.

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), "Una representación de permutación que sabe lo que significa" eulerian " (PDF) , Matemáticas discretas e informática teórica , 4 : 101–108, archivado desde el original (PDF) el 24 de mayo de 2011 , recuperado el 27 de marzo de 2005.
• Arndt, Jörg (2010). Asuntos computacionales: ideas, algoritmos, código fuente. págs. 232-238.

enlaces externos

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