Hangi kombinasyonların sayısı $x_1+x_2+x_3=100$ her biri için $3\ge i\ge 1$, $x_i$ negatif olmayan bir tamsayıdır $40\ge x_i$
Geçenlerde şu soruyla karşılaştım:
Hangi kombinasyonların sayısını bulun $x_1+x_2+x_3=100$ her biri için $3\ge i\ge 1$, $x_i$ negatif olmayan bir tamsayıdır $40\ge xi$.
Bunu şu şekilde çözdüm, farklı örneklere böldüm
Eğer $x_1=20$: 1 çözüm ($x_2=40, x_3=40$)
Eğer $x_1=21$: 2 çözüm
Eğer $x_1=22$: 3 çözüm
$\ldots$
Eğer $x_1=40$: 21 çözüm
Ortaya çıkan toplam, bir aritmetik ilerlemenin eklenmesi olduğundan, elimizde $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
Bu soruyu dahil etme-hariç tutma ilkesiyle ilgili bir bölümde buldum, ancak dahil etme hariç tutma ilkesini kullanarak nasıl çözeceğimi düşünemiyorum. Lütfen birisi bana bu sorunun net bir çözümünü dahil etme-dışlama ilkesini kullanarak gösterebilir ve sezgisel olarak her adıma nasıl devam etmeyi düşündüğünü açıklayabilir mi?
Yanıtlar
Denklemin belirli bir çözümü $$x_1 + x_2 + x_3 = 100 \tag{1}$$ yerleşimine karşılık gelir $3 - 1 = 2$ üst üste toplama işaretleri $100$olanlar. Örneğin, toplama işaretlerini$20$inci ve $60$onlar, çözümü elde ederiz $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (değeri için ilk toplama işaretinin solundaki sayıları sayın $x_1$değeri için iki toplama işareti arasında $x_2$ve değeri için her iki toplama işaretinin sağında $x_3$). Bu nedenle, denklemin negatif olmayan tamsayılardaki çözüm sayısı$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ çünkü hangisini seçmeliyiz $102$ için gerekli pozisyonlar $100$ Birler ve iki ekleme işareti, ilave işaretleri ile doldurulacaktır.
Bunlardan bir veya daha fazla değişkenin aştığı durumları çıkarmalıyız. $40$.
Bir değişken aşıyor $40$: Hangi değişkeni aştığını seçmenin üç yolu vardır: $40$. Varsayalım ki$x_1$. Sonra$x_1' = x_1 - 41$negatif olmayan bir tamsayıdır. İkame$x_1' + 41$ için $x_1$ denklem 1'de verim \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} Denklem 2, negatif olmayan tam sayılarda bir denklemdir. $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$çözümler. Dolayısıyla var$$\binom{3}{1}\binom{61}{2}$$ bir değişkenin değerinin aştığı çözümler $40$.
Ancak, bu miktarı toplamdan çıkarırsak, iki değişkenin aştığı her durumu çıkarmış oluruz. $40$ bu iki değişkenden birini aşan değişken olarak atamanın her yolu için iki kez, bir kez $40$. Bu tür durumları yalnızca bir kez çıkarmak istiyoruz, bu nedenle bunları toplama eklemeliyiz.
İki değişken aşıyor $40$: Var $\binom{3}{2}$ hangi iki değişkeni aştığını seçme yolları $40$. Varsayalım ki$x_1$ ve $x_2$. Sonra$x_1' = x_1 - 41$ ve $x_2' = x_2 - 41$negatif olmayan tam sayılardır. İkame$x_1' + 41$ için $x_1$ ve $x_2' + 41$ için $x_2$ denklem 1'de verim \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} Denklem 3, negatif olmayan tam sayılarda bir denklemdir. $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$çözümler. Dolayısıyla var$$\binom{3}{2}\binom{20}{2}$$ iki değişkenin aştığı çözümler $40$.
Böylece, Dahil Etme-Dışlama İlkesine göre, hiçbir değişkenin aşmadığı denklem 1'in çözüm sayısı $40$ dır-dir $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ bulduğunuz gibi.
$\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}$ Tarafından $\ds{\ \underline{definition}}$cevap şu şekilde verilir: \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}