Inclusao e exclusao exerc

Prévia do material em texto

MATEMÁTICA DISCRETA
SEGUNDO SEM. 2011
UNICAMP
Princípio Multiplicativo
MA220
Prof. Stefano De Leo
Princípio da Inclusão e Exclusão
◦ Usando
N(A ∪B) = N(A) +N(B)−N(A ∩B) (1)
N(A ∪B ∪ C) = N(A) +N(B) +N(C)−N(A ∩B)−N(A ∩ C)−N(B ∩ C) +N(A ∩B ∩ C) (2)
encontre a expressão para N(A ∪B ∪ C ∪D).
• N(A ∪B ∪ C ∪D) = N(A∗ ∪D) com A∗ = A ∪B ∪ C. Usando (1) temos
N(A ∪B ∪ C ∪D) = N(A∗) +N(D)−N(A∗ ∩D) .
Usando (2) e observando que
A∗ ∩D = (A ∪B ∪ C) ∩D = (A ∩D) ∪ (B ∩D) ∪ (C ∩D) ,
temos
N(A ∪B ∪ C ∪D) = N(A) +N(B) +N(C) +N(D)
−N(A ∩B)−N(A ∩ C)−N(B ∩ C) +N(A ∩B ∩ C)
−N [(A ∩D) ∪ (B ∩D) ∪ (C ∩D)] .
Usando novamente a (2) temos
N [(A ∩D) ∪ (B ∩D) ∪ (C ∩D)] = N(A ∩D) +N(B ∩D) +N(C ∩D)
−N [(A ∩D) ∩ (B ∩D)]−N [(A ∩D) ∩ (C ∩D)]−N [(B ∩D) ∩ (C ∩D)]
+N [(A ∩D) ∩ (B ∩D) ∩ (C ∩D)] ,
então
N(A ∪B ∪ C ∪D) = N(A) +N(B) +N(C) +N(D)
−N(A ∩B)−N(A ∩ C)−N(A ∩D)−N(B ∩ C)−N(B ∩D)−N(C ∩D)
+N(A ∩B ∩ C) +N(A ∩ C ∩D) +N(A ∩B ∩D) +N(B ∩ C ∩D)
−N(A ∩B ∩ C ∩D) .
◦ Encontrar o número de soluções, em inteiros, de
y1 + y2 + y3 + y4 = 22
em que 5 ≤ y1 ≤ 7, 4 ≤ y2 ≤ 6, 1 ≤ y3 ≤ 4 and y4 ≥ 5.
• Mudança de variáveis de yn a xn (interios positivos):
y1 = x1 + 4 (x1 ≤ 3) , y2 = x2 + 3 (x2 ≤ 3) , y3 = x3 (x3 ≤ 4) , y4 = x4 + 4 .
x1 + x2 + x3 + x4 = 22− 4− 3− 4 = 11
TOT : 10! / 3! 7! = 120
A(> 3) : 11-3-1 ⇒ 7! / 3! 4! = 35
B(> 3) : 11-3-1 ⇒ 7! / 3! 4! = 35
C(> 4) : 11-4-1 ⇒ 6! / 3! 3! = 20
AB(> 3, > 3) : 11-3-3-1 ⇒ 4! / 3! 1! = 4
AC(> 3, > 4) : 11-3-4-1 ⇒ 3! / 3! 0! = 1
BC(> 3, > 4) : 11-3-4-1 ⇒ 3! / 3! 0! = 1
N(A ∪B ∪ C) = 35+35+20-4-1-1 = 84
Res: 120 - 84 =36