Numero di combinazioni per le quali $x_1+x_2+x_3=100$ se per ogni $3\ge i\ge 1$, $x_i$ è un numero intero non negativo con $40\ge x_i$
Di recente mi sono imbattuto nella seguente domanda:
Trova il numero di combinazioni per cui $x_1+x_2+x_3=100$ se per ogni $3\ge i\ge 1$, $x_i$ è un numero intero non negativo con $40\ge xi$.
L'ho risolto nel modo seguente, suddividendolo in diverse istanze
Se $x_1=20$: 1 soluzione ($x_2=40, x_3=40$)
Se $x_1=21$: 2 soluzioni
Se $x_1=22$: 3 soluzioni
$\ldots$
Se $x_1=40$: 21 soluzioni
Poiché il totale risultante è l'aggiunta di una progressione aritmetica, abbiamo $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
Ho trovato questa domanda in un capitolo relativo al principio di inclusione-esclusione, tuttavia non riesco a pensare a come risolverlo utilizzando il principio di esclusione di inclusione. Qualcuno potrebbe mostrarmi una chiara soluzione di questa domanda con l'uso del principio di inclusione-esclusione, spiegando anche come pensava intuitivamente di andare avanti a ogni passaggio?
Risposte
Una particolare soluzione dell'equazione $$x_1 + x_2 + x_3 = 100 \tag{1}$$ corrisponde al posizionamento di $3 - 1 = 2$ segni di addizione in una fila di $100$quelli. Ad esempio, se inseriamo i segni di addizione dopo$20$th e $60$esimo, otteniamo la soluzione $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (conta il numero di unità a sinistra del primo segno di addizione per il valore di $x_1$, tra i due segni di addizione per il valore di $x_2$, ea destra di entrambi i segni di addizione per il valore di $x_3$). Pertanto, il numero di soluzioni dell'equazione negli interi non negativi è$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ poiché dobbiamo scegliere quali due dei $102$ posizioni richieste per $100$ uno e due segni di addizione saranno riempiti con segni di addizione.
Da questi dobbiamo sottrarre quei casi in cui una o più variabili eccede $40$.
Una variabile supera $40$: Esistono tre modi per scegliere quale variabile supera $40$. Supponiamo che lo sia$x_1$. Poi$x_1' = x_1 - 41$è un numero intero non negativo. Sostituzione$x_1' + 41$ per $x_1$ nell'equazione 1 si ottiene \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} L'equazione 2 è un'equazione negli interi non negativi con $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$soluzioni. Quindi, ci sono$$\binom{3}{1}\binom{61}{2}$$ soluzioni in cui il valore di una variabile supera $40$.
Tuttavia, se sottraiamo questo importo dal totale, avremo sottratto ogni caso in cui due variabili superano $40$ due volte, una per ogni modo di designare una di queste due variabili come variabile che eccede $40$. Vogliamo solo sottrarre tali casi una volta, quindi dobbiamo aggiungerli al totale.
Due variabili superano $40$: Ci sono $\binom{3}{2}$ modi per selezionare quali due variabili superano $40$. Supponiamo che lo siano$x_1$ e $x_2$. Poi$x_1' = x_1 - 41$ e $x_2' = x_2 - 41$sono numeri interi non negativi. Sostituzione$x_1' + 41$ per $x_1$ e $x_2' + 41$ per $x_2$ nell'equazione 1 si ottiene \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} L'equazione 3 è un'equazione negli interi non negativi con $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$soluzioni. Quindi, ci sono$$\binom{3}{2}\binom{20}{2}$$ soluzioni in cui due variabili superano $40$.
Pertanto, in base al principio di inclusione-esclusione, il numero di soluzioni dell'equazione 1 in cui nessuna variabile supera $40$ è $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ come hai trovato.
$\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}$ Di $\ds{\ \underline{definition}}$, la risposta è data da: \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}