simple combinatoria pregunta sobre el objeto de la división de

Question

De cuántas maneras se puede resolver la ecuación $X_1+X_2+ \cdots +X_{15} = 300$ ($X_1,X_2, \ldots, X_{15}$ son números naturales), de modo que :

a) para cada $1 \leq i \leq 15$, $X_i \leq 19$
b) por cada $1 \leq i \leq 15$, $X_i \leq 20$
c) para cada $1 \leq i \leq 15$, $X_i \leq 40$

Así que estoy 99% seguro de que a y b son no por la lógica y no a la combinatoria.
$19 \cdot 15 = 285$ hay $0$ de posibilidades de que va a pasar.
$20 \cdot 15 = 300$ así que la única opción que va a pasar va a ser si todos los números son $20$.
para c, estoy pensando en tomar todas las opciones, por lo que es $314$ elija $300$ y a partir de ahí estoy restando todas las veces que me dan un número $41$, yo lo hago de $7$ veces porque después de $8$ veces será más de $300$, estoy ni siquiera cerca de la manera correcta ? Gracias de antemano.

Answer 1

Si no hay restricciones, a continuación, el número de soluciones de la ecuación $$x_1 + x_2 + \cdots + x_{15} = 300$$ en los enteros no negativos sería $$\binom{300 + 14}{14} = \binom{314}{14}$$ Sin embargo, queremos que cada una de las $x_i \leq 40$. Por lo tanto, debemos restar el número de soluciones en las que uno o más de los $x_i \geq 41$. Desde $7 \cdot 41 = 287 < 300 < 328 = 8 \cdot 41$, hasta las siete de la $x_i$'s podría ser, al menos,$41$. Para ello, utilizamos la Inclusión-Exclusión Principio.

Restando el número de soluciones en el que exactamente un $x_i$ supera $40$ del total de la quita cada solución en la que exactamente dos $x_i$'s exceder $40$ dos veces, por lo que debemos añadir el número de soluciones en el que exactamente dos $x_i$'s exceder $40$. Eliminar el número de soluciones en el que exactamente un $x_i$ supera $40$ del número total de soluciones, luego agregar el número de soluciones en el que exactamente dos $x_i$'s exceder $40$ cuenta cada solución en la que exactamente tres $x_i$'s exceder $40$ cuenta de una vez (ya que cada solución fue el primer eliminado tres veces, y luego restaurada en tres ocasiones), así que hay que restar el número de soluciones en el que exactamente tres $x_i$'s exceder $40$. Por un razonamiento similar, se debe agregar el número de soluciones en el que exactamente cuatro $x_i$'s exceder $40$, restar el número en el que exactamente cinco $x_i$'s exceder $40$, añada el número de soluciones en el que exactamente seis $x_i$'s exceder $40$, luego restar el número de soluciones en el que exactamente siete $x_i$'s exceder $40$.

Supongamos $x_1 > 40$. Deje $y_1 = x_1 - 41$. \begin{align*} x_1 + x_2 + \cdots + x_{15} & = 300\\ y_1 + 41 + x_2 + \cdots + x_{15} & = 300\\ y_1 + x_2 + \cdots + x_{15} & = 259 \end{align*} El número de soluciones de esta ecuación en los enteros no negativos es $$\binom{259 + 14}{14} = \binom{273}{14}$$ Desde allí se $15$ maneras de que exactamente uno de los $x_i$'s exceder $40$, el número de soluciones en el que exactamente un $x_i > 40$ es $$\binom{15}{1}\binom{273}{14}$$ Supongamos $x_1$ $x_2$ ambos superan $40$. Deje $y_1 = x_1 - 41$$y_2 = x_2 - 41$. Entonces \begin{align*} x_1 + x_2 + x_3 + \cdots + x_{15} & = 300\\ y_1 + 41 + y_2 + 41 + x_3 + \cdots + x_{15} & = 300\\ y_1 + y_2 + x_3 + \cdots + x_{15} & = 218 \end{align*} Esta ecuación tiene $$\binom{218 + 14}{14} = \binom{232}{14}$$ soluciones en los enteros no negativos. Desde allí se $\binom{15}{2}$ maneras de que exactamente dos de las $x_i$'s exceder $40$, hay $$\binom{15}{2}\binom{232}{14}$$ soluciones en las que exactamente dos de las $x_i$'s exceder $40$.

Calcular el número de soluciones en el que exactamente tres, exactamente cuatro, exactamente dar, exactamente seis, y exactamente siete de la $x_i$'s exceder $40$, a continuación, utilizar la Inclusión-Exclusión Principio para determinar el número de soluciones en el que cada una de las $x_i \leq 40$. La solución debería ser algo como

$$\binom{314}{14} - \binom{15}{1}\binom{273}{14} + \binom{15}{2}\binom{232}{14} - \cdots + \cdots - \cdots + \cdots - \cdots$$

Answer 2

El enfoque que está tomando es sin duda a lo largo de el camino correcto, tratar de hacer un poco más formal, mediante la Inclusión-Exclusión en el principio, y lo más probable es encontrar las cosas más simples.

Alternativamente (y equivalentes), se podía ver en la generación de funciones: la ordinaria, la generación de la función de las opciones para un determinado $X_i$ es $$ \sum_{i=0}^{40}x^i, $$ dado que sólo hay una opción de cada tamaño; esta es una forma geométrica de la suma, y puede ser simplificado. ¿Qué hace la OGF por la suma de $X_1+\cdots+X_{15}$ buscar en este caso, y lo que el coeficiente le dirá cuántas combinaciones suma a $300$?