Problema de combinación con restricciones

Question

Tienes cuatro contenedores y una jarra de agua con capacidad para 100L. Cada contenedor tiene diferentes capacidades con niveles máximos de, digamos... 70L, 45L, 33L y 11L respectivamente.

¿Cuál es la fórmula que se puede utilizar para resolver el número de todas las combinaciones posibles en las que se puede verter un total (en este caso, 100L de agua) entre una serie de recipientes (70L, 45L, 33L 11L), cada uno de los cuales tiene un nivel máximo diferente?

He investigado el coeficiente binomial, $\displaystyle \frac {n!}{r!(n-r)!}$ pero esto resolvería el número de combinaciones si los contenedores tienen el mismo máximos, no variando máximos.

Las funciones generadoras pueden resolver combinaciones con restricciones, pero ¿qué pasa con una fórmula que se pueda introducir directamente para encontrar sólo la respuesta al coeficiente único y al total que se busca; no todos los coeficientes posibles y todos los totales posibles para esos conjuntos? Me cuesta entender cómo se puede conseguir esto mediante funciones generadoras o cualquier otro método.

¿Puedes dibujar una fórmula para resolver el número de combinaciones conociendo lo siguiente: el número de conjuntos y sus máximos, y el número total que se puede dividir entre ellos?

He aquí otro ejemplo: ${[0-5] + [0-15] + [0-24] + [0-35] + [0-51]}$ . El total debe ser 60.

Answer 1

Así que estás pidiendo una manera fácil de encontrar el número de soluciones en enteros no negativos a $a+b+c+d=100$ , $a\le70$ , $b\le45$ , $c\le33$ , $d\le11$ . Hagámoslo por las malas y veamos qué nos dice la respuesta. Lo que queremos es el coeficiente de $x^{100}$ en $$(1+x+\cdots+x^{70})(1+x+\cdots+x^{45})(1+x+\cdots+x^{33})(1+x+\cdots+x^{11})$$ que es $$(x^{71}-1)(x^{46}-1)(x^{34}-1)(x^{12}-1)(1-x)^{-4}$$ que es $$(1-x^{12}-x^{34}+x^{58}-x^{71}+x^{80}+x^{83}-x^{92}+\dots)(1+4x+10x^2+20x^3+\dots)$$ donde los coeficientes del segundo paréntesis son los coeficientes binomiales $n$ -elegir-3. Así que la respuesta va a ser una suma/diferencia de 8 de estos coeficientes binomiales. No se me ocurre ninguna razón para esperar que haya una forma más sencilla para la respuesta, ni una forma más sencilla de llegar a ella. ¿Y tú?

Answer 2

Se puede utilizar la programación dinámica. Dados enteros no negativos $M_j$ , $j = 1 \ldots n$ , dejemos que $F(y,m)$ sea el número de soluciones de $x_1 + \ldots + x_m = y$ con $x_j \in \{0,\ldots,M_j\}$ para cada $j$ . Entonces $F(y, 1) = 1$ para $y=0, 1, \ldots M_1$ , $0$ para $y > M_1$ y $F(y, m+1) = \sum_{x=0}^{\min(y,M_{m+1})} F(y - x, m)$ .

Answer 3

Otro enfoque es la inclusión-exclusión. Si no tuvieras las restricciones sólo estarías pidiendo el número de soluciones en enteros no negativos a $$a+b+c+d=100$$ que es ${103\choose3}$ . Pero hay que tirar las soluciones con $a\ge71$ que es $a-71\ge0$ . Dejemos que $a'=a-71$ ; entonces estás tirando soluciones a $$a'+b+c+d=29$$ de los cuales hay ${32\choose3}$ . Del mismo modo, hay que desechar las soluciones con $b\ge46$ Los que tienen $c\ge34$ y los que tienen $d\ge12$ . Esto te lleva a $${103\choose3}-{32\choose3}-{57\choose3}-{69\choose3}-{91\choose3}$$ Pero ha desechado algunas soluciones dos veces; por ejemplo, las que tienen tanto $b\ge46$ y $c\ge34$ . Hay que volver a colocarlos. Estos corresponden a soluciones de $$a+b'+c'+d=20$$ de los cuales hay ${23\choose3}$ . Del mismo modo, para las soluciones con $b\ge46$ y $d\ge12$ y los que tienen $c\ge34$ y $d\ge12$ y los que tienen $a\ge71$ y $d\ge12$ . En total, son 4 coeficientes binomiales que hay que volver a añadir. Por último, están las soluciones con $b\ge46$ y $c\ge34$ y $d\ge12$ ; estos se contaron originalmente, luego se echaron tres veces, luego se volvieron a echar tres veces; hay que echarlos una vez más, por lo que hay que restar un coeficiente binomial más, el correspondiente a $$a+b'+c'+d'=8$$ que es ${11\choose3}$ .