組み合わせの数 $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$thと $60$これらは、解決策を取得します $x_1 = 20$、 $x_2 = 40$、 $x_3 = 40$ （の値の最初の加算記号の左側にあるものの数を数えます $x_1$、の値の2つの加算記号の間 $x_2$、およびの値の両方の加算記号の右側 $x_3$）。したがって、非負の整数の方程式の解の数は次のようになります。$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ どちらを選択する必要があるので $102$ に必要な位置 $100$ 1つと2つの追加記号は追加記号で埋められます。
これらから、1つ以上の変数がを超えるケースを差し引く必要があります $40$。
変数がを超える $40$：どの変数が超過するかを選択する3つの方法があります $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$。
ただし、この金額を合計から差し引くと、2つの変数が超過する各ケースが差し引かれます。 $40$ 2回、これら2つの変数の1つをを超える変数として指定する方法ごとに1回 $40$。そのような場合は一度だけ減算したいので、合計に加算する必要があります。
2つの変数が $40$： がある $\binom{3}{2}$ 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}$$ 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}