Pertanyaan yang berkaitan dengan prinsip inklusi-eksklusi

Question

Hari ini saya menemukan prinsip inklusi-pengecualian untuk pertama kalinya. Saya yakin saya telah memahaminya, namun ketika saya mencoba memecahkan beberapa pertanyaan tentangnya, saya sangat terhambat. Saya tidak bisa menyelesaikan satu pun dari mereka. Bisakah Anda menyarankan beberapa pertanyaan dengan kesulitan yang meningkat, sehingga saya bisa memahami topik yang sedang dibahas? Salah satu pertanyaannya adalah yang ini:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , Itu ada di buku kontes matematika Yunani dan saya juga menemukannya di situs ini.

Pertanyaan lain yang tidak dapat saya temukan di internet, jadi saya akan menerjemahkannya:

Temukan jumlah penyelesaian persamaan $x_1+x_2+x_3=100$, jika untuk setiap $3\ge i\ge1$, xi adalah bilangan bulat bukan negatif dengan $40\ge x_i$.

Saya telah menemukan solusi untuk kedua pertanyaan ini, alasan saya mempostingnya juga, adalah untuk memberikan pemahaman yang lebih baik kepada pembaca posting (seperti yang ditunjukkan dalam komentar), tentang tingkat pertanyaan apa dalam inklusi- prinsip pengecualian memberi saya kesulitan

Answer 1

Pertanyaan kedua, diterjemahkan, tidak benar-benar membutuhkan inklusi-eksklusi; itu cukup mudah dilakukan dengan menggunakanhttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), yang merupakan teknik lain yang layak dipelajari (jika Anda belum melakukannya):

Mari menulis $u_i=40-x_i$, sehingga batasannya adalah $u_i\ge0$, lalu tulis ulang persamaan tersebut untuk diselesaikan sebagai

$$u_1+u_2+u_3=20$$

(Ini berasal dari $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$, dan kemudian memindahkan barang-barang.) Bintang dan batang sekarang menunjukkan jumlah tripel non-negatif yang dijumlahkan $20$ adalah

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

Sejujurnya, saya pikir saya akan kesulitan memecahkan masalah ini menggunakan inklusi-pengecualian; Saya sendiri tertarik untuk melihat apakah ada cara mudah untuk melakukannya.

Answer 2

Inilah pendekatan inklusi-eksklusi untuk masalah kedua, di mana $k$ adalah jumlah $i\in\{1,2,3\}$ dengan $x_i \ge 41$: \ begin {align} \ 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 {merah} { 231}. \ end {align} The$$\binom{100-41k+3-1}{3-1}$$ bagian berasal dari hitungan bintang-dan-batang dari solusi integer nonnegatif untuk $x_1+x_2+x_3=100$ dengan $x_i \ge 41$ untuk $k$ ditentukan $i\in\{1,2,3\}$, ekuivalen, solusi integer nonnegatif untuk $y_1+y_2+y_3=100-41k$.