Sistema numérico combinatorio

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 combinadica , o representación de Macaulay de un número entero , es una correspondencia entre números naturales (se considera que incluye el 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 un mapa de N a las k combinaciones tomadas de N ; Desde este punto de vista, 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 corresponda a cualquier número N no negativo fue observado por primera vez por DH Lehmer . ^[1] De hecho, un algoritmo codicioso encuentra la k -combinación correspondiente a N : tomar c _k máximo con , luego tomar c _{k −1} máximo con , y así sucesivamente. Encontrar el número N , usando la fórmula anterior, a partir de la combinación k ( c _k , ..., c ₂ , c ₁ ) también se conoce como "clasificación", y la operación opuesta (dada por el algoritmo codicioso) como " desclasificación"; las operaciones se conocen con estos nombres en la mayoría de los sistemas de álgebra informática 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 abreviado a "sistema numérico combinatorio" por Knuth , ^[4] quien también da una referencia mucho más antigua; ^[5] el término "combinádico" lo introduce James McCaffrey ^[6] (sin referencia a terminología o trabajos anteriores).

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

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 en el orden 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 .

Combinaciones de pedidos

Una k combinación de un conjunto S es un subconjunto de S con k elementos (distintos). El objetivo principal del sistema numérico combinatorio es proporcionar una representación, cada una mediante un único número, de todas las k posibles combinaciones 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 de por supuesto ser suficientemente grande); en otras palabras , considerar C como un subconjunto de un conjunto más grande al aumentar n no cambiará el número que representa  C. Por lo tanto, para el sistema numérico combinatorio 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 garantizar 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. Entonces, 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 el mismo mayor parte 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 ver las combinaciones como si describieran 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); luego, la comparación de k combinaciones se puede realizar 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 que C ′. Sin embargo, este número no es con el que se quiere representar la combinación k , ya que muchos números binarios tienen un número de bits elevados diferentes de k ; uno quiere encontrar la posición relativa de C en la lista ordenada de (sólo) k -combinaciones .

Lugar de una combinación en el pedido.

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 orden se deduce 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 ci _lo es. Por lo tanto, se pueden agrupar esas k -combinaciones S según los valores posibles 1, 2, ..., k de i , y contar cada grupo por separado. Para un valor dado de i uno debe incluir c _k , ..., c _{i +1} en S , y los i elementos restantes de S deben elegirse entre los ci _enteros no negativos estrictamente menores que c _i ; además, cualquier elección de este tipo dará como resultado k -combinaciones S estrictamente menores que  C . El número de opciones posibles es , que por tanto es el número de combinaciones en el grupo i ; el número total de k -combinaciones estrictamente menor que C entonces es ${\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 hay para cada N  ∈  N exactamente una k -combinación en el índice  N de la lista (suponiendo k  ≥ 1, ya que la lista es entonces infinita), por lo que el argumento anterior demuestra que cada N se puede escribir exactamente de una manera como suma de k coeficientes binomiales de la forma dada.

Encontrar la combinación k para un número dado

La fórmula dada permite encontrar inmediatamente el lugar en el orden lexicográfico de una k -combinación dada. El proceso inverso de encontrar la k -combinación en un lugar dado N requiere algo más de trabajo, pero de todos modos es sencillo. Según la definición del orden 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 deduce 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 elemento más grande es , y tiene c _i  =  i  − 1 para todo i  <  k (para esta combinación, todos los términos de la expresión excepto son cero). Por lo tanto c _k es el mayor número 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 puede 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}}}$

Ejemplo

Supongamos que se quiere determinar la combinación de 5 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 más grande que no excede 72 es 56, para n  = 8. Por lo tanto, c ₅  = 8, y los elementos restantes forman la combinación de 4 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, entonces c ₄  = 6. Continuando de manera similar buscando una combinación de 3 en la posición 16 − 15 = 1 se encuentra c ₃  = 3, que consume la unidad final; esto establece , y los valores restantes c _i serán los máximos con , es decir c _i = i − 1 . Así hemos encontrado la combinación de 5 {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}$

Ejemplo de Lotería Nacional

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}}.}$

Ver también

• Sistema de números factoriales (también llamados factorádicos)
• Sistema de números primordiales
• Sistemas de numeración asimétricos , también, por ejemplo, de combinación con números naturales, ampliamente utilizados en la compresión de datos.

Referencias

1. Matemática Combinatoria Aplicada , Ed. EF Beckenbach (1964), págs. 27-30.
2. Generación de objetos combinatorios elementales, Lucia Moura, U. Ottawa, otoño de 2009
3. "Combinaciones - Manual de referencia de Sage 9.4: combinatoria".
4. Knuth, DE (2005), "Generación de todas las combinaciones y particiones", El arte de la programación informática , vol. 4, fascículo 3, Addison-Wesley, págs. 5-6, ISBN 0-201-85394-9.
5. Pascal, Ernesto (1887), Giornale di Matematiche , vol. 25, págs. 45-49
6. McCaffrey, James (2004), Generación del enésimo elemento lexicográfico de una combinación matemática, Microsoft Developer Network

Otras lecturas

• Huneke, Craig; Swanson, Irena (2006), "Apéndice 5", Cierre integral de ideales, anillos y módulos , Serie de notas de conferencias de la London Mathematical Society, vol. 336, Cambridge, Reino Unido: Cambridge University Press , ISBN 978-0-521-68860-4, señor  2266432
• Caviglia, Giulio (2005), "Un teorema del teorema de restricción del hiperplano de Eakin y Sathaye y 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