Denklemli Dahil Etme-Dışlama Problemi

Question

Sorun:

$x_1+x_2+x_3+x_4 = 22$. Orada kaç çözüm var$x_i$s negatif olmayan tam sayılardır ve $1<x_1<7$, $3\leq x_2 \leq 5$, $x_3 \leq 7$, $1<x_4\leq 13$?

Benim işim: $y_1+y_2+y_3+y_4 = 15$

$y_1<5, y_2<3, y_3<8, y_4<12$

$x_1 = y_1+2, x_2=y_2+3, x_3=y_3,x_4=y_4+2$

Sahip olduğumuz üst sınırları görmezden gelmek $C(15+4-1,15)=816$

Çözümler ne zaman $y_1 \geq 5, y_2\geq 0, y_3\geq 0, y_4 \geq 0$

$(y_1-5) + y_2 + y_3 + y_4 = 10$

$C(10+4-1,10) = 286$

Çözümler ne zaman $y_1 \geq 0, y_2 \geq 3, y_3 \geq 0, y_4 \geq 0$

$y_1 + y_2-3 + y_3 + y_4 = 12$

$C(12+4-1,12) = 455$

Çözümler ne zaman $y_1 \geq 0, y_2 \geq 0, y_3 \geq 8,y_4 \geq 0$

$y_1 + y_2 + y_3-8 + y_4 = 7$

$C(7+4-1,7) = 120$

Çözümler ne zaman $y_1 \geq 0, y_2 \geq 0, y_3 \geq 0, y_4 \geq 12$

$y_1 + y_2 + y_3 + y_4-12 = 3$

$C(3+4-1,3) = 20$

$816-286-455-120-20 = -65$

Bu yüzden yukarıdaki adımlardan bazılarına başladım. Bunu doğru yapıp yapmadığımı ve neyi eksik saydığımı nasıl hesaplayacağıma dair sonraki adımın ne olduğunu merak ediyorum çünkü$-65$ Açıkçası o cevap vermiyor.

Answer 1

Problemi doğru şekilde denklemin çözüm sayısını bulmaya indirgendiniz $$y_1 + y_2 + y_3 + y_4 = 15 \tag{1}$$ kısıtlamalara tabi $y_1 < 5, y_2 < 3, y_3 < 8, y_4 < 12$.

İzin Vermek $A_1$ hangi sonuç kümesini ifade eder? $y_1 \geq 5$, $A_2$ hangi sonuç kümesini ifade eder? $y_2 \geq 3$, $A_3$ hangi sonuç kümesini ifade eder? $y_3 \geq 8$, ve $A_4$ hangi sonuç kümesini ifade eder? $y_4 \geq 12$. Dahil Etme-Hariç Tutma İlkesine göre, bu kısıtlamalardan en az birinin ihlal edildiği çözümlerin sayısı denklem 1'deki çözümlerin sayısından çıkarılarak, hiçbir kısıtlamanın ihlal edilmediği sonuçların sayısı bulunur.

Doğru bir şekilde denklem 1'in çözüm sayısının $$\binom{15 + 4 - 1}{4 - 1} = \binom{18}{3} = \binom{18}{15}$$ ve şu \begin{align*} |A_1| & = \binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = \binom{13}{10}\\ |A_2| & = \binom{12 + 4 - 1}{4 - 1} = \binom{15}{3} = \binom{15}{12}\\ |A_3| & = \binom{7 + 4 - 1}{4 - 1} = \binom{10}{3} = \binom{10}{7}\\ |A_4| & = \binom{3 + 4 - 1}{4 - 1} = \binom{6}{3} \end{align*}Olumsuz bir yanıt almanızın nedeni, iki kısıtlamanın iki kez ihlal edildiği her durumu, her bir şekilde kısıtlamalardan birini ihlal edilen kısıtlama olarak belirlemiş olmanızdır. Bu tür durumları yalnızca bir kez çıkarmak istiyoruz, bu nedenle bunları toplama eklemeliyiz. Aslında, Dahil Etme-Dışlama İlkesine göre , en az bir koşulun ihlal edildiği çözümlerin sayısı\begin{align*} & |A_1 \cup A_2 \cup A_3 \cup A_4|\\ & \quad = |A_1| + |A_2| + |A_3| + |A_4|\\ & \qquad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_3| - |A_2 \cap A_4| - |A_3 \cap A_4|\\ & \quad \qquad + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\\ & \qquad \qquad - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{align*}

Bu terimlerin çoğunun sıfıra eşit olduğuna dikkat edin. Örneğin, mümkün değil$y_1 \geq 5$ ve $y_2 \geq 12$ dan beri $5 + 12 > 15$.

Hesaplayalım $|A_1 \cap A_2|$. Kalan dönemlerin hesaplamalarını size bırakacağım.

$|A_1 \cap A_2|$: Sonra $y_1 \geq 5$ ve $y_2 \geq 3$. İzin Vermek$y_1' = y_1 - 5$ ve $y_2' = y_2 - 3$. Sonra$y_1'$ ve $y_2'$negatif olmayan tam sayılardır. İkame$y_1' + 4$ için $y_1$ ve $y_2' + 3$ için $y_2$ denklem 1'de verim \begin{align*} y_1' + 5 + y_2' + 3 + y_3 + y_4 & = 15\\ y_1' + y_2' + y_3 + y_4 & = 7 \tag{2} \end{align*} Denklem 2, negatif olmayan tam sayılarda bir denklemdir.

$$\binom{7 + 4 - 1}{4 - 1} = \binom{10}{3} = \binom{10}{7}$$

çözümler.