Dahil etme-hariç tutma ilkesiyle ilgili sorular

Aug 17 2020

Bugün dahil etme-dışlama ilkesiyle ilk kez karşılaştım. Anladığıma inanıyorum, ancak bazı soruları çözmeye çalıştığımda, ciddi şekilde takılıp kaldım. Hiçbirini çözemedim. Elimizdeki konuyu iyi bir şekilde anlayabilmem için artan zorluklarla ilgili bazı sorular önerebilir misiniz? Sorulardan biri şudur:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , Bir Yunan yarışması matematik kitabındaydı ve ben de bu sitede buldum.

Diğer soruyu internette bulamadım, bu yüzden çevireceğim:

Denklemin çözüm sayısını bulun $x_1+x_2+x_3=100$her biri için $3\ge i\ge1$, xi, negatif olmayan bir tam sayıdır $40\ge x_i$.

Bu soruların her ikisine de çözüm buldum, onları da göndermemin nedeni, yazının okuyucusuna (yorumlarda belirtildiği gibi), dahil edilen soruların düzeyini daha iyi anlamaktır. dışlama ilkesi beni zorlaştırıyor

Yanıtlar

1 BarryCipra Aug 24 2020 at 03:13

İkincisi, çevrilmiş soru gerçekten dahil etme-dışlama gerektirmez; kullanarak oldukça kolayhttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), öğrenmeye değer başka bir teknik olan (henüz yapmadıysanız):

Hadi yaz $u_i=40-x_i$, böylece kısıtlama $u_i\ge0$ve sonra çözmek için denklemi yeniden yazın

$$u_1+u_2+u_3=20$$

(Bu geliyor $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$ve sonra bir şeyler hareket ettirin.) Yıldızlar ve çubuklar artık negatif olmayan üçlülerin sayısını gösteriyor $20$ dır-dir

$${22\choose2}={22\cdot21\over2}=231$$

Dürüst olmak gerekirse, dahil etme-dışlama kullanarak bu sorunu çözmekte zorlanacağımı düşünüyorum; Bunu yapmanın kolay bir yolu olup olmadığını görmek isterim.

1 RobPratt Aug 24 2020 at 04:31

İşte ikinci problem için dahil etme-hariç tutma yaklaşımı, burada $k$ sayısı $i\in\{1,2,3\}$ ile $x_i \ge 41$: \ başla {hizala} \ sum_ {k = 0} ^ 2 (-1) ^ k \ binom {3} {k} \ binom {100-41k + 3-1} {3-1} & = \ binom { 102} {2} -3 \ binom {61} {2} +3 \ binom {20} {2} \\ & = 5151-3 \ cdot 1830 + 3 \ cdot 190 \\ & = \ color {kırmızı} { 231}. \ ucu {hizalama}$$\binom{100-41k+3-1}{3-1}$$ kısmı, negatif olmayan tamsayı çözümlerinin yıldız ve çubuk sayısından gelir. $x_1+x_2+x_3=100$ ile $x_i \ge 41$ için $k$ belirtildi $i\in\{1,2,3\}$, eşdeğer olarak, negatif olmayan tamsayı çözümleri $y_1+y_2+y_3=100-41k$.