Perguntas relacionadas ao princípio de inclusão-exclusão

Question

Hoje me deparei com o princípio de inclusão-exclusão pela primeira vez. Acredito ter entendido, no entanto, quando tentei resolver algumas questões sobre isso, fiquei muito preso. Não consegui resolver nenhum deles. Você poderia sugerir algumas questões de dificuldade crescente, para que eu possa ter uma boa compreensão do tópico em questão? Uma das perguntas é esta:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement Estava em um livro grego de competição de matemática e também o encontrei neste site.

A outra pergunta não consegui encontrar na internet, então vou traduzir:

Encontre o número de soluções para a equação $x_1+x_2+x_3=100$, se para cada $3\ge i\ge1$, xi é um número inteiro não negativo com $40\ge x_i$.

Eu encontrei as soluções para ambas as questões, a razão pela qual estou postando-as também, é dar um melhor entendimento ao leitor da postagem (como apontado nos comentários), de qual nível de perguntas na inclusão princípio de exclusão está me dando dificuldade

Answer 1

A segunda pergunta, traduzida, não precisa realmente de inclusão-exclusão; é facilmente feito usandohttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), que é outra técnica que vale a pena aprender (se você ainda não tiver feito isso):

Vamos escrever $u_i=40-x_i$, de modo que a restrição é $u_i\ge0$e, em seguida, reescrever a equação para resolver como

$$u_1+u_2+u_3=20$$

(Isso vem de $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$e, em seguida, movendo as coisas.) Estrelas e barras agora indicam o número de triplos não negativos somando $20$ é

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

Para ser honesto, acho que seria difícil resolver esse problema usando inclusão-exclusão; Eu mesmo estaria interessado em ver se há uma maneira fácil de fazer isso.

Answer 2

Aqui está a abordagem de inclusão-exclusão para o segundo problema, onde $k$ é o número de $i\in\{1,2,3\}$ com $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 {align} O$$\binom{100-41k+3-1}{3-1}$$ parte vem de uma contagem de estrelas e barras das soluções inteiras não negativas para $x_1+x_2+x_3=100$ com $x_i \ge 41$ para $k$ Especificadas $i\in\{1,2,3\}$, equivalentemente, as soluções inteiras não negativas para $y_1+y_2+y_3=100-41k$.