Sistema numérico combinatorio

{0,3,4,6,9} y {0,1,3,7,9}

En matemáticas , y en particular en combinatoria , el sistema numérico combinatorio de grado k (para algún entero positivo k ), también conocido como combinatoria o representación de Macaulay de un entero , es una correspondencia entre los números naturales (que incluyen  el 0) N y las 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        ${\displaystyle {\tbinom {n}{k}}}$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 un mapa de N a las k -combinaciones tomadas de N ; en esta visión la correspondencia es una biyección . 

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 combinación corresponda a un entero no negativo fue observado por Lehmer (1964). ^{[ 1 ]} De hecho, un algoritmo voraz encuentra la k -combinación correspondiente a N : tomar c _k maximal con${\displaystyle {\tbinom {c_{k}}{k}}\leq N}$, luego tome c _{k −1} máximo con${\displaystyle {\tbinom {c_{k-1}}{k-1}}\leq N-{\tbinom {c_{k}}{k}}}$y así sucesivamente. Encontrar el número N , usando 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 ]}

El término "representación combinatoria de enteros" fue abreviado a "sistema numérico combinatorio" por Knuth (2011). ^{[ 4 ]} También hace referencia a Ernesto Pascal (1887). ^{[ 5 ]} El término "combinádico" fue introducido por James McCaffrey. ^{[ 6 ]}

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

La principal aplicación del sistema numérico combinatorio es que permite el cálculo rápido de la k -combinación que se encuentra en una posición determinada del orden lexicográfico, sin necesidad de 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 numerosas aplicaciones, entre las que se incluyen 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 propósito principal del sistema numérico combinatorio es proporcionar una representación, cada elemento mediante un solo número, de todos los elementos.${\displaystyle {\tbinom {n}{k}}}$k -combinaciones posibles de un conjunto S de n elementos. Si elegimos, para cualquier n , {0, 1, ..., n  −  1 } como tal conjunto, se puede disponer que la representación de una k -combinación C dada sea independiente del valor de n (aunque n debe ser 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 numérico combinatorio, simplemente se considera C como una k -combinación del conjunto N de todos los números naturales, sin mencionar explícitamente n . 

Para asegurar que los números que representan las k -combinaciones de {0, 1, ..., n  −  1 } sean menores que los que representan las k -combinaciones que no están contenidas en {0, 1, ..., n  −  1 }, las k -combinaciones deben ordenarse de manera que sus elementos más grandes se comparen primero. El ordenamiento más natural que posee esta propiedad es el ordenamiento lexicográfico de la secuencia decreciente de sus elementos. Así, al comparar las 5-combinaciones C  =  {0,3,4,6,9} y C ′  =  {0,1,3,7,9}, se tiene que C precede a 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 ordenamiento es considerar las combinaciones como descripciones 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 muestra nuevamente que C viene antes que C ′. Sin embargo, este número no es el que se quiere usar para representar la k -combinación, ya que muchos números binarios tienen una cantidad de bits elevados diferente de k ; se quiere encontrar la posición relativa de C en la lista ordenada de (solo) k -combinaciones .

El número asociado en el sistema numérico combinatorio 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 deduce que para cada k -combinación S estrictamente menor que C , existe 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 de 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   ${\displaystyle {\tbinom {c_{i}}{i}}}$, 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 {\binom {c_{1}}{1}}+{\binom {c_{2}}{2}}+\cdots +{\binom {c_{k}}{k}},}$

y este es el índice (que comienza en  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 de la lista (suponiendo que k ≥ 1, ya que la lista es entonces infinita), por lo que el argumento anterior prueba 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 inmediatamente la posición en el orden lexicográfico de una k -combinación dada. El proceso inverso de encontrar la k -combinación en una posición N dada requiere algo más de trabajo, pero no obstante es sencillo. Por definición del orden lexicográfico, dos k -combinaciones que difieren en su elemento mayor c _k se ordenarán según la comparación de esos elementos mayores, de lo cual se deduce que todas las combinaciones con un valor fijo de su elemento mayor son contiguas en la lista. Además, la combinación más pequeña con c _k como elemento mayor es${\displaystyle {\tbinom {c_{k}}{k}}}$y tiene c _i  = i − 1 para todo i < k (para esta combinación todos los términos en la expresión excepto     ${\displaystyle {\tbinom {c_{k}}{k}}}$son cero). Por lo tanto , c _k es el mayor número tal que${\displaystyle {\tbinom {c_{k}}{k}}\leq N}$. Si k > 1 los elementos restantes de la k -combinación forman la k -combinación 1 correspondiente al número  ${\displaystyle N-{\tbinom {c_{k}}{k}}}$en el sistema numérico combinatorio de grado k − 1 , y por lo tanto se puede encontrar continuando de la misma manera para ${\displaystyle N-{\tbinom {c_{k}}{k}}}$y k − 1 en lugar de N y k .

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

${\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ía)
• Sistema de números primordios
• Sistemas de numeración asimétricos , también conocidos como sistemas de combinación para formar 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, MR 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 , pp. 76–86 , doi : 10.1007/BFb0085925 , ISBN  978-3-540-48188-1