Posibles combinaciones. Elementos de combinatoria
Una combinación es una selección desordenada de elementos de un conjunto finito con un número fijo y sin repeticiones de elementos. Las diferentes combinaciones deben diferir en al menos un elemento y el orden de los elementos no importa. Por ejemplo, del conjunto de todas las vocales de las letras latinas (AEIOU), se pueden hacer 10 combinaciones diferentes de 3 letras, formando los siguientes tercetos desordenados:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Es interesante notar que de las mismas cinco letras también puedes obtener 10 combinaciones diferentes si las combinas 2 letras a la vez, formando los siguientes pares desordenados:
AE, AI, AO, AU, EI, EO, UE, IO, IU, OU.
Sin embargo, si combinas las mismas letras vocales latinas de 4, solo obtendrás las siguientes 5 combinaciones diferentes:
AEIO, AEIU, AIOU, EIOU, AEOU.
En general, para denotar el número de combinaciones de n elementos diferentes de m elementos, se utiliza el siguiente simbolismo funcional, índice o vectorial (Appel):
Independientemente de la forma de notación, el número de combinaciones de n elementos por m elementos se puede determinar utilizando las siguientes fórmulas multiplicativas y factoriales:
Es fácil comprobar que el resultado de los cálculos utilizando estas fórmulas coincide con los resultados del ejemplo comentado anteriormente con combinaciones de vocales en letras latinas. En particular, con n=5 y m=3, los cálculos utilizando estas fórmulas darán el siguiente resultado:
En el caso general, las fórmulas para el número de combinaciones tienen un significado combinatorio y son válidas para cualquier valor entero de n y m, tales que n > m > 0. Si m > n y m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Además, es útil recordar los siguientes números límite de combinaciones, que pueden comprobarse fácilmente mediante sustitución directa en las fórmulas multiplicativas y factoriales:
También cabe señalar que la fórmula multiplicativa sigue siendo válida incluso cuando n es un número real, siempre que m siga siendo un valor entero. Sin embargo, entonces el resultado del cálculo que lo utiliza, aunque mantiene la validez formal, pierde su significado combinatorio.
IDENTIDADES DE COMBINACIONES
El uso práctico de fórmulas multiplicativas y factoriales para determinar el número de combinaciones para valores arbitrarios de n y m resulta de poca productividad debido al crecimiento exponencial de los productos factoriales de su numerador y denominador. Incluso para valores relativamente pequeños de n y m, estos productos a menudo exceden las capacidades de representar números enteros en los sistemas informáticos y de software modernos. Además, sus valores resultan ser significativamente mayores que el valor resultante del número de combinaciones, que puede ser relativamente pequeño. Por ejemplo, el número de combinaciones de n=10 por m=8 elementos es solo 45. Sin embargo, para encontrar este valor usando la fórmula factorial, ¡primero debes calcular valores mucho mayores de 10! en el numerador y 8! en el denominador:
Para eliminar las operaciones que requieren mucho tiempo para procesar grandes cantidades, para determinar el número de combinaciones, puede utilizar varias relaciones de recurrencia, que se derivan directamente de las fórmulas multiplicativas y factoriales. En particular, de la fórmula multiplicativa se deriva la siguiente relación de recurrencia, que nos permite llevar la relación de sus índices más allá del signo del número de combinaciones:
Finalmente, mantener constante el subíndice proporciona la siguiente relación de recurrencia, que se obtiene fácilmente a partir de la fórmula factorial para el número de combinaciones:
Después de transformaciones elementales, las tres relaciones de recurrencia resultantes se pueden representar de las siguientes formas:
Si ahora sumamos los lados izquierdo y derecho de las 2 primeras fórmulas y reducimos el resultado en n, obtenemos una relación de recurrencia importante, que se llama identidad de la suma de números combinados:
La identidad de la suma proporciona una regla de recurrencia básica para determinar eficientemente el número de combinaciones para valores grandes de n y m, ya que permite reemplazar las operaciones de multiplicación en productos factoriales por operaciones de suma más simples y para números más pequeños de combinaciones. En particular, utilizando la identidad de la suma, ahora es fácil determinar el número de combinaciones de n=10 por m=8 elementos, que se analizó anteriormente, realizando la siguiente secuencia de transformaciones recurrentes:
Además, a partir de la identidad de la suma se pueden derivar varias relaciones útiles para calcular sumas finitas, en particular, la fórmula para la suma por subíndice, que tiene la siguiente forma:
Esta relación se obtiene si en la identidad de la suma expandimos la recurrencia a lo largo del término con mayor superíndice mientras su subíndice es mayor que 0. El siguiente ejemplo numérico ilustra este proceso de transformaciones recurrentes:
La fórmula de suma de subíndices se utiliza a menudo para calcular la suma de potencias de números naturales. En particular, suponiendo m=1, utilizando esta fórmula es fácil encontrar la suma de los primeros n números de la serie natural:
Se puede obtener otra versión útil de la fórmula de suma expandiendo la recurrencia de la identidad de la suma a lo largo del término con el superíndice más pequeño. El siguiente ejemplo numérico ilustra esta versión de transformaciones recurrentes:
En el caso general, como resultado de tales transformaciones, se obtiene la suma de los números de combinaciones, ambos índices difieren en uno de los términos vecinos, y la diferencia en los índices permanece constante (en el ejemplo considerado, es también igual a uno). Así, obtenemos la siguiente fórmula de suma para ambos índices de números combinados:
Además de las relaciones de recurrencia y las fórmulas de suma analizadas anteriormente, en el análisis combinatorio se han obtenido muchas otras identidades útiles para números combinados. El más importante entre ellos es identidad de simetría, que se parece a esto:
La validez de la identidad de simetría se puede verificar en el siguiente ejemplo comparando los números de combinaciones de 5 elementos por 2 y por (5 2) = 3:
La identidad de simetría tiene un significado combinatorio obvio, ya que, al determinar el número de opciones para seleccionar m elementos de n elementos, establece simultáneamente el número de combinaciones de los elementos restantes (nm) no seleccionados. La simetría indicada se obtiene inmediatamente reemplazando m por (nm) en la fórmula factorial del número de combinaciones:
Los números y las identidades combinadas se utilizan ampliamente en diversas áreas de las matemáticas computacionales modernas. Sin embargo, sus aplicaciones más populares están relacionadas con el binomio de Newton y el triángulo de Pascal.
TEOREMA DEL BINOMIO
Para realizar diversas transformaciones y cálculos matemáticos, es importante poder representar cualquier potencia natural de un binomio algebraico (binomio) en forma de polinomio. Para potencias pequeñas, el polinomio deseado se puede obtener fácilmente multiplicando binomios directamente. En particular, en el curso de matemáticas elementales se conocen bien las siguientes fórmulas para el cuadrado y el cubo de la suma de dos términos:
En el caso general, para un grado arbitrario n de un binomio, la representación requerida en forma de polinomio la proporciona el teorema del binomio de Newton, que declara verdadera la siguiente igualdad:
Esta igualdad suele denominarse binomio de Newton. El polinomio de su lado derecho está formado por la suma de los productos de n términos X e Y del binomio del lado izquierdo, y los coeficientes delante de ellos se llaman binomios y son iguales al número de combinaciones con índices, que se obtienen de sus poderes. Dada la particular popularidad de la fórmula binomial de Newton en el análisis combinatorio, los términos coeficiente binomial y número de combinaciones generalmente se consideran sinónimos.
Obviamente, las fórmulas de suma al cuadrado y al cubo son casos especiales del teorema del binomio para n=2 y n=3, respectivamente. Para manejar grados más altos (n>3), se debe utilizar la fórmula binomial de Newton. Su aplicación para un binomio de cuarto grado (n=4) se demuestra con el siguiente ejemplo:
Cabe señalar que la fórmula binomial era conocida incluso antes que Newton por los matemáticos medievales del Oriente árabe y de Europa occidental. Por tanto, su nombre generalmente aceptado no es históricamente justo. El mérito de Newton es que generalizó esta fórmula al caso de un exponente real arbitrario r, que puede tomar cualquier valor racional e irracional positivo o negativo. En el caso general, dicha fórmula binomial de Newton tiene una suma infinita en el lado derecho y generalmente se escribe de la siguiente manera:
Por ejemplo, con un valor fraccionario positivo del exponente r=1/2, teniendo en cuenta los valores de los coeficientes binomiales, se obtiene la siguiente expansión:
En el caso general, la fórmula binomial de Newton para cualquier exponente es una versión especial de la fórmula de Maclaurin, que da la expansión de una función arbitraria en una serie de potencias. Newton demostró que para |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>norte) = 0 . Si ahora establecemos Z=X/Y y multiplicamos los lados izquierdo y derecho por Yn, obtenemos una versión de la fórmula binomial de Newton analizada anteriormente.
A pesar de su universalidad, el teorema del binomio conserva su significado combinatorio sólo para potencias enteras no negativas del binomio. En este caso, se puede utilizar para demostrar varias identidades útiles para coeficientes binomiales. En particular, anteriormente se discutieron fórmulas para sumar los números de combinaciones por subíndice y por ambos índices. La identidad sumatoria del superíndice que falta se puede obtener fácilmente a partir de la fórmula binomial de Newton poniendo X = Y = 1 o Z = 1 en ella:
Otra identidad útil establece la igualdad de las sumas de coeficientes binomiales con números pares e impares. Se obtiene inmediatamente de la fórmula binomial de Newton si X = 1 e Y = 1 o Z = 1:
Finalmente, de ambas identidades consideradas obtenemos la identidad de la suma de coeficientes binomiales con números sólo pares o sólo impares:
Con base en las identidades consideradas y la regla recurrente de eliminar índices debajo del signo del número de combinaciones, se pueden obtener una serie de relaciones interesantes. Por ejemplo, si en la fórmula de suma en superíndice reemplazamos n en todas partes con (n1) y eliminamos los índices en cada término, obtenemos la siguiente relación:
Utilizando una técnica similar en la fórmula para la suma de coeficientes binomiales con números pares e impares, es posible demostrar la validez de, por ejemplo, la siguiente relación:
Otra identidad útil le permite calcular fácilmente la suma de los productos de coeficientes binomiales ubicados simétricamente de dos binomios de grados arbitrarios n y k usando la siguiente fórmula de Cauchy:
La validez de esta fórmula se deriva de la necesaria igualdad de coeficientes para cualquier grado m de la variable Z en los lados izquierdo y derecho de la siguiente relación idéntica:
En el caso especial cuando n=k=m, teniendo en cuenta la identidad de simetría, se obtiene una fórmula más popular para la suma de cuadrados de coeficientes binomiales:
Se pueden encontrar muchas otras identidades útiles para coeficientes binomiales en la extensa literatura sobre análisis combinatorio. Sin embargo, su aplicación práctica más famosa está relacionada con el triángulo de Pascal.
TRIÁNGULO DE PASCAL
El triángulo aritmético de Pascal forma una tabla numérica infinita formada por coeficientes binomiales. Sus líneas están ordenadas por potencias de binomios de arriba a abajo. En cada línea, los coeficientes binomiales están ordenados en orden ascendente de los superíndices de los números de combinación correspondientes de izquierda a derecha. El triángulo de Pascal suele escribirse en forma isósceles o rectangular.
Más visual y común es el formato isósceles, donde los coeficientes binomiales, escalonados, forman un triángulo isósceles infinito. Su fragmento inicial para binomios hasta 4º grado (n=4) tiene la siguiente forma:
En general, el triángulo isósceles de Pascal proporciona una regla geométrica conveniente para determinar coeficientes binomiales, que se basa en las identidades de la suma y la simetría de las combinaciones numéricas. En particular, según la identidad de la suma, cualquier coeficiente binomial es la suma de los dos coeficientes de la fila anterior más cercana a él. Según la identidad de simetría, el triángulo isósceles de Pascal es simétrico con respecto a su bisectriz. Así, cada una de sus líneas es un palíndromo numérico de coeficientes binomiales. Las características algebraicas y geométricas indicadas permiten expandir fácilmente el triángulo isósceles de Pascal y encontrar consistentemente los valores de coeficientes binomiales de potencias arbitrarias.
Sin embargo, para estudiar diversas propiedades del triángulo de Pascal, es más conveniente utilizar el formato rectangular formalmente más estricto. En este formato, se especifica mediante una matriz triangular inferior de coeficientes binomiales, donde forman un triángulo rectángulo infinito. El fragmento inicial del triángulo rectángulo de Pascal para binomios hasta el noveno grado (n=9) tiene la siguiente forma:
Geométricamente, una mesa rectangular de este tipo se obtiene deformando horizontalmente el triángulo isósceles de Pascal. Como resultado, las series de números paralelas a los lados laterales del triángulo isósceles de Pascal se convierten en verticales y diagonales del triángulo rectángulo de Pascal, y las líneas horizontales de ambos triángulos coinciden. Al mismo tiempo, las reglas de la suma y la simetría de los coeficientes binomiales siguen siendo válidas, aunque el triángulo rectángulo de Pascal pierde la simetría visual característica de su homólogo isósceles. Para compensar esto, resulta más conveniente analizar formalmente las diversas propiedades numéricas de los coeficientes binomiales para las horizontales, verticales y diagonales del triángulo rectángulo de Pascal.
Al comenzar el análisis de las horizontales del triángulo rectángulo de Pascal, es fácil notar que la suma de los elementos de cualquier fila con el número n es igual a 2n de acuerdo con la fórmula para sumar binomios por superíndice. De esto se deduce que la suma de los elementos sobre cualquiera de las líneas horizontales con el número n es igual a (2 n 1). Este resultado se vuelve bastante obvio si el valor de la suma de los elementos de cada horizontal se escribe en el sistema numérico binario. Por ejemplo, para n=4 esta suma se puede escribir de la siguiente manera:
Aquí hay un par de propiedades más interesantes de las horizontales que también están relacionadas con potencias de dos. Resulta que si el número horizontal es una potencia de dos (n=2 k), entonces todos sus elementos internos (excepto los externos) son números pares. Por el contrario, todos los números de una recta horizontal serán impares si su número es uno menor que una potencia de dos (n=2 k 1). La validez de estas propiedades se puede verificar comprobando la paridad de los coeficientes binomiales internos, por ejemplo, en los horizontales n=4 y n=3 o n=8 y n=7.
Sea ahora el número de fila del triángulo rectángulo de Pascal un número primo p. Entonces todos sus coeficientes binomiales internos son divisibles por p. Esta propiedad es fácil de comprobar para valores pequeños de números de contorno primos. Por ejemplo, todos los coeficientes binomiales internos del quinto horizontal (5, 10 y 5) son obviamente divisibles por 5. Para probar este resultado para cualquier número horizontal primo p, es necesario escribir la fórmula multiplicativa de sus coeficientes binomiales de la siguiente manera:
Dado que p es un número primo y, por tanto, no es divisible por m!, el producto de los factores restantes del numerador de esta fórmula debe ser divisible por m! para garantizar un valor entero del coeficiente binomial. De ello se deduce que la relación entre corchetes es un número natural N y el resultado deseado se vuelve obvio:
Usando este resultado, podemos establecer que los números de todas las líneas horizontales del triángulo de Pascal, cuyos elementos internos son divisibles por un número primo dado p, son potencias de p, es decir, tienen la forma n=p k. En particular, si p=3, entonces el número primo p divide no sólo todos los elementos internos de la fila 3, como se estableció anteriormente, sino, por ejemplo, la novena horizontal (9, 36, 84 y 126). Por otra parte, en el triángulo de Pascal es imposible encontrar una recta horizontal cuyos elementos internos sean todos divisibles por un número compuesto. De lo contrario, el número de dicha línea horizontal debe ser simultáneamente una potencia de los divisores primos del número compuesto por el que se dividen todos sus elementos internos, pero esto es imposible por razones obvias.
Las consideraciones consideradas nos permiten formular el siguiente criterio general para la divisibilidad de los elementos horizontales del triángulo de Pascal. El máximo común divisor (MCD) de todos los elementos internos de cualquier línea horizontal del triángulo de Pascal con número n es igual al número primo p si n=pk o 1 en todos los demás casos:
MCD(Cmn) = ( ) para cualquier 0< m < n .
Como conclusión del análisis de las horizontales, cabe considerar otra propiedad interesante que tienen las series de coeficientes binomiales que las forman. Si los coeficientes binomiales de cualquier recta horizontal de número n se multiplican por potencias sucesivas del número 10, y luego se suman todos estos productos, el resultado es 11 n. La justificación formal de este resultado es la sustitución de los valores X=10 e Y=1 (o Z=1) en la fórmula binomial de Newton. El siguiente ejemplo numérico ilustra el cumplimiento de esta propiedad para n=5:
El análisis de las propiedades de las verticales del triángulo rectángulo de Pascal puede comenzar con el estudio de las características individuales de sus elementos constituyentes. Formalmente, cada m vertical está formada por la siguiente secuencia infinita de coeficientes binomiales con un superíndice constante (m) y un incremento del subíndice:
Evidentemente, cuando m=0 se obtiene una secuencia de unos, y cuando m=1 se forma una serie de números naturales. Cuando m=2 la vertical está formada por números triangulares. Cada número triangular se puede representar en un plano en forma de triángulo equilátero, que está lleno de objetos arbitrarios (núcleos) dispuestos en forma de tablero de ajedrez. En este caso, el valor de cada número triangular T k determina el número de núcleos representativos, y el índice muestra cuántas filas de núcleos se necesitan para representarlo. Por ejemplo, 4 números triangulares iniciales representan las siguientes configuraciones del número correspondiente de símbolos nucleares "@":
Cabe señalar que de manera similar se pueden considerar los números cuadrados S k , que se obtienen elevando al cuadrado números naturales y, en general, números poligonales figurados formados rellenando regularmente polígonos regulares. En particular, los 4 números cuadrados iniciales se pueden representar de la siguiente manera:
Volviendo al análisis de las verticales del triángulo de Pascal, podemos observar que la siguiente vertical en m=3 está llena de números tetraédricos (piramidales). Cada uno de estos números P k especifica el número de núcleos que se pueden organizar en forma de tetraedro, y el índice determina cuántas capas triangulares horizontales de filas de núcleos se requieren para representarlo en un espacio tridimensional. En este caso, todas las capas horizontales deben representarse como números triangulares sucesivos. Los elementos de las siguientes verticales del triángulo de Pascal para m>3 forman series de números hipertetraedales, que no tienen una interpretación geométrica visual en el plano o en el espacio tridimensional, pero formalmente corresponden a análogos multidimensionales de números triangulares y tetraédricos.
Aunque las series numéricas verticales del triángulo de Pascal tienen las características de forma individuales consideradas, para ellas es posible calcular las sumas parciales de los valores de los elementos iniciales de la misma manera, utilizando la fórmula para sumar los números de combinaciones por subíndice. . En el triángulo de Pascal, esta fórmula tiene la siguiente interpretación geométrica. La suma de los valores de los n coeficientes binomiales superiores de cualquier vertical es igual al valor del elemento de la siguiente vertical, que se encuentra una línea debajo. Este resultado también es consistente con la estructura geométrica de los números triangulares, tetraédricos e hipertetraédricos, ya que la representación de cada uno de esos números consta de capas centrales que representan números de orden inferior. En particular, el enésimo número triangular Tn se puede obtener sumando todos los números naturales que representan sus capas lineales:
De manera similar, no es difícil encontrar el número tetraédrico Pn calculando la siguiente suma de los primeros n números triangulares que forman sus capas centrales horizontales:
Además de las horizontales y verticales en el triángulo rectángulo de Pascal, se pueden trazar filas diagonales de elementos, cuyo estudio de propiedades también es de cierto interés. En este caso se suele distinguir entre diagonales descendentes y ascendentes. Las diagonales descendentes son paralelas a la hipotenusa del triángulo rectángulo de Pascal. Están formados por series de coeficientes binomiales con un incremento de ambos índices. Debido a la identidad de simetría, las diagonales descendentes coinciden en los valores de sus elementos con las correspondientes filas verticales del triángulo de Pascal y por tanto repiten todas sus propiedades comentadas anteriormente. La correspondencia indicada se puede rastrear por la coincidencia de los valores de los elementos de la diagonal descendente y la vertical con cualquier número n, si no se tienen en cuenta los ceros verticales:
Las diagonales ascendentes forman series numéricas geométricamente perpendiculares a la hipotenusa del triángulo rectángulo de Pascal. Están llenos de coeficientes binomiales con una disminución del menor y un incremento del superíndice. En particular, las 7 diagonales ascendentes superiores forman la siguiente secuencia numérica sin tener en cuenta los ceros finales:
En general, el número diagonal ascendente n contiene los siguientes coeficientes binomiales, cuya suma de los índices de cada uno de los cuales es igual a (n1):
En virtud de la identidad de la suma para números combinados, cada elemento diagonal es igual a la suma de dos elementos correspondientes en índices de las dos diagonales ascendentes anteriores. Esto permite que cada diagonal ascendente posterior se construya mediante la suma por pares de elementos horizontales adyacentes de las dos diagonales anteriores, expandiendo infinitamente el triángulo de Pascal a lo largo de la diagonal. El siguiente fragmento del triángulo de Pascal ilustra la construcción de una diagonal ascendente número 8 a lo largo de las diagonales numeradas 6 y 7:
Con este método de construcción, la suma de los elementos de cualquier diagonal ascendente, a partir de la 3, será igual a la suma de los elementos de las dos diagonales ascendentes anteriores, y las 2 primeras diagonales constan de un solo elemento, el valor de los cuales es 1. Los resultados de los cálculos correspondientes forman la siguiente serie numérica, según la cual se puede comprobar la validez de la propiedad considerada de las diagonales ascendentes del triángulo rectángulo de Pascal:
Al analizar estos números, se puede ver que de acuerdo con una ley similar se forma la conocida secuencia de números de Fibonacci, donde cada número siguiente es igual a la suma de los dos anteriores, y los dos primeros números son iguales a 1:
Por tanto, podemos sacar la siguiente conclusión importante: las sumas diagonales de los elementos del triángulo de Pascal constituyen la secuencia de Fibonacci. Esta propiedad nos permite establecer otra característica interesante del triángulo de Pascal. Ampliando la fórmula de Fibonacci de forma recursiva, es fácil demostrar que la suma de los primeros n números de Fibonacci es igual a (F n+2 1).
Por tanto, la suma de los coeficientes binomiales que llenan las n diagonales superiores también es igual a (F n+2 1). De ello se deduce que la suma de las primeras n diagonales del triángulo de Pascal es 1 menor que la suma de los coeficientes binomiales que están en su diagonal con el número (n+2).
En conclusión, cabe señalar que las propiedades consideradas de las horizontales, verticales y diagonales del triángulo de Pascal no agotan la enorme variedad de posibilidades que conectan diversos aspectos matemáticos que a primera vista no tienen nada en común. Propiedades tan inusuales nos permiten considerar el triángulo de Pascal como uno de los sistemas numéricos más perfectos, cuyas capacidades no se pueden enumerar y son difíciles de sobreestimar.
El algoritmo para calcular el número de combinaciones utilizando el triángulo de Pascal se presenta a continuación:
Función privada SochTT (ByVal n como entero, ByVal k como entero) Como doble Dim i como entero Dim j como entero Dim TT () como doble ReDim TT (n, k) Para i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Siguiente Para i = 2 To n Para j = 1 A i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Siguiente Siguiente SochTT = TT (n, k) Función final
Si necesita calcular el número de combinaciones muchas veces, entonces puede ser más conveniente construir el triángulo de Pascal una vez y luego recibir datos de la matriz.
Dim TT () como subprivado doble CreateTT () ReDim TT (0, 0) BuildTT 0, 0 Función subprivada final SochTT (ByVal n como entero, ByVal k como entero) como doble si n > Ubound (TT) entonces BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Función final Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal comienza como entero, ByVal termina como entero) Dim i Como entero Dim j Como entero ReDim Preservar TT (fin, fin) Para i = inicio Para finalizar TT (0, i) = 1 TT (i, i) = 1 Siguiente Si final< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Primero debe llamar al procedimiento CreateTT. Luego puede obtener el número de combinaciones utilizando la función SochTT. Cuando ya no necesite el triángulo, llame al procedimiento TerminateTT. En el código anterior, al llamar a la función SochTT, si el triángulo aún no se ha completado al nivel requerido, se completa mediante el procedimiento BuildTT. Luego, la función obtiene el elemento deseado de la matriz TT y lo devuelve.
Dim X () Como entero Dim Counter () Como entero Dim K Como entero Dim N Como entero Public Sub Soch() Dim i Como entero N = CInt(InputBox("Ingrese N")) K = CInt(InputBox("Ingrese K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Siguiente txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Como entero) Dim i Como entero Dim j Como entero Dim n1 Como entero Dim Out() Como entero Dim X1() Como entero Si c = K Entonces ReDim Out(K) X1 = X Para i = 1 a K - 1 n1 = 0 Para j = 1 Para N Si X1(j)<>0 Entonces n1 = n1 + 1 Si n1 = Contador(i) Entonces Out(i) = X1(j) X1(j) = 0 Salir para finalizar si es siguiente txtOut.Text = txtOut.Text & CStr(Out(i)) Siguiente txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
LISTADO DE COMBINACIONES DE NÚMEROS NATURALES
Para resolver muchos problemas prácticos, es necesario enumerar todas las combinaciones de cardinalidad fija que se pueden obtener a partir de los elementos de un conjunto finito dado, y no solo determinar su número. Teniendo en cuenta la posibilidad siempre existente de numeración entera de los elementos de cualquier conjunto finito, en la mayoría de los casos está permitido limitarnos al uso de algoritmos para enumerar combinaciones de números naturales. El más natural y simple de ellos es el algoritmo para enumerar combinaciones de números naturales en orden lexigráfico.
Para describir formalmente este algoritmo, es conveniente suponer que el conjunto principal, cuyas combinaciones de m elementos deben enumerarse, forma números naturales consecutivos del 1 al n. Entonces cualquier combinación de m Como resultado del ordenamiento, el valor en cada posición de dicho vector de combinaciones resulta naturalmente limitado en valor desde arriba y desde abajo de la siguiente manera: El algoritmo lexigráfico genera secuencialmente dichos vectores combinados, comenzando con el vector lexigráficamente más pequeño, donde todas las posiciones contienen los siguientes valores mínimos posibles de elementos iguales a sus índices: Cada vector de combinación sucesivo se forma a partir del actual después de escanear sus elementos de izquierda a derecha para encontrar el elemento más a la derecha que aún no ha alcanzado su valor límite: El valor de dicho elemento debe incrementarse en 1. A cada elemento a su derecha se le debe asignar el valor más pequeño posible, que es 1 mayor que su vecino a la izquierda. Tras estos cambios, el siguiente vector de combinaciones tendrá la siguiente composición elemental: Por lo tanto, el siguiente vector de combinación será lexigráficamente más grande que el anterior, ya que los valores de sus elementos iniciales (j1) son iguales en valor y el valor del elemento en la posición j es 1 mayor que el del anterior. . Se garantiza que la relación especificada de orden lexigráfico creciente se cumplirá en todas las iteraciones del algoritmo. El resultado es una secuencia lexigráfica creciente, que se completa con el vector de combinación lexigráficamente más grande, donde los elementos en todas las posiciones tienen los siguientes valores máximos: El algoritmo lexigráfico considerado se ilustra con el siguiente ejemplo, donde es necesario enumerar en orden lexigráfico creciente las 15 combinaciones de n=6 primeros números naturales por m=4 números, es decir, todos los posibles subconjuntos de 4 elementos del generador principal establezca (1, 2, 3, 4, 5, 6) a partir de 6 elementos. Los resultados del cálculo se presentan en la siguiente tabla: En este ejemplo, los valores más grandes permitidos de números en las posiciones de los vectores de combinación son, respectivamente, 3, 4, 5 y 6. Para facilitar la interpretación de los resultados, en cada vector de combinación, el elemento más a la derecha, que tiene aún no ha alcanzado su valor máximo, está subrayado. Los índices numéricos de vectores combinados determinan sus números en orden lexigráfico. En el caso general, el número lexigráfico N de cualquier combinación de n elementos por m se puede calcular mediante la siguiente fórmula, donde, por razones estéticas, se utiliza el simbolismo de Appel para denotar los números de combinaciones: En particular, los siguientes cálculos utilizando esta fórmula para el número de combinación (1, 3, 4, 6) de n=6 elementos de m=4 en orden lexigráfico darán el resultado N=8, que corresponde al ejemplo discutido anteriormente: En el caso general, utilizando la identidad para la suma de los números de combinaciones para ambos índices, es posible demostrar que el número de la combinación lexigráficamente más pequeña (1, ... i, ... m) cuando se calcula usando este la fórmula siempre será igual a 1: También es obvio que el número de la combinación lexigráficamente más grande (m,… nm+i,… n) cuando se calcula usando esta fórmula será igual al número de combinaciones de n elementos por m: La fórmula para calcular números de combinación lexigráfica se puede utilizar para resolver el problema inverso, donde es necesario determinar el vector de combinación por su número en orden lexigráfico. Para resolver un problema tan inverso, se debe escribir en forma de ecuación, donde todos los valores desconocidos de los elementos del vector de la combinación deseada (C 1, ... C i, ... C m ) se concentran en el número de combinaciones de su lado derecho, y la diferencia conocida L del número de combinaciones se escribe en el lado izquierdo de n elementos cada m y el número de la combinación requerida N: La solución a esta ecuación la proporciona el siguiente algoritmo "codicioso", durante cuyas iteraciones se seleccionan secuencialmente los valores de los elementos del vector de la combinación deseada. En la iteración inicial, se selecciona el valor mínimo posible (dentro de sus limitaciones) de C 1, en el cual el primer término del lado derecho tendrá un valor máximo que no excederá L: Ahora el lado izquierdo de L debe reducirse por el primer número de combinaciones en el lado derecho con el valor seleccionado de C 1, y de manera similar determinar el valor de C 2 en la segunda iteración: De manera similar, todas las iteraciones posteriores deben realizarse para seleccionar los valores de todos los demás elementos C i de la combinación deseada, hasta el último elemento C m: Por razones obvias, el valor del último elemento C m se puede determinar basándose en la igualdad de su número de combinaciones con el valor residual del lado izquierdo de L: Cabe señalar que el valor del último elemento de la combinación C m se puede encontrar de forma aún más sencilla, sin enumerar sus posibles valores: La implementación de iteraciones del algoritmo considerado se ilustra con el siguiente ejemplo, donde es necesario determinar combinaciones con el número N=8 en orden lexigráfico, si n=6 y m=4: La capacidad algorítmica para determinar una combinación mediante un número determinado en orden lexigráfico se puede utilizar en varias direcciones. En particular, al enumerar combinaciones en orden lexigráfico, es necesario garantizar el retorno a cualquier combinación obtenida anteriormente; basta con saber solo su número. Además, es posible generar combinaciones en cualquier orden, que está regulado por una secuencia dada arbitrariamente de sus números lexigráficos. Ahora presentamos un algoritmo para generar combinaciones en orden lexicográfico: 2 para i:= 1 a k hacer A[i] := i; 5 comenzar a escribir (A,…, A[k]); 6 si A[k] = n entonces p:= p 1 en caso contrario p:= k; 8 para i:= k hasta p hacer A[i] := A[p] + i p + 1 COMBINACIONES CON ELEMENTOS REPETIDOS A diferencia de una combinación clásica, donde todos los elementos son diferentes, una combinación con repeticiones forma una selección desordenada de elementos de un conjunto finito, donde cualquier elemento puede aparecer con indefinida frecuencia y no necesariamente está presente en una sola copia. En este caso, el número de repeticiones de elementos suele estar limitado únicamente por la longitud de la combinación, y las combinaciones que difieren en al menos un elemento se consideran diferentes. Por ejemplo, eligiendo 4 números opcionalmente diferentes del conjunto 1, 2 y 3, puedes crear las siguientes 15 combinaciones con repeticiones: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
En general, se pueden formar combinaciones con repeticiones seleccionando n elementos de tipos arbitrarios. Sin embargo, siempre se pueden asociar a números naturales consecutivos del 1 al n. Luego, cualquier combinación de m números opcionalmente diferentes en este rango se puede escribir en forma vectorial, organizándolos en orden no decreciente de izquierda a derecha: Naturalmente, con esta forma de notación, cualquier elemento vecino puede ser igual debido a la posibilidad de repeticiones ilimitadas. Sin embargo, cada vector de combinación con repeticiones de n elementos por m puede asociarse con un vector de combinación de (n+m−1) elementos por m, que se construye de la siguiente manera: Está claro que para cualquier valor de los elementos del vector f, se garantiza que los elementos del vector C serán diferentes y estrictamente ordenados en orden creciente de sus valores en el rango de 1 a (n+m1) : La presencia de una correspondencia uno a uno entre los elementos de los vectores de combinación f y C nos permite proponer el siguiente método simple para enumerar sistemáticamente combinaciones con repeticiones de n elementos por m. Sólo es necesario enumerar, por ejemplo, en orden lexigráfico, todas las C combinaciones de (n+m1) elementos de m, transformando secuencialmente los elementos de cada una de ellas en los correspondientes elementos de combinaciones con repeticiones f utilizando la siguiente fórmula: Como resultado, se forma una secuencia de vectores de combinaciones con repeticiones de elementos, que se organizan en el orden generado al enumerar las combinaciones correspondientes sin repeticiones de elementos. En particular, para obtener la secuencia anterior de combinaciones de 3 dígitos 1, 2 y 3 con repeticiones de 4 dígitos, es necesario enumerar en orden lexigráfico todas las combinaciones sin repeticiones de 6 dígitos 1,2,3,4, 5. y 6 son 4 dígitos cada uno, convirtiéndolos como se indica. El siguiente ejemplo muestra dicha conversión de la combinación (1,3,4,6) con el número lexicográfico 8: La correspondencia uno a uno considerada entre combinaciones con y sin repeticiones de elementos significa que sus conjuntos son igualmente poderosos. Por tanto, en el caso general, el número de combinaciones con repeticiones de n elementos por m es igual al número de combinaciones sin repeticiones de (n+m1) elementos por m. Usando el mismo simbolismo para denotar los números de combinaciones con repeticiones f y sin repeticiones C, esta igualdad se puede escribir de la siguiente manera: Es fácil comprobar que para el ejemplo considerado anteriormente, donde n=3 y m=4, el número de combinaciones de repetición será igual a 15, lo que coincide con el resultado de su listado directo: Cabe señalar que, a diferencia de la versión clásica, los valores de los parámetros de combinación con repeticiones n y m no están directamente relacionados entre sí, por lo tanto f(n,m)>0 para cualquier combinación de sus valores positivos. Las condiciones de contorno correspondientes se determinan a partir de la igualdad entre los valores de (n+m1) y (n1) o (n+m1) y m: También debería ser bastante obvio que si m es igual a 1, entonces no son posibles repeticiones de elementos y, por lo tanto, para cualquier valor positivo de n>0 la siguiente igualdad será cierta: Además, para números de combinaciones con repeticiones para cualquier valor positivo de n y m, es válida la siguiente relación de recurrencia, que es similar a la identidad de la suma para números de combinaciones sin repeticiones de elementos: En realidad, se convierte en la identidad de suma indicada al sustituir formalmente los números correspondientes de combinaciones sin repeticiones en sus lados izquierdo y derecho: La relación de recurrencia considerada se puede utilizar para determinar efectivamente el número de combinaciones con repeticiones, cuando es importante eliminar las operaciones que requieren mucha mano de obra para calcular productos factoriales y reemplazarlas con operaciones de suma más simples. En este caso, para calcular el valor de f(n,m), sólo es necesario aplicar esta relación de recurrencia hasta obtener la suma de términos de la forma f(1,m) y f(i,1), donde i toma valores en el rango de n a 1. Por definición de cantidad, dichos términos son iguales a 1 e i, respectivamente. El siguiente ejemplo ilustra el uso de esta técnica de transformación para el caso de n=3 y m=4: LISTADO DE COMBINACIONES BINARIAS Al implementar combinaciones en hardware o programación en lenguaje ensamblador, es importante poder procesar registros de combinación en formato binario. En este caso, cualquier combinación de n elementos de m debe especificarse en forma de un número binario de n bits (B n,...B j,...B 1), donde m dígitos unitarios indican los elementos de la combinación, y los dígitos restantes (nm) tienen valores cero. Obviamente, con esta forma de notación, diferentes combinaciones deben diferir en la disposición de los dígitos de unos, y sólo hay C(n,m) formas de organizar m unos o (nm) ceros en un conjunto binario de n bits. Por ejemplo, la siguiente tabla enumera las 6 combinaciones binarias de este tipo, que proporcionan números binarios de 4 bits para todas las combinaciones de 4 elementos de un conjunto arbitrario (E 1, E 2, E 3, E 4) por 2: En el caso general, la tarea de enumerar tales combinaciones binarias se reduce a una búsqueda sistemática de todos los conjuntos binarios de n bits con diferentes disposiciones de m uno y (nm) cero bits. En la forma más simple, dicha búsqueda se implementa mediante varios métodos de transposición de bits adyacentes con un desplazamiento (algoritmos de desplazamiento transpositivo). Estos son algoritmos iterativos y sus nombres reflejan la naturaleza de las operaciones realizadas en cada paso. Los procedimientos iterativos de los algoritmos de desplazamiento transpositivo forman secuencias de combinaciones binarias que comienzan con un conjunto binario, donde todos los unos se concentran en los dígitos de orden inferior (a la derecha) y terminan cuando todos los unos están en los dígitos de orden superior ( a la izquierda): Si bien coinciden en combinaciones iniciales y finales, estas secuencias difieren en el orden en que se enumeran los conjuntos binarios intermedios. Sin embargo, en todos los casos, cada combinación binaria posterior se forma a partir de la anterior como resultado de realizar las correspondientes operaciones de transposición y desplazamiento. Al mismo tiempo, varios algoritmos de desplazamiento transpositivo se diferencian en la forma en que seleccionan un par de bits para la transposición y un grupo de bits para el desplazamiento. Esta especificidad se analiza a continuación para los algoritmos de transposición con desplazamiento hacia la izquierda y hacia la derecha. En el algoritmo de transposición con desplazamiento a la izquierda, en cada paso la siguiente combinación binaria se obtiene a partir de la actual reemplazando el par de dígitos más a la izquierda 01 por 10 (transposición) y desplazando el grupo de dígitos unitarios principales, si los hay, cerca del par 10 obtenido después de la transposición (desplazamiento). Si en este caso no hay unidades en los dígitos iniciales de la combinación binaria actual, entonces el cambio no se realiza, incluso cuando la unidad principal se obtiene después de la transposición en este paso. El desplazamiento tampoco se realiza cuando no existen ceros en los bits más significativos antes del par 10 obtenido tras la transposición. Las acciones consideradas se ilustran con el siguiente ejemplo de realización de dos iteraciones sucesivas de este algoritmo, donde en una iteración (15) solo se realiza la transposición (T") y en la otra iteración (16) la transposición se complementa con un desplazamiento ( T"+S"): En el algoritmo de transposición de desplazamiento a la derecha, se realizan pasos conceptualmente similares en cada paso. Sólo la transposición garantiza que los bits más a la derecha de 01 se reemplacen por 10 (en lugar de los más a la izquierda), y luego todos los que están a la derecha se desplacen a los bits menos significativos. Como antes, el desplazamiento se realiza sólo si hay unidades que se pueden desplazar hacia la derecha. Las acciones consideradas se ilustran con el siguiente ejemplo de realización de dos iteraciones sucesivas de este algoritmo, donde en una iteración (3) solo se realiza la transposición (T") y en la otra iteración (4) la transposición se complementa con un desplazamiento ( T"+S"): Cabe señalar que las iteraciones de ambos algoritmos se pueden escribir en forma aditiva si las combinaciones binarias se interpretan como números enteros en el sistema numérico de base 2. En particular, para el algoritmo de transposición con desplazamiento a la derecha, cada siguiente combinación binaria (B" n ,…B" j , …B" 1), siempre se puede obtener a partir de la combinación actual (B n,…B j,…B 1) realizando las operaciones de suma de números enteros utilizando la siguiente fórmula aditiva: En esta fórmula aditiva, los exponentes de las potencias de dos f y t denotan, respectivamente, el número de dígitos cero de orden inferior de la combinación binaria actual y el número de unos en una fila a la izquierda de ellos. Por ejemplo, para la cuarta combinación binaria (001110) de n=6 dígitos f =1 y t =3. Por lo tanto, calcular la siguiente combinación binaria usando la fórmula aditiva en la iteración 5 dará el siguiente resultado, equivalente a realizar las operaciones de transposición y desplazamiento: Para un análisis comparativo de los algoritmos de transposición considerados con desplazamientos hacia la izquierda y hacia la derecha, es recomendable comparar las secuencias de combinaciones binarias que generan en sus iteraciones. La siguiente tabla muestra dos de estas secuencias de combinaciones binarias de 4 elementos de 2, que se obtienen mediante los algoritmos de desplazamiento hacia la izquierda (TSL) y hacia la derecha (TSR), respectivamente: Comparando estas 2 secuencias, puedes ver que son espejo inverso. Esto significa que dos combinaciones binarias cualesquiera que se encuentran en ellas a la misma distancia de los extremos mutuamente opuestos de sus secuencias son una imagen especular entre sí, es decir, coinciden cuando se invierte la indexación de los bits en cualquiera de ellas. Por ejemplo, el segundo patrón binario desde el principio de la secuencia TSL (0101) es una imagen especular del patrón binario (1010) que está en segundo lugar desde el final de la secuencia TSR. En general, cualquier combinación binaria con el número i de una secuencia es una imagen especular de una combinación binaria con el número (ni+1) de otra secuencia. Esta relación entre estas secuencias es consecuencia de la naturaleza simétrica de las operaciones de transposición y desplazamiento en los dos algoritmos considerados para enumerar combinaciones binarias. Cabe señalar que el formato binario también se puede utilizar para registrar combinaciones con repeticiones de elementos. Para ello, es necesario establecer una correspondencia uno a uno entre combinaciones con repeticiones y combinaciones binarias, que se construyen de la siguiente manera. Sea una combinación arbitraria con repeticiones, que se obtiene eligiendo m elementos opcionalmente diferentes de los n elementos del grupo electrógeno. Para establecer la coincidencia deseada, primero debe agregar todos los elementos del conjunto formado (cat) a la combinación y luego ordenar la concatenación resultante (sort) de modo que todos los elementos idénticos estén uno al lado del otro. El resultado es una secuencia de (n+m) elementos, donde hay n grupos de elementos idénticos. Habrá un total de (n+m1) espacios entre elementos, entre los cuales habrá (n1) espacios entre grupos de elementos idénticos y m espacios entre elementos dentro de grupos. Para mayor claridad, puede colocar los símbolos “|” en los espacios indicados. y correspondientemente. Si ahora hacemos coincidir 1 con los espacios entre grupos (|) y 0 con todos los demás espacios (), obtenemos una combinación binaria. Está formado por un conjunto binario de (n+m1) bits, donde (n1) son unos ym cero bits, cuya ubicación corresponde únicamente a la combinación original con repeticiones de los elementos n a m. La técnica de transformación considerada se ilustra con el siguiente ejemplo de construcción de una combinación binaria (1001101) utilizando una combinación con repeticiones (BBD), cuyos elementos se seleccionan del conjunto generador de las primeras cinco letras latinas: En general, el número de dichos conjuntos binarios determina el número de formas de organizar (n1) unos (o m ceros) en (n+m1) dígitos binarios. Este valor es obviamente igual al número de combinaciones de (n+m1) por (n1) o por m, es decir, C(n+m1,n1) o C(n+m1,m), que es igual al número de combinaciones con repeticiones f( n,m) de n elementos, m cada uno. Por tanto, al tener una correspondencia uno a uno entre combinaciones con repeticiones y combinaciones binarias, es legítimo reducir la enumeración de combinaciones con repeticiones a la enumeración de combinaciones binarias, por ejemplo, utilizando algoritmos de transposición con desplazamiento hacia la izquierda o hacia la derecha. Después de esto, solo necesita restaurar las combinaciones requeridas con repeticiones usando las combinaciones binarias resultantes. Esto siempre se puede hacer utilizando la siguiente técnica de recuperación. Dejemos que el conjunto principal, a partir de cuyos elementos se formen combinaciones con repeticiones de m elementos no necesariamente diferentes, se ordene de forma arbitraria de modo que cada uno de sus elementos tenga un cierto número de serie de 1 a n. Implementemos también la enumeración de combinaciones binarias de (n+m1) dígitos binarios, donde (n1) unos y m cero dígitos. Cada combinación binaria resultante se puede complementar a la izquierda con un dígito unitario ficticio, y todos los dígitos unitarios se pueden numerar de izquierda a derecha con números enteros del 1 al n. Entonces, el número de ceros seguidos después de cada i-ésima unidad de la combinación binaria será igual al número de instancias del i-ésimo elemento del conjunto principal en la combinación correspondiente con repeticiones. La técnica considerada se ilustra con el siguiente ejemplo, donde, utilizando una combinación binaria (1001101), se restaura una combinación con repeticiones de BBD, cuyos elementos se seleccionan del conjunto generador de las primeras cinco letras latinas, escritas en orden alfabético. , y el trazo superior indica elementos que están ausentes en esta combinación: Al realizar acciones similares en las condiciones de este ejemplo, puede enumerar las 35 combinaciones binarias que forman conjuntos binarios de 7 bits, donde hay 4 unos y 3 ceros, y restaurar las combinaciones correspondientes con repeticiones de 5 elementos de 3. Se acercaba el invierno y Khoma y Suslik decidieron abastecerse de guisantes. Corrieron todo el día hasta el granero y cargaron con varias cápsulas: Khoma, cuatro, y Suslik, dos. Al anochecer contaron todas las vainas que habían cosechado y se preguntaron cómo dividir ahora los guisantes. Khoma argumentó que si arrastraba el doble de guisantes a la vez que Suslik, entonces debería obtener el doble de guisantes. Suslik objetó razonablemente que, en primer lugar, la velocidad de Khoma es notablemente menor que la de Suslik y, en segundo lugar, quién sabe, tal vez Khoma solo se escapó una o dos veces, y el resto del tiempo estuvo inactivo... Ayuda a tus amigos a comprender al menos un poco esta difícil situación. Determine todas las opciones posibles sobre cuántas vainas trajo Suslik y cuántas Khoma. En la primera línea hay un número par natural M: el número de cápsulas robadas, 2 ≤ M ≤ 1000. Todas las combinaciones posibles de las cantidades de vainas que trajeron Suslik y Khoma, una combinación por línea. Cada combinación representa dos números enteros no negativos separados por un espacio: el primer número es el número de vainas traídas por Suslik, el segundo, por Khoma. Ordena las combinaciones en orden descendente del primer número. #incluir usando el espacio de nombres estándar; int principal()( int a, b = 0; cin >> a ; mientras (a >= 0 ) ( corte<<
a
<<
" "
<<
b
<<
"\n"
;
un -= 4 ; segundo += 4 ; devolver 0; Sea a el número de vainas traídas por Homa y b sea el número de vainas traídas por Suslik. Dado que, según las condiciones del problema, Khoma llevaba sólo cuatro pods, consideraremos a = a-4 y b = b + 4 para enumerar así todas las combinaciones posibles del número de pods traídos por Suslik y Khoma. Usemos también un bucle. mientras, que repetirá la acción descrita anteriormente hasta \geq 0. En la respuesta imprimimos todas las combinaciones posibles de los números de pods traídos por amigos, uno por línea, ordenados en orden descendente del primer número. Ejemplo // Combinaciones de 3 de 52 para (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Aquí veremos un problema más complejo, cuya solución no encontré en RuNet (sin embargo, daré un enlace, pero esa fórmula es claramente incorrecta), basada en la combinación misma (en este caso, un conjunto de tres números) encuentra su índice. Supongamos, para mayor precisión, después de ordenar i1 = 3, i2 = 7, i3 = 12. Un algoritmo de generación típico es que generamos combinaciones de 2 de 52, y para cada combinación en un bucle anidado generamos combinaciones de 3 de 50 y comprobamos que los índices (i3, i4, i5) en la combinación anidada no no coincidir con los índices (i1, i2) en combinación externa: código C ++ // COMBINACIÓN EXTERNA para (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
código C ++ si (i3 >= i1) --i3; si (i3 >= i2) --i2; // similar para i4, i5 Código de ejemplo para dividir el índice por 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Índice de la combinación de 2 de 52, multiplicado por C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // “Re-indexar” el grupo interno para que la numeración sea 0...49 si (i3 > = i1) --i3; si (i3 >= i2) --i3; si (i4 >= i1) --i4; si (i4 >= i2) --i4; si (i5 >= i1) --i5 ; if (i5 >= i2) --i5; // Ahora suma el índice de la combinación por 3 // 0: // SUMA para n = 0 por i3-1 COMBINACIONES (2, 49-n) // = SUMA para m = 50-i3 por 49 (m * (m-1) / 2) desplazamiento += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // SUMA para n = i3+1 a i4-1 COMBINACIONES (1, 49-n) desplazamiento += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUMA para n = i4+1 a i5-1 (1) desplazamiento + = (i5 - i4 - 1); compensación de retorno; ) En general, dividiría los algoritmos combinatorios en las siguientes clases: Número de combinaciones Combinación de norte Por k llamado un conjunto k elementos seleccionados de los datos norte elementos. Los conjuntos que difieren sólo en el orden de los elementos (pero no en la composición) se consideran idénticos; es por eso que las combinaciones difieren de las ubicaciones. Número de combinaciones de norte Por k
igual al coeficiente binomial Por un valor fijo norte función generadora de números de combinaciones con repeticiones de norte Por k es: La función generadora bidimensional de números de combinaciones con repeticiones es: Fundación Wikimedia. 2010. 70 setenta 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Factorización: 2×5×7 Notación romana: LXX Binario: 100 0110 ... Wikipedia Número de luz, un número condicional que expresa de forma única el exterior. condiciones durante la fotografía (generalmente el brillo del sujeto y la fotosensibilidad del material fotográfico utilizado). Cualquier valor de E. h. se puede seleccionar varias veces. combinaciones número de apertura... ... Gran Diccionario Politécnico Enciclopédico Una forma de número que distingue dos objetos tanto en relación con un solo objeto como en relación con muchos objetos. Esta forma no existe en el ruso moderno, pero quedan restos de su influencia. Entonces, combinaciones de dos tablas (cf. plural... ... Diccionario de términos lingüísticos. Matemáticas combinatorias, combinatoria, una rama de las matemáticas dedicada a resolver problemas de elección y disposición de elementos de un conjunto determinado, generalmente finito, de acuerdo con reglas dadas. Cada una de estas reglas determina el método de construcción... ... Enciclopedia Matemática En combinatoria, una combinación de por es un conjunto de elementos seleccionados de un conjunto dado que contiene diferentes elementos. Los conjuntos que difieren sólo en el orden de los elementos (pero no en la composición) se consideran idénticos, estas combinaciones... ... Wikipedia Se dedica al estudio de acontecimientos cuya ocurrencia no se conoce con certeza. Nos permite juzgar la razonabilidad de esperar la ocurrencia de algunos eventos en comparación con otros, aunque asignar valores numéricos a las probabilidades de los eventos muchas veces es innecesario... ... Enciclopedia de Collier 1) lo mismo que el análisis combinatorio matemático. 2) Una sección de matemáticas elementales asociada al estudio del número de combinaciones, sujetas a ciertas condiciones, que pueden componerse a partir de un conjunto finito dado de objetos... ... Gran enciclopedia soviética - (paradojas griegas inesperadas, extrañas) en un sentido amplio: una afirmación que difiere marcadamente de la opinión establecida y generalmente aceptada, una negación de lo que parece "incondicionalmente correcto"; en un sentido más estricto, dos afirmaciones opuestas, por... ... Enciclopedia filosófica - (o el principio de inclusiones y exclusiones) una fórmula combinatoria que permite determinar la cardinalidad de la unión de un número finito de conjuntos finitos, que en el caso general pueden cruzarse entre sí ... Wikipedia Teoría matemática que se ocupa de determinar el número de formas diferentes de distribuir objetos dados en un orden conocido; Es especialmente importante en la teoría de ecuaciones y teoría de la probabilidad. Las tareas más simples de este tipo son... ... Diccionario enciclopédico F.A. Brockhaus y I.A. EfrónDatos de entrada
Producción
Pruebas
Datos de entrada
Producción
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Código de programa
La solución del problema
Índice combinado
Cada combinación, permutación, disposición y otros objetos combinatorios se pueden asociar con un índice: este es el número en el que aparece al iterar a través de este algoritmo.
Hay una opción para buscar "de frente". Encendemos el contador de combinaciones, tomamos el algoritmo anterior y probamos todo hasta llegar a la opción deseada. Esta opción tiene una complejidad temporal muy elevada, por lo que descartaremos esta opción.
Supongamos que la entrada contiene los números i1, i2, i3. En primer lugar, debemos organizarlos en orden ascendente (tenga en cuenta que el algoritmo de generación en sí, mencionado anteriormente, siempre los produce en forma ordenada, aunque el concepto mismo de "combinación" implica un orden arbitrario).
Esto significa que “repasamos” todas las combinaciones donde i1 era igual a 0, 1 y 2.
Para i1 = 0, hemos pasado por C(2, 51) combinaciones, ya que los índices i1, i2 pasan por todas las combinaciones de 2 de los 51 números.
Para i1 = 1 pasamos por combinaciones C(2, 50).
Para i1 = 2 pasamos por combinaciones C(2, 49).
En total, pasamos por SUM (de n = 0 a n = i1-1) C(2, 51-n).
Para i1 = 3, consideremos aquellas combinaciones que pasamos mientras ejecutamos el índice i2 (y para nosotros comienza con i2 = i1+1 = 4).
Cuando i2 = 4, pasaron las combinaciones C(1, 47), cuando i2 = 5, pasaron las combinaciones C(1, 46), cuando i2 = 6, pasaron las combinaciones C(1, 45).
Por completa analogía, para i2 = 7 consideramos las combinaciones que recorrió el índice i3.
Obtenemos la fórmula general:
El índice de combinación requerido = SUMA (de n = 0 a i1-1) C(2, 51-n) + SUMA (de n = i1+1 a i2-1) C(1, 51-n) + SUMA (de n = i2+1 a i3-1) C (0, 51-n).Índice de subconjunto
En combinatoria hay un objeto más complejo: la partición en subconjuntos. Por ejemplo, dividir un conjunto de 52 elementos en tres subconjuntos de, digamos, 2, 3 y 47 elementos, respectivamente, donde el orden de los elementos dentro de cada subconjunto no es importante. (Por cierto, una combinación de 2 de 52 es simplemente un caso especial de división en dos subconjuntos de 2 y 50 elementos, respectivamente).
Nuevamente, cada una de estas particiones tiene su propio índice.
Resulta que nuestro algoritmo para encontrar el índice de combinación se puede modificar para encontrar el índice de partición.
Cabe señalar que debemos ordenar los índices de la “combinación externa” i1, i2 entre sí y los índices i3, i4, i5 entre sí, pero independientemente de los dos primeros.
También hay que tener en cuenta que en una “combinación anidada” esencialmente trabajamos con un conjunto de 50 elementos, pero los índices i3, i4, i5 deben “desplazarse” de cierta manera para que no cambien de 0. a 51, pero de 0 a 49:
(por así decirlo, recortamos los índices i1, i2 de nuestro conjunto de 52 elementos y luego desplazamos el conjunto restante para cerrar los agujeros, mientras que los índices i3-i5 se desplazan).
Hay que tener en cuenta que dentro de cada combinación “externa” tenemos exactamente C(3, 50) combinaciones “anidadas”.
Entonces el algoritmo se reducirá a lo siguiente:
COMBINATION_INDEX (i1, i2 de 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 de 50 después del cambio de índice). Llevando los algoritmos a una complejidad constante
Debo señalar inmediatamente que se produce un “error” en la fórmula si, por ejemplo, i1 = 0 (contamos la suma para n = de 0 a -1) o i2 = 1 (contamos la suma de 1 a 0). De hecho, en tales casos la suma correspondiente debe tomarse igual a cero y el resultado será correcto.
También debo prestar atención a la complejidad temporal de nuestros algoritmos: tienen complejidad lineal, siempre que se considere que C es un tiempo constante. Esto ya es mucho mejor que la fuerza bruta.
Pero en realidad (en nuestro caso 52) nada nos impide reducir el algoritmo a una complejidad constante. Para ello aplicaremos conocimientos de matemáticas y calcularemos analíticamente todas las cantidades.
Por ejemplo, el número de combinaciones C(2, K), si lo “expandes” en forma de fórmula K. / ((K-2)! * 2!), se reduce a un polinomio de 2º grado. Y como lo tenemos bajo el signo de suma, podemos aplicar las fórmulas para la suma de enésimas potencias de números en la serie natural (ver Wikipedia) y obtener un solo polinomio de 3er grado. Lo que obviamente tiene una complejidad temporal constante. (Además, el “error” que cité al principio del subtítulo no se manifiesta de ninguna manera; la fórmula sigue siendo correcta).
repito, esto para una dimensión fija del conjunto básico. Sin embargo, estoy seguro de que con la ayuda de la metaprogramación puedes “enseñar” al compilador para que haga este trabajo por ti. Epílogo
En mi simulador de póquer (Texas Hold'em), quería calcular y almacenar de antemano las probabilidades de ganar de todas las combinaciones posibles de mis cartas de mano (2 piezas) y todas las cartas del flop (3 cartas en la mesa). el 52-set por 2, 3, 47 subconjuntos.
Calculado y guardado.
Pero cuando llegó el momento de leer datos de un archivo para una combinación específica, realmente no quería calcular algo durante mucho tiempo ni buscar en un archivo de gigabytes. Ahora simplemente determino el desplazamiento en el archivo y leo directamente lo que necesito.
Sería interesante tener un libro de referencia sobre algoritmos combinatorios para todos los objetos combinatorios, incluidas permutaciones, combinaciones, ubicaciones, subconjuntos, combinaciones con repeticiones, ubicaciones con repeticiones. Fórmulas explícitas
Enlaces
Vea qué es "Número de combinaciones" en otros diccionarios:
Libros