función generadora: ¿cuántas posibilidades hay para lanzar 10 dados diferentes para que su suma sea 25?

Question

Mi libro de texto de matemáticas discreto tiene la siguiente solución al problema que usa funciones de generación (la solución tiene que usar funciones de generación):

ps

Una vez que comenzamos a desarrollar la serie de poder formal, obtenemos lo siguiente:

$$f(x)=(x+x^2+x^3+x^4+x^5+x^6)^{10}$ $ Debido a$$x^{10}(1-x^6)^{10}\frac{1}{(1-x)^{10}}$, ahora necesitamos encontrar el coeficiente de solo$x^{10}$:$x^{15}$ $ Entiendo completamente las dos primeras expresiones, pero ¿por qué estamos usando la tercera? $$\binom{10}{0}\binom{10-1+15}{15}-\binom{10}{1}\binom{10-1+9}{9}+\binom{10}{2}\binom{10-1+3}{3}$ $ ¿De dónde proviene el$$\binom{10}{2}\binom{10-1+3}{3}$ y por qué esto no es suficiente:$3$ $?

Answer 1

El coeficiente de$x^{25}$ en$(x+x^2+\ldots+x^6)^{10}$ es igual al coeficiente de$x^{15}$ en$$ (1+x+\ldots+x^5)^{10} = (1-x^6)^{10}\cdot\frac{1}{(1-x)^{10}} $ $ así que la respuesta está dada por$$ [x^{15}] \left(\sum_{k=0}^{10}\binom{10}{k}(-1)^k x^{6k}\right)\cdot\left(\sum_{j\geq 0}\binom{9+j}{j}x^j\right) $ $ y basta con considerar solo el términos asociados con$k=0,1,2$, ya que$x^{6k}$ tiene un exponente mayor que$15$ para cualquier$k>2$. Al calcular el producto Cauchy entre las series anteriores, se deduce que la respuesta está dada por:$$ \underbrace{\binom{10}{0}\binom{24}{15}}_{k=0,\;j=15}-\underbrace{\binom{10}{1}\binom{18}{9}}_{k=1,\;j=9}+\underbrace{\binom{10}{2}\binom{12}{3}}_{k=2,\;j=3}.$ $

Answer 2

Como contraposición a la generación de funciones, personalmente aprendí a resolver esta cuestión a través de la inclusión a la exclusión.

Estábamos buscando el número entero de soluciones del sistema: $\begin{cases} x_1+x_2+\dots+x_{10}=25\\ 1\leq x_i\leq 6&\text{for all}~i\end{cases}$

A través de un cambio de variable, en su lugar, tenemos el sistema de $\begin{cases}y_1+y_2+\dots+y_{10}=15\\ 0\leq y_i\leq 5\end{cases}$

Se aproxima a través de la inclusión-exclusión en los eventos que el correspondiente límite superior condiciones son violados. Deje $S$ estar donde nos ignorar cualquier cota superior de condiciones. Deje $A_i$ ser el conjunto donde el $i$'th límite superior condición es violado. El total sin límite superior de condiciones violado es:

$$|S|-\sum\limits_{i=1}^{10}|A_i|+\sum\limits_{i=1}^{10}\sum\limits_{j=i+1}^{10}|A_i\cap A_j| - \sum\limits_{i=1}^{10}\sum\limits_{j=i+1}^{10}\sum\limits_{k=j+1}^{10}|A_i\cap A_j\cap A_k|+\dots$$

si no tenemos un límite superior de condiciones violado, hay $\binom{10+15-1}{15}$ soluciones. Si una cota superior de la condición es violado, de escoger uno. Cada uno de los cuales contará con un total de $\binom{10+9-1}{9}$ soluciones para un total de $\binom{10}{1}\binom{18}{9}$ necesidad de ser retirado de la cuenta. Si dos de límite superior de condiciones son violados, recoger los cuales dos de ellos son. Cada uno de los cuales contará con un total de $\binom{10+3-1}{3}$ soluciones para un total de $\binom{10}{2}\binom{12}{3}$ necesidad de añadir. Tres de límite superior de condiciones de ser al mismo tiempo violado es imposible.

Esto le da, de nuevo, la solución de:

$$\binom{10}{0}\binom{24}{15}-\binom{10}{1}\binom{18}{9}+\binom{10}{2}\binom{12}{3}$$

La explicación para el último término de esta comprensión, que había sustraído de la misma "malos resultados" de su total demasiadas veces lo contrario. Por qué usamos un $3$ sería de cómo vamos a resolver la cuestión de saber cuántos violar la $i$'th y $j$'th límite superior de condiciones. Supongamos $i=1$$j=2$, entonces tenemos el sistema:

$\begin{cases} y_1+y_2+\dots+y_{10}=15\\ 6\leq y_1\\ 6\leq y_2\\ 0\leq y_3\\ \vdots \\ 0\leq y_{10}\end{cases}$

Después de un cambio de variable, tenemos el sistema

$\begin{cases} z_1+z_2+\dots+z_{10}=3\\ 0\leq z_i\end{cases}$ que es de una forma conocida.