Nombre de combinaisons pour lesquelles $x_1+x_2+x_3=100$ si pour chaque $3\ge i\ge 1$, $x_i$ est un entier non négatif avec $40\ge x_i$
Je suis récemment tombé sur la question suivante:
Trouvez le nombre de combinaisons pour lesquelles $x_1+x_2+x_3=100$ si pour chaque $3\ge i\ge 1$, $x_i$ est un entier non négatif avec $40\ge xi$.
Je l'ai résolu de la manière suivante, en le divisant en différentes instances
Si $x_1=20$: 1 solution ($x_2=40, x_3=40$)
Si $x_1=21$: 2 solutions
Si $x_1=22$: 3 solutions
$\ldots$
Si $x_1=40$: 21 solutions
Comme le total résultant est l'addition d'une progression arithmétique, nous avons $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
J'ai trouvé cette question dans un chapitre relatif au principe d'inclusion-exclusion, mais je ne vois pas comment la résoudre en utilisant le principe d'exclusion d'inclusion. Quelqu'un pourrait-il s'il vous plaît me montrer une solution soignée de cette question avec l'utilisation du principe d'inclusion-exclusion, en expliquant également comment il a intuitivement pensé passer à chaque étape?
Réponses
Une solution particulière de l'équation $$x_1 + x_2 + x_3 = 100 \tag{1}$$ correspond au placement de $3 - 1 = 2$ signes d'ajout dans une rangée de $100$ceux. Par exemple, si nous plaçons les signes d'addition après le$20$e et $60$e, nous obtenons la solution $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (compter le nombre de uns à gauche du premier signe d'addition pour la valeur de $x_1$, entre les deux signes d'addition pour la valeur de $x_2$, et à droite des deux signes d'addition pour la valeur de $x_3$). Par conséquent, le nombre de solutions de l'équation dans les entiers non négatifs est$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ puisque nous devons choisir lesquels des deux $102$ postes requis pour $100$ un et deux signes d'addition seront remplis de signes d'addition.
De ceux-ci, nous devons soustraire les cas dans lesquels une ou plusieurs des variables dépasse $40$.
Une variable dépasse $40$: Il existe trois façons de choisir quelle variable dépasse $40$. Supposons que ce soit$x_1$. ensuite$x_1' = x_1 - 41$est un entier non négatif. Remplacer$x_1' + 41$ pour $x_1$ dans l'équation 1 donne \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} L'équation 2 est une équation dans les entiers non négatifs avec $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$solutions. Par conséquent, il y a$$\binom{3}{1}\binom{61}{2}$$ solutions dans lesquelles la valeur d'une variable dépasse $40$.
Cependant, si nous soustrayons ce montant du total, nous aurons soustrait chaque cas dans lequel deux variables dépassent $40$ deux fois, une fois pour chaque façon de désigner l'une de ces deux variables comme la variable qui dépasse $40$. Nous ne voulons soustraire ces cas qu'une seule fois, nous devons donc les ajouter au total.
Deux variables dépassent $40$: Il y a $\binom{3}{2}$ façons de sélectionner les deux variables qui dépassent $40$. Supposons qu'ils soient$x_1$ et $x_2$. ensuite$x_1' = x_1 - 41$ et $x_2' = x_2 - 41$sont des entiers non négatifs. Remplacer$x_1' + 41$ pour $x_1$ et $x_2' + 41$ pour $x_2$ dans l'équation 1 donne \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} L'équation 3 est une équation dans les entiers non négatifs avec $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$solutions. Par conséquent, il y a$$\binom{3}{2}\binom{20}{2}$$ solutions dans lesquelles deux variables dépassent $40$.
Ainsi, selon le principe d'inclusion-exclusion, le nombre de solutions de l'équation 1 dans lesquelles aucune variable ne dépasse $40$ est $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ comme vous l'avez trouvé.
$\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}$ Par $\ds{\ \underline{definition}}$, la réponse est donnée par: \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}