Jumlah kombinasi yang $x_1+x_2+x_3=100$ jika untuk setiap $3\ge i\ge 1$, $x_i$ adalah bilangan bulat non negatif dengan $40\ge x_i$
Saya baru-baru ini menemukan pertanyaan berikut:
Temukan jumlah kombinasinya $x_1+x_2+x_3=100$ jika untuk setiap $3\ge i\ge 1$, $x_i$ adalah bilangan bulat non negatif dengan $40\ge xi$.
Saya menyelesaikannya dengan cara berikut, membaginya menjadi beberapa contoh berbeda
Jika $x_1=20$: 1 solusi ($x_2=40, x_3=40$)
Jika $x_1=21$: 2 solusi
Jika $x_1=22$: 3 solusi
$\ldots$
Jika $x_1=40$: 21 solusi
Karena total yang dihasilkan adalah penjumlahan dari perkembangan aritmatika, kita punya $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
Saya menemukan pertanyaan ini di bab yang berkaitan dengan prinsip inklusi-eksklusi, namun saya tidak dapat memikirkan cara menyelesaikannya menggunakan prinsip pengecualian inklusi. Bisakah seseorang menunjukkan kepada saya solusi yang tepat untuk pertanyaan ini dengan menggunakan prinsip inklusi-pengecualian, juga menjelaskan bagaimana dia secara intuitif berpikir untuk melanjutkan ke setiap langkah?
Jawaban
Solusi persamaan tertentu $$x_1 + x_2 + x_3 = 100 \tag{1}$$ sesuai dengan penempatan $3 - 1 = 2$ tanda tambahan di deretan $100$satu. Misalnya, jika kita menempatkan tanda penjumlahan setelah$20$th dan $60$Yang pertama, kami mendapatkan solusinya $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (hitung jumlah satu di sebelah kiri tanda penjumlahan pertama untuk nilai $x_1$, di antara dua tanda penjumlahan untuk nilai $x_2$, dan di sebelah kanan kedua tanda penjumlahan untuk nilai $x_3$). Oleh karena itu, jumlah solusi dari persamaan dalam bilangan bulat nonnegatif adalah$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ karena kita harus memilih dua dari $102$ posisi yang dibutuhkan untuk $100$ satu dan dua tanda penjumlahan akan diisi dengan tanda penjumlahan.
Dari sini, kita harus mengurangi kasus-kasus di mana satu atau lebih variabel melebihi $40$.
Variabel melebihi $40$: Ada tiga cara untuk memilih variabel mana yang melebihi $40$. Misalkan itu$x_1$. Kemudian$x_1' = x_1 - 41$adalah bilangan bulat nonnegatif. Mengganti$x_1' + 41$ untuk $x_1$ dalam persamaan 1 menghasilkan \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} Persamaan 2 adalah persamaan dalam bilangan bulat nonnegatif dengan $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$solusi. Karenanya, ada$$\binom{3}{1}\binom{61}{2}$$ solusi di mana nilai variabel melebihi $40$.
Namun, jika kita mengurangi jumlah ini dari total, kita akan mengurangkan setiap kasus yang melebihi dua variabel $40$ dua kali, sekali untuk setiap cara menunjuk salah satu dari dua variabel tersebut sebagai variabel yang melebihi $40$. Kami hanya ingin mengurangi kasus seperti itu satu kali, jadi kami harus menambahkannya ke total.
Dua variabel melebihi $40$: Ada $\binom{3}{2}$ cara untuk memilih dua variabel yang melebihi $40$. Misalkan mereka$x_1$ dan $x_2$. Kemudian$x_1' = x_1 - 41$ dan $x_2' = x_2 - 41$adalah bilangan bulat nonnegatif. Mengganti$x_1' + 41$ untuk $x_1$ dan $x_2' + 41$ untuk $x_2$ dalam persamaan 1 menghasilkan \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} Persamaan 3 adalah persamaan dalam bilangan bulat nonnegatif dengan $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$solusi. Karenanya, ada$$\binom{3}{2}\binom{20}{2}$$ solusi di mana dua variabel melebihi $40$.
Jadi, dengan Prinsip Inklusi-Pengecualian, jumlah solusi dari persamaan 1 di mana tidak ada variabel yang melebihi $40$ adalah $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ seperti yang Anda temukan.
$\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}$ Oleh $\ds{\ \underline{definition}}$, jawabannya diberikan oleh: \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}