Sistema de numeración combinatoria

En matemáticas , y en particular en combinatoria , el sistema de numeración combinatoria de grado k (para algún entero positivo k ), también conocido como combinads , o la representación Macaulay de un entero , es una correspondencia entre números naturales (que incluyen 0) N y k - combinaciones . Las combinaciones se representan como secuencias estrictamente decrecientes c _k  > ... >  c ₂  >  c ₁  ≥ 0 donde cada c _i corresponde al índice de un elemento elegido en una k -combinación dada. Los números distintos corresponden a k -combinaciones distintas, y las producen en orden lexicográfico . Los números menores que corresponden a todas las k -combinaciones de {0, 1, ..., n − 1 }. La correspondencia no depende del tamaño  n del conjunto del que se toman las k -combinaciones, por lo que puede interpretarse como una función de N a las k -combinaciones tomadas de N ; en esta visión, la correspondencia es una biyección . ${\displaystyle {\tbinom {n}{k}}}$

El número N correspondiente a ( c _k , ..., c ₂ , c ₁ ) viene dado por

${\displaystyle N={\binom {c_{k}}{k}}+\cdots +{\binom {c_{2}}{2}}+{\binom {c_{1}}{1}}}$.

El hecho de que una secuencia única corresponde a cualquier número no negativo N fue observado por primera vez por DH Lehmer . ^[1] De hecho, un algoritmo voraz encuentra la k -combinación correspondiente a N : toma c _k máxima con , luego toma c _{k −1} máxima con , y así sucesivamente. Encontrar el número N , utilizando la fórmula anterior, a partir de la k -combinación ( c _k , ..., c ₂ , c ₁ ) también se conoce como "clasificación", y la operación opuesta (dada por el algoritmo voraz) como "desclasificación"; las operaciones se conocen con estos nombres en la mayoría de los sistemas de álgebra computacional y en matemáticas computacionales . ^{[2] [3]}${\displaystyle {\tbinom {c_{k}}{k}}\leq N}$${\displaystyle {\tbinom {c_{k-1}}{k-1}}\leq N-{\tbinom {c_{k}}{k}}}$

El término originalmente utilizado "representación combinatoria de números enteros" fue acortado a "sistema numérico combinatorio" por Knuth ^[4] , quien también da una referencia mucho más antigua; ^[5] el término "combinádico" es introducido por James McCaffrey ^[6] (sin referencia a terminología o trabajo previo).

A diferencia del sistema de numeración factorial , el sistema de numeración combinatoria de grado k no es un sistema de base mixta : la parte del número N representada por un "dígito" c _i no se obtiene de él simplemente multiplicándolo por un valor posicional. ${\displaystyle {\tbinom {c_{i}}{i}}}$

La principal aplicación del sistema de numeración combinatoria es que permite el cálculo rápido de la k -combinación que se encuentra en una posición dada en el ordenamiento lexicográfico, sin tener que enumerar explícitamente las k -combinaciones que la preceden; esto permite, por ejemplo, la generación aleatoria de k -combinaciones de un conjunto dado. La enumeración de k -combinaciones tiene muchas aplicaciones, entre las que se encuentran las pruebas de software , el muestreo , el control de calidad y el análisis de juegos de lotería .

Una k -combinación de un conjunto S es un subconjunto de S con k elementos (distintos). El objetivo principal del sistema de numeración combinatoria es proporcionar una representación, cada una mediante un único número, de todas las k -combinaciones posibles de un conjunto S de n elementos. Eligiendo, para cualquier n , {0, 1, ..., n  − 1 } como tal conjunto, se puede disponer que la representación de una k -combinación dada C sea independiente del valor de n (aunque n debe ser, por supuesto, suficientemente grande); en otras palabras, considerar C como un subconjunto de un conjunto mayor al aumentar n no cambiará el número que representa  a C . Por lo tanto, para el sistema de numeración combinatoria uno simplemente considera C como una k -combinación del conjunto N de todos los números naturales, sin mencionar explícitamente n . ${\displaystyle {\tbinom {n}{k}}}$

Para asegurar que los números que representan las k -combinaciones de {0, 1, ..., n  − 1 } sean menores que los que representan k -combinaciones no contenidas en {0, 1, ..., n  − 1 }, las k -combinaciones deben ordenarse de tal manera que sus elementos más grandes se comparen primero. El ordenamiento más natural que tiene esta propiedad es el ordenamiento lexicográfico de la secuencia decreciente de sus elementos. Así, comparando las 5-combinaciones C  = {0,3,4,6,9} y C ′ = {0,1,3,7,9}, se tiene que C viene antes de C ′, ya que tienen la misma parte más grande 9, pero la siguiente parte más grande 6 de C es menor que la siguiente parte más grande 7 de C ′; las secuencias comparadas lexicográficamente son (9,6,4,3,0) y (9,7,3,1,0).

Otra forma de describir este orden es considerar las combinaciones como la descripción de los k bits elevados en la representación binaria de un número, de modo que C  = { c ₁ , ..., c _k } describe el número.

${\displaystyle 2^{c_{1}}+2^{c_{2}}+\cdots +2^{c_{k}}}$

(esto asocia números distintos a todos los conjuntos finitos de números naturales); entonces la comparación de k -combinaciones se puede hacer comparando los números binarios asociados. En el ejemplo C y C ′ corresponden a los números 1001011001 ₂  = 601 ₁₀ y 1010001011 ₂  = 651 ₁₀ , lo que nuevamente muestra que C viene antes de C ′. Sin embargo, este número no es el que se quiere representar con la k -combinación, ya que muchos números binarios tienen un número de bits elevados diferente de k ; uno quiere encontrar la posición relativa de C en la lista ordenada de (solo) k -combinaciones .

El número asociado en el sistema de numeración combinatoria de grado k a una k -combinación C es el número de k -combinaciones estrictamente menores que C en el orden dado. Este número se puede calcular a partir de C  = { c _k , ..., c ₂ , c ₁ } con c _k  > ... > c ₂ > c ₁ de la siguiente manera.

De la definición del ordenamiento se sigue que para cada k -combinación S estrictamente menor que  C , hay un índice único  i tal que c _i está ausente de S , mientras que c _k , ..., c _{i +1} están presentes en S , y ningún otro valor mayor que c _i lo está. Por lo tanto, se pueden agrupar esas k -combinaciones S según los posibles valores 1, 2, ..., k de i , y contar cada grupo por separado. Para un valor dado de i se debe incluir c _k , ..., c _{i +1} en S , y los i elementos restantes de S deben elegirse entre los c _i enteros no negativos estrictamente menores que c _i ; además, cualquier elección de este tipo dará como resultado una k -combinación S estrictamente menor que  C . El número de elecciones posibles es , que es por lo tanto el número de combinaciones en el grupo i ; el número total de k -combinaciones estrictamente menores que C es entonces ${\displaystyle {\tbinom {c_{i}}{i}}}$

${\displaystyle {\binom {c_{1}}{1}}+{\binom {c_{2}}{2}}+\cdots +{\binom {c_{k}}{k}},}$

y este es el índice (comenzando desde 0) de C en la lista ordenada de k -combinaciones.

Obviamente, para cada N  ∈  N hay exactamente una k -combinación en el índice  N en la lista (suponiendo que k  ≥ 1, ya que la lista es entonces infinita), por lo que el argumento anterior demuestra que cada N puede escribirse exactamente de una manera como una suma de k coeficientes binomiales de la forma dada.

La fórmula dada permite encontrar el lugar en el ordenamiento lexicográfico de una k -combinación dada inmediatamente. El proceso inverso de encontrar la k -combinación en un lugar dado N requiere algo más de trabajo, pero es sencillo de todos modos. Por la definición del ordenamiento lexicográfico, dos k -combinaciones que difieren en su elemento más grande c _k se ordenarán de acuerdo con la comparación de esos elementos más grandes, de lo que se sigue que todas las combinaciones con un valor fijo de su elemento más grande son contiguas en la lista. Además, la combinación más pequeña con c _k como el elemento más grande es , y tiene c _i  =  i  − 1 para todo i  <  k (para esta combinación todos los términos en la expresión excepto son cero). Por lo tanto, c _k es el número más grande tal que . Si k  > 1 los elementos restantes de la k -combinación forman la k − 1 -combinación correspondiente al número en el sistema numérico combinatorio de grado k − 1 , y por lo tanto se pueden encontrar continuando de la misma manera para y k − 1 en lugar de N y k . ${\displaystyle {\tbinom {c_{k}}{k}}}$${\displaystyle {\tbinom {c_{k}}{k}}}$${\displaystyle {\tbinom {c_{k}}{k}}\leq N}$${\displaystyle N-{\tbinom {c_{k}}{k}}}$${\displaystyle N-{\tbinom {c_{k}}{k}}}$

Supongamos que se quiere determinar la 5-combinación en la posición 72. Los valores sucesivos de para n  = 4, 5, 6, ... son 0, 1, 6, 21, 56, 126, 252, ..., de los cuales el mayor que no excede 72 es 56, para n  = 8. Por lo tanto, c ₅  = 8, y los elementos restantes forman la 4-combinación en la posición 72 − 56 = 16 . Los valores sucesivos de para n  = 3, 4, 5, ... son 0, 1, 5, 15, 35, ..., de los cuales el mayor que no excede 16 es 15, para n  = 6, por lo que c ₄  = 6. Continuando de manera similar para buscar una 3-combinación en la posición 16 − 15 = 1 se encuentra c ₃  = 3, que utiliza la unidad final; esto establece , y los valores restantes c _i serán los máximos con , es decir c _i = i − 1 . Por lo tanto, hemos encontrado la 5-combinación {8, 6, 3, 1, 0 }. ${\displaystyle {\tbinom {n}{5}}}$${\displaystyle {\tbinom {n}{4}}}$${\displaystyle 72={\tbinom {8}{5}}+{\tbinom {6}{4}}+{\tbinom {3}{3}}}$${\displaystyle {\tbinom {c_{i}}{i}}=0}$

Para cada una de las combinaciones de lotería c ₁  <  c ₂  <  c ₃  <  c ₄  <  c ₅  <  c ₆  , existe un número de lista N entre 0 y que se puede encontrar sumando ${\displaystyle {\binom {49}{6}}}$${\displaystyle {\binom {49}{6}}-1}$

${\displaystyle {\binom {49-c_{1}}{6}}+{\binom {49-c_{2}}{5}}+{\binom {49-c_{3}}{4}}+{\binom {49-c_{4}}{3}}+{\binom {49-c_{5}}{2}}+{\binom {49-c_{6}}{1}}.}$

• Sistema de numeración factorial (también llamado factorádico)
• Sistema de numeración primordial
• Sistemas de numeración asimétricos , también por ejemplo de combinación de números naturales, ampliamente utilizados en la compresión de datos.

• Huneke, Craig; Swanson, Irena (2006), "Apéndice 5", Cierre integral de ideales, anillos y módulos , London Mathematical Society Lecture Note Series, vol. 336, Cambridge, Reino Unido: Cambridge University Press , ISBN 978-0-521-68860-4, Sr.  2266432
• Caviglia, Giulio (2005), "Un teorema de Eakin y Sathaye y el teorema de restricción del hiperplano de Green", Álgebra conmutativa: aspectos geométricos, homológicos, combinatorios y computacionales , CRC Press , ISBN 978-1-420-02832-4
• Green, Mark (1989), "Restricciones de series lineales a hiperplanos y algunos resultados de Macaulay y Gotzmann", Curvas algebraicas y geometría proyectiva , Lecture Notes in Mathematics, vol. 1389, Springer , págs. 76–86, doi :10.1007/BFb0085925, ISBN 978-3-540-48188-1