Вопросы, касающиеся принципа включения-исключения

Question

Сегодня я впервые столкнулся с принципом включения-исключения. Я считаю, что понял это, однако, когда я попытался решить некоторые вопросы по нему, я сильно застрял. Я не мог решить ни одну из них. Не могли бы вы предложить несколько вопросов по нарастающей сложности, чтобы я мог лучше разобраться в обсуждаемой теме? Один из вопросов такой:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , Это было в греческом учебнике по математике, и я тоже нашел его на этом сайте.

Другой вопрос, который я не нашел в Интернете, поэтому переведу:

Найдите количество решений уравнения $x_1+x_2+x_3=100$, если для каждого $3\ge i\ge1$, xi - неотрицательное целое число с $40\ge x_i$.

Я нашел решения обоих этих вопросов, причина, по которой я их также публикую, состоит в том, чтобы дать читателю сообщения (как указано в комментариях) лучшее понимание того, какой уровень вопросов во включении - Принцип исключения доставляет мне трудности

Answer 1

Второй, переведенный, вопрос на самом деле не требует включения-исключения; это довольно легко сделать, используяhttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), это еще один метод, который стоит изучить (если вы еще этого не сделали):

Давайте напишем $u_i=40-x_i$, так что ограничение $u_i\ge0$, а затем перепишите уравнение, чтобы решить его как

$$u_1+u_2+u_3=20$$

(Это происходит от $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$, а затем перемещать вещи.) Звездочки и столбцы теперь показывают количество неотрицательных троек, суммируемых $20$ является

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

Если честно, я думаю, мне было бы сложно решить эту проблему с помощью включения-исключения; Мне было бы интересно узнать, есть ли простой способ сделать это.

Answer 2

Вот подход включения-исключения для второй проблемы, где $k$ это количество $i\in\{1,2,3\}$ с участием $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}. \ конец {Выравнивание}$$\binom{100-41k+3-1}{3-1}$$ часть исходит из количества звезд и столбцов неотрицательных целочисленных решений для $x_1+x_2+x_3=100$ с участием $x_i \ge 41$ за $k$ указан $i\in\{1,2,3\}$, что эквивалентно, неотрицательные целочисленные решения $y_1+y_2+y_3=100-41k$.