Número de combinações para as quais $x_1+x_2+x_3=100$ se para cada $3\ge i\ge 1$, $x_i$ é um número inteiro não negativo com $40\ge x_i$

Aug 18 2020

Recentemente me deparei com a seguinte pergunta:

Encontre o número de combinações para as quais $x_1+x_2+x_3=100$ se para cada $3\ge i\ge 1$, $x_i$ é um número inteiro não negativo com $40\ge xi$.

Eu resolvi isso da seguinte maneira, dividindo-o em diferentes instâncias

E se $x_1=20$: 1 solução ($x_2=40, x_3=40$)

E se $x_1=21$: 2 soluções

E se $x_1=22$: 3 soluções

$\ldots$

E se $x_1=40$: 21 soluções

Como o total resultante é a adição de uma progressão aritmética, temos $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$

Encontrei essa questão em um capítulo relacionado ao princípio de inclusão-exclusão, mas não consigo pensar em como resolvê-lo usando o princípio de exclusão de inclusão. Alguém poderia me mostrar uma solução simples para essa questão com o uso do princípio de inclusão-exclusão, explicando também como ele intuitivamente pensou em seguir cada etapa?

Respostas

2 N.F.Taussig Aug 18 2020 at 21:09

Uma solução particular da equação $$x_1 + x_2 + x_3 = 100 \tag{1}$$ corresponde à colocação de $3 - 1 = 2$ sinais de adição em uma fileira de $100$uns. Por exemplo, se colocarmos os sinais de adição após o$20$th e $60$estes, obtemos a solução $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (conte o número de unidades à esquerda do primeiro sinal de adição para o valor de $x_1$, entre os dois sinais de adição para o valor de $x_2$, e à direita de ambos os sinais de adição para o valor de $x_3$) Portanto, o número de soluções da equação nos inteiros não negativos é$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ uma vez que devemos escolher quais dos dois $102$ posições exigidas para $100$ uns e dois sinais de adição serão preenchidos com sinais de adição.

Destes, devemos subtrair os casos em que uma ou mais das variáveis ​​excede $40$.

Uma variável excede $40$: Existem três maneiras de escolher qual variável excede $40$. Suponha que seja$x_1$. Então$x_1' = x_1 - 41$é um número inteiro não negativo. Substituindo$x_1' + 41$ para $x_1$ na equação 1 produz \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} A Equação 2 é uma equação nos inteiros não negativos com $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$soluções. Portanto, existem$$\binom{3}{1}\binom{61}{2}$$ soluções em que o valor de uma variável excede $40$.

No entanto, se subtrairmos este valor do total, teremos subtraído cada caso em que duas variáveis ​​excedem $40$ duas vezes, uma para cada forma de designar uma dessas duas variáveis ​​como a variável que excede $40$. Queremos subtrair esses casos apenas uma vez, portanto, devemos adicioná-los ao total.

Duas variáveis ​​excedem $40$: Tem $\binom{3}{2}$ maneiras de selecionar quais duas variáveis ​​excedem $40$. Suponha que eles sejam$x_1$ e $x_2$. Então$x_1' = x_1 - 41$ e $x_2' = x_2 - 41$são inteiros não negativos. Substituindo$x_1' + 41$ para $x_1$ e $x_2' + 41$ para $x_2$ na equação 1 produz \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} A Equação 3 é uma equação nos inteiros não negativos com $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$soluções. Portanto, existem$$\binom{3}{2}\binom{20}{2}$$ soluções em que duas variáveis ​​excedem $40$.

Assim, pelo Princípio de Inclusão-Exclusão, o número de soluções da equação 1 em que nenhuma variável excede $40$ é $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ como você encontrou.

2 FelixMarin Aug 19 2020 at 01:10

$\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}$ De $\ds{\ \underline{definition}}$, a resposta é 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}