Количество комбинаций, для которых $x_1+x_2+x_3=100$ если для каждого $3\ge i\ge 1$, $x_i$ неотрицательное целое число с $40\ge x_i$
Недавно я столкнулся со следующим вопросом:
Найдите количество комбинаций, для которых $x_1+x_2+x_3=100$ если для каждого $3\ge i\ge 1$, $x_i$ неотрицательное целое число с $40\ge xi$.
Я решил это следующим образом, разбив на разные экземпляры
Если $x_1=20$: 1 раствор ($x_2=40, x_3=40$)
Если $x_1=21$: 2 решения
Если $x_1=22$: 3 решения
$\ldots$
Если $x_1=40$: 21 решение
Поскольку итоговая сумма складывается из арифметической прогрессии, мы имеем $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
Я нашел этот вопрос в главе, посвященной принципу включения-исключения, однако я не могу придумать, как его решить, используя принцип исключения включения. Не мог бы кто-нибудь показать мне изящное решение этого вопроса с использованием принципа включения-исключения, объясняя также, как он интуитивно думал о переходе к каждому шагу?
Ответы
Частное решение уравнения $$x_1 + x_2 + x_3 = 100 \tag{1}$$ соответствует размещению $3 - 1 = 2$ знаки сложения в ряду $100$ед. Например, если мы поместим знаки сложения после$20$й и $60$th, получаем решение $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (подсчитайте количество единиц слева от первого знака сложения для значения $x_1$, между двумя знаками сложения для значения $x_2$, а справа от обоих знаков сложения значения $x_3$). Следовательно, количество решений уравнения в целых неотрицательных числах равно$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ поскольку мы должны выбрать, какие два из $102$ должности, необходимые для $100$ один и два знака сложения будут заполнены знаками сложения.
Из них мы должны вычесть те случаи, когда одна или несколько переменных превышают $40$.
Переменная превышает $40$: Есть три способа выбрать, какая переменная превышает $40$. Предположим, это$x_1$. потом$x_1' = x_1 - 41$является целым неотрицательным числом. Подстановка$x_1' + 41$ за $x_1$ в уравнении 1 дает \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} Уравнение 2 представляет собой уравнение в неотрицательных целых числах с $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$решения. Следовательно, есть$$\binom{3}{1}\binom{61}{2}$$ решения, в которых значение переменной превышает $40$.
Однако, если мы вычтем эту сумму из общей суммы, мы вычтем каждый случай, когда две переменные превышают $40$ дважды, по одному разу для каждого способа обозначения одной из этих двух переменных как переменной, превышающей $40$. Мы хотим вычесть такие случаи только один раз, поэтому мы должны добавить их к общей сумме.
Две переменные превышают $40$: Есть $\binom{3}{2}$ способы выбрать, какие две переменные превышают $40$. Предположим, они$x_1$ и $x_2$. потом$x_1' = x_1 - 41$ и $x_2' = x_2 - 41$неотрицательные целые числа. Подстановка$x_1' + 41$ за $x_1$ и $x_2' + 41$ за $x_2$ в уравнении 1 дает \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} Уравнение 3 представляет собой уравнение в неотрицательных целых числах с $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$решения. Следовательно, есть$$\binom{3}{2}\binom{20}{2}$$ решения, в которых две переменные превосходят $40$.
Таким образом, согласно принципу включения-исключения, количество решений уравнения 1, в котором ни одна переменная не превышает $40$ является $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ как вы нашли.
$\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}$ По $\ds{\ \underline{definition}}$, ответ дает: \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}