Número de combinaciones para las que $x_1+x_2+x_3=100$ si por cada $3\ge i\ge 1$, $x_i$ es un número entero no negativo con $40\ge x_i$
Recientemente me encontré con la siguiente pregunta:
Encuentre el número de combinaciones para las cuales $x_1+x_2+x_3=100$ si por cada $3\ge i\ge 1$, $x_i$ es un número entero no negativo con $40\ge xi$.
Lo resolví de la siguiente manera, dividiéndolo en diferentes instancias
Si $x_1=20$: 1 solución ($x_2=40, x_3=40$)
Si $x_1=21$: 2 soluciones
Si $x_1=22$: 3 soluciones
$\ldots$
Si $x_1=40$: 21 soluciones
Como el total resultante es la suma de una progresión aritmética, tenemos $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
Encontré esta pregunta en un capítulo relacionado con el principio de inclusión-exclusión, sin embargo, no puedo pensar en cómo resolverlo usando el principio de inclusión-exclusión. ¿Podría alguien mostrarme una solución clara a esta pregunta con el uso del principio de inclusión-exclusión, explicando también cómo pensó intuitivamente en continuar con cada paso?
Respuestas
Una solución particular de la ecuación $$x_1 + x_2 + x_3 = 100 \tag{1}$$ corresponde a la colocación de $3 - 1 = 2$ signos de suma en una fila de $100$unos. Por ejemplo, si colocamos los signos de suma después del$20$th y $60$ésos, obtenemos la solución $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (cuente el número de unos a la izquierda del primer signo de suma para el valor de $x_1$, entre los dos signos de suma para el valor de $x_2$, y a la derecha de ambos signos de suma para el valor de $x_3$). Por tanto, el número de soluciones de la ecuación en los enteros no negativos es$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ ya que debemos elegir cuáles de las $102$ puestos requeridos para $100$ uno y dos signos de adición se llenarán con signos de adición.
De éstos, debemos restar aquellos casos en los que una o más de las variables excede $40$.
Una variable excede $40$: Hay tres formas de elegir qué variable excede $40$. Supongamos que es$x_1$. Luego$x_1' = x_1 - 41$es un número entero no negativo. Sustituyendo$x_1' + 41$ para $x_1$ en la ecuación 1 produce \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} La ecuación 2 es una ecuación en los enteros no negativos con $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$soluciones. Por lo tanto, hay$$\binom{3}{1}\binom{61}{2}$$ soluciones en las que el valor de una variable excede $40$.
Sin embargo, si restamos esta cantidad del total, habremos restado cada caso en el que dos variables excedan $40$ dos veces, una por cada forma de designar una de esas dos variables como la variable que excede $40$. Solo queremos restar estos casos una vez, por lo que debemos sumarlos al total.
Dos variables superan $40$: Existen $\binom{3}{2}$ formas de seleccionar qué dos variables exceden $40$. Supongamos que son$x_1$ y $x_2$. Luego$x_1' = x_1 - 41$ y $x_2' = x_2 - 41$son números enteros no negativos. Sustituyendo$x_1' + 41$ para $x_1$ y $x_2' + 41$ para $x_2$ en la ecuación 1 produce \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} La ecuación 3 es una ecuación en los enteros no negativos con $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$soluciones. Por lo tanto, hay$$\binom{3}{2}\binom{20}{2}$$ soluciones en las que dos variables superan $40$.
Por lo tanto, según el principio de inclusión-exclusión, el número de soluciones de la ecuación 1 en las que ninguna variable excede $40$ es $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ como encontraste.
$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ Por $\ds{\ \underline{definition}}$, la respuesta viene dada por: \begin{align} &\bbox[5px,#ffd]{\sum_{x_{1} = 1}^{40} \sum_{x_{2} = 1}^{40}\sum_{x_{3} = 1}^{40}\ \overbrace{\bracks{z^{100}}z^{x_{1}\ +\ x_{2}\ +\ x_{3}}} ^{\ds{\delta_{x_{1}\ +\ x_{2}\ +\ x_{3}{\large ,} 100}}}\ =\ \bracks{z^{100}}\pars{\sum_{x = 1}^{40}z^{x}}^{3}} \\[5mm] = &\ \bracks{z^{100}}\pars{z\,{z^{40} - 1 \over z - 1}}^{3} \\[5mm] = &\ \bracks{z^{97}}\pars{1 - z^{40}}^{3}\pars{1 - z}^{-3} = \bracks{z^{97}}\pars{1 - 3z^{40} + 3z^{80}}\pars{1 - z}^{-3} \\[5mm] = &\ \bracks{z^{97}}\pars{1 - z}^{-3} - 3\bracks{z^{57}}\pars{1 - z}^{-3} + 3\bracks{z^{17}}\pars{1 - z}^{-3} \\[5mm] = &\ {-3 \choose 97}\pars{-1}^{97} - 3{-3 \choose 57}\pars{-1}^{57} + 3{-3 \choose 17}\pars{-1}^{17} \\[5mm] = &\ \underbrace{{99 \choose 97}}_{\ds{4851}}\ -\ 3\ \underbrace{{59 \choose 57}}_{\ds{1711}}\ +\ 3\ \underbrace{{19 \choose 17}}_{\ds{171}}\ =\ \bbx{\large 231} \end{align}