조합 수 $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$일, 우리는 해결책을 얻습니다 $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}