Các câu hỏi liên quan đến nguyên tắc loại trừ bao gồm

Question

Hôm nay, lần đầu tiên tôi biết đến nguyên tắc loại trừ bao gồm. Tôi tin rằng tôi đã hiểu nó, tuy nhiên khi tôi cố gắng giải quyết một số câu hỏi về nó, tôi đã bị mắc kẹt nghiêm trọng. Tôi không thể giải quyết bất kỳ ai trong số họ. Bạn có thể vui lòng gợi ý một số câu hỏi về độ khó tăng dần để tôi có thể nắm bắt được chủ đề trong tầm tay được không? Một trong những câu hỏi là câu hỏi này:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , Nó nằm trong một cuốn sách toán học về cuộc thi của Hy Lạp và tôi cũng tìm thấy nó trên trang web này.

Một câu hỏi khác mà tôi không thể tìm thấy trên internet, vì vậy tôi sẽ dịch nó:

Tìm số nghiệm của phương trình $x_1+x_2+x_3=100$, nếu cho mọi $3\ge i\ge1$, xi là một số nguyên không âm với $40\ge x_i$.

Tôi đã tìm ra giải pháp cho cả hai câu hỏi này, lý do mà tôi đăng chúng cũng là để giúp người đọc bài viết hiểu rõ hơn (như đã chỉ ra trong phần bình luận), mức độ câu hỏi được đưa vào- nguyên tắc loại trừ đang gây khó khăn cho tôi

Answer 1

Câu hỏi thứ hai, đã dịch, không thực sự cần loại trừ bao gồm; nó khá dễ dàng thực hiện bằng cách sử dụnghttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), đó là một kỹ thuật khác rất đáng học hỏi (nếu bạn chưa làm như vậy):

Cùng viết nào $u_i=40-x_i$, do đó hạn chế là $u_i\ge0$và sau đó viết lại phương trình để giải thành

$$u_1+u_2+u_3=20$$

(Điều này đến từ $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$và sau đó di chuyển mọi thứ xung quanh.) Các dấu sao và thanh giờ đây cho biết số lượng bộ ba không âm cộng lại thành $20$ Là

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

Thành thật mà nói, tôi nghĩ rằng tôi sẽ gặp khó khăn khi giải quyết vấn đề này bằng cách sử dụng loại trừ bao gồm; Bản thân tôi muốn biết xem có cách nào dễ dàng để làm như vậy không.

Answer 2

Đây là cách tiếp cận loại trừ bao gồm cho vấn đề thứ hai, trong đó $k$ là số $i\in\{1,2,3\}$ với $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 {red} { 231}. \ end {class} Các$$\binom{100-41k+3-1}{3-1}$$ một phần đến từ số sao-và-vạch của các nghiệm nguyên không âm để $x_1+x_2+x_3=100$ với $x_i \ge 41$ cho $k$ chỉ định $i\in\{1,2,3\}$, tương đương, các giải pháp số nguyên không âm cho $y_1+y_2+y_3=100-41k$.