Cómo encontrar el número de soluciones enteras no negativas en una ecuación

Answer 1

Es útil poder reformular un problema en términos de otro que ya sabe cómo resolver, ya que este ejercicio está tratando de demostrarlo.

Hay una fórmula para la cantidad de soluciones a la primera ecuación, basada en contar varios conjuntos. El número de soluciones no negativas a la suma de las variables [matemáticas] n [/ matemáticas] que suman [matemáticas] k [/ matemáticas] es [matemáticas] k + n – 1 \ elegir k [/ matemáticas]; La respuesta de Hai Tran da una referencia.

Entonces, ¿cómo podemos traducir los problemas # 2 y # 3 a esa forma? (Una forma de abordar el n. ° 2 es sumar todos los [math] k [/ math] del 1 al 57, pero eso es algo engorroso). En cambio, podemos agregar una variable ficticia

[matemáticas] x_1 + x_2 + x_3 +… + x_ {100} + x_ {101} = 57 [/ matemáticas]

Cuando la suma de las primeras 100 variables es menor que 57, [math] x_ {101} [/ math] hace la diferencia. Cuando son iguales a 57, [matemáticas] x_ {101} = 0 [/ matemáticas]. Si son mayores que 57, entonces ninguna solución funciona. Por lo tanto, el número de soluciones a esta ecuación transformada es exactamente igual al número de soluciones de la ecuación original.

Este es un truco útil en la programación lineal: a menudo verá que se usa allí. (¡También ha demostrado una identidad sobre los coeficientes binomiales, si escribe las dos formas de resolver este problema!)

Para abordar el tercer problema, podemos pensar en reemplazar cada variable [math] 1 \ leq x_i [/ ​​math] con una nueva variable [math] 0 \ leq y_i = x_i – 1 [/ math]. Si sustituimos todas las “y” en la restricción obtenemos

[matemáticas] y_1 + y_2 +… + y_ {100} = (x_1 – 1) + (x_2 -1) +… (x_ {100} – 1) = 200 – 100 = 100 [/ matemáticas]

que sabemos resolver Cada conjunto de [matemáticas] y [/ matemáticas] en esta ecuación nos da una respuesta distinta para [matemáticas] x [/ matemáticas] en la ecuación original, por lo que los recuentos son idénticos. ¡Este es un paso importante! No todas las transformaciones conservan el número de soluciones, pero si podemos ubicarlas en correspondencia 1-1, entonces estamos bien.

Answer 2

Este teorema es lo que necesitas:

Fuente: https://math.dartmouth.edu/~m68f …

(1) Aplicar el teorema con n = 100, k = 200

(2) Aplicar el teorema con n = 100, k de 0 a 57

(3) Sea yi = xi – 1 para todo i {1,…, 100}

Tenemos y1 + y2 +… + y100 = 200 – 100 = 100

Aplicar el teorema con n = k = 100

Answer 3

La respuesta al número de soluciones enteras no negativas de [matemáticas] x_1 +… + x_m = n [/ matemáticas] es [matemáticas] \ binom {m + n – 1} {m – 1} [/ matemáticas]

Prueba: Considere la pregunta sobre el número de soluciones enteras positivas para [matemáticas] x_1 +… + x_m = n [/ matemáticas]. Esto es equivalente a distribuir [math] n [/ math] dulces a [math] m [/ math] niños.

Una forma de hacer esto es colocar todos los dulces en una línea, colocar dos palos en los dos extremos y colocar otros palos [matemáticos] m-1 [/ matemáticos] en los espacios entre los dulces. Y el primer niño obtendrá los dulces entre el primer y el segundo palo, el segundo niño tomará los que están entre el segundo y el tercer palo, y así sucesivamente.

Como cada niño recibe un número positivo de dulces, no se pueden colocar dos palos en el mismo espacio entre dos dulces. Hay [matemática] m-1 [/ matemática] palos y [matemática] n-1 [/ matemática] huecos, por lo que la cantidad de formas de colocar los palos es [matemática] \ binom {n-1} {m-1 }[/matemáticas]. Este es el número de soluciones enteras positivas para [matemáticas] x_1 +… + x_m = n [/ matemáticas]

Para el número de soluciones enteras no negativas, considere [matemática] x_1 +… + x_m + m = m + n [/ matemática], que es equivalente a [matemática] (x_1 + 1) +… + (x_m + 1) = m + n [/ matemáticas]. Como [math] x_i [/ ​​math] no es negativo, [math] x_i + 1 [/ math] es positivo, por lo que con la prueba anterior podemos ver que el número de soluciones es [math] \ binom {m + n – 1} {m – 1} [/ matemáticas].

Entonces solo queda la parte 2. Esto es realmente lo mismo que esta ecuación [matemáticas] x_1 +… + x_ {100} + x_ {101} = 57 [/ matemáticas].