Slide - O Princípio da Inclusão-exclusão - 2022-1

O Princ´ıpio da Inclus˜ao-Exclus˜ao Jeroen van de Graaf DCC - UFMG 2022/01 An´alise Combinat´oria O PRINC´IPIO DA INCLUS˜AO-EXCLUS˜AO O Princ´ıpio da Inclus˜ao-Exclus˜ao – n = 2 Sabemos que |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2| Prova Na soma |A1| + |A2|, os elementos de |A1| ∩ |A2| s˜ao contados duas vezes. O Princ´ıpio da Inclus˜ao-Exclus˜ao – n = 2 Exemplo 7.5.2 Quantos inteiros no [1, 1000] s˜ao divis´ıveis por 7 ou 11? Para facilitar vamos usar a seguinte nota¸c˜ao, onde a∪ = |A1 ∪ A2|; ai = |Ai|; a12 = |A1 ∩ A2|. Obtemos ent˜ao a∪ = a1 + a2 − a12 Inteiros divis´ıveis por 7: a1 = ⌊ 1000 7 ⌋ = 142. Inteiros divis´ıveis por 11: a2 = ⌊ 1000 11 ⌋ = 90. Inteiros divis´ıveis por 7 e 11: a12 = ⌊ 1000 77 ⌋ = 12. Inteiros divis´ıveis por 7 ou 11: a∪ = a1 + a2 − a12 = 142 + 90 − 12 = 220. O Principio da Inclusao-Exclusao — n = 3 Para 3 conjuntos a férmula é |A1 U Az U A3| = |Ai| + |A2| + |A3| — |A1 9 A2| — |A1 9 As] — |A2 9 As] + |Ar 9 Az A3| ——_—— SSF OS. An eae Su Sy So S3 onde S, é cardinalidade somada das intersecdes de k conjuntos. O Princ´ıpio da Inclus˜ao-Exclus˜ao – n = 3 Exemplo 7.5.4 1232 alunos cursam espanhol, 879 corsam francˆes, 114 cursam russo. Ainda, 103 cursam E e F, 23 cursam E e R, 14 cursam F e R. H´a 2092 alunos, Quantos cursam E, F e R? Reposta Usaremos a seguinte f´ormula: S∪ = S1 − S2 + S3 Substituindo os termos: S∪ = 2092 S1 = N(E) + N(F) + N(R) = 1232 + 879 + 114 S2 = N(EF) + N(ER) + N(FR) = 103 + 23 + 14 S3 = N(EFR) ´e o valor procurado Ent˜ao 2092 = 1232 + 879 + 114 − 103 − 23 − 14 + S3 implicando que S3 = 7. O Principio da Inclusao-Exclusao — n qualquer Teorema So = S$,-54+ 83 —+--4+(-1)""'S, onde Su = |Ai U Ap U--- UA, | Si = Vi NAi = |Ai| + |A2| + |As| +++ + [An S2 = Vie; |Ain Ai = |At2| + |Ais] + +++ + [A(n—1)n $3 = Vicjcn AINA) OAK! = |Atza| + |Atzal + +++ + —|A(n—2)(n—1)n Sn = |Ar3...n| e onde Ai2 = Ai N A2; Aiz3 = Ar N A2 MN A3; etc (O livro nado usa essa nota¢do nem usa S;, mas é muito conveniente.) O Principio da Inclusao-Exclusao — n qualquer Prova Vamos verificar que um elemento x arbitrario que pertence a r dos conjuntos Aj, Ao,..., An contribui exatemente 1 ao lado direito da equa¢ao. Repare que — x € contado (1) vezes no $1; — x € contado () vezes no So; — x é contado (3) vezes no $3, etc. Em geral, x é contado (") vezes no Sm, 0 somatério envolvendo m conjuntos A;. Entao, x contribui r r r aif _ + —..-+(-1) ao lado direito da equacdo. Vamos mostrar que essa soma 6 1. O Principio da Inclusao-Exclusao — n qualquer Trocando para coeficientes binomiais r r r raifr lembramos que r r r r(r\ _ Portanto r\_fr\_ fr ry _4yyt fo) O Princ´ıpio da Inclus˜ao-Exclus˜ao – propriedades Nota¸c˜ao alternativa ▶ Sejam P1, ..., Pn poss´ıveis propriedades de um elemento a ∈ A. ▶ Denote N = |A|. ▶ Seja N(Pi) o n´umero de elementos em A com propriedade Pi. Ent˜ao |Ai| = |{a ∈ A | a tem propriedade Pi}| = N(Pi) ▶ Seja N(PiPj) o n´umero de elementos em A com propriedade Pi e Pj, correspondendo portanto a |Ai ∪ Aj|. Com essa nova nota¸c˜ao, obtemos portanto: S1 = N(P1) + N(P2) + N(P3) + · · · + N(Pn) S2 = N(P1P2) + N(P1P3) + · · · + N(Pn−1Pn) S3 = N(P1P2P3) + N(P1P2P4) + · · · + N(Pn−2Pn−1Pn) · · · Sn = N(P1P2 · · · Pn) Contando os elementos com nenhuma das propriedades Contar elementos com nenhuma das propriedades Denotemos o n´umero de elementos que n˜ao tˆem propriedade i com N(P′ i ), e com nenhuma das n propriedades por N(P′ 1P′ 2 · · · P′ n). Como podemos contar esse caso? Repare que ´e o complemento de quando x tem pelo menos uma das propriedades P1 · · · Pn, o que corresponde `a cardinalidade da uni˜ao dos conjuntos, |A1 ∪ · · · ∪ An|. Contando os elementos com nenhuma das propriedades Exemplo 7.5.2 Quantos inteiros no [1, 1000] n˜ao s˜ao divis´ıveis por 7 nem por 11? Inteiros divis´ıveis por 7: a1 = ⌊ 1000 7 ⌋ = 142. Inteiros divis´ıveis por 11: a2 = ⌊ 1000 11 ⌋ = 90 Inteiros divis´ıveis por 7 e 11: a12 = ⌊ 1000 77 ⌋ = 12 Inteiros divis´ıveis por 7 ou 11: a∪ = a1 + a2 − a12 = 142 + 90 − 12 = 220 Inteiros n˜ao divis´ıveis por 7 nem por 11: N − a∪ = 1000 − 220 = 780 Aqui N = |A|, a cardinalidade do universo. Contando os elementos com nenhuma das propriedades Seja N(P{P3--- Ph) = |{x € A| x nao tem nenhuma das propriedades P;}|. Entao N(P{P3-+-P%) = N—|A, U Ap U=++U An Também So = Si-S2.4+ $3 —-+-4(-1)°"'S, Entao obtemos o seguinte Teorema N(PIPS-+- Pl) =N—S, +S — 53 —---+(-1)"S, onde Si = 0; (Pi) = N(P1) + N(P2) + N(P3) +> +> + (Pn) S2 = Vic; N(PiP)) = N(PiP2) + N(PiP3) +--+ + N(Pn—1Pn) S3 = Vicjex N(PiP)Pk) = N(PiP2P3) + N(PiP2Pa) + +--+ N(Pn—2Pn—1Pn) Sn = N(PiP2--- Pn) Contando os elementos com nenhuma das propriedades Exemplo 7.6.1 Quantas solu¸c˜oes existem para x1 + x2 + x3 = 11 sujeito a x1 ≤ 3, x1 ≤ 4, x1 ≤ 6. ▶ N = C(3 − 1 + 11, 11) = 78 ▶ N(P1) = n´umero de solu¸c˜oes com x1 ≥ 4 = C(3 − 1 + 7, 7) = 36 ▶ N(P2) = n´umero de solu¸c˜oes com x2 ≥ 5 = C(3 − 1 + 6, 6) = 28 ▶ N(P3) = n´umero de solu¸c˜oes com x3 ≥ 7 = C(3 − 1 + 4, 4) = 15 ▶ N(P1P2) = n´umero de solu¸c˜oes com x1 ≥ 4 ∧ x2 ≥ 5 = C(3 − 1 + 2, 2) = 6 ▶ N(P1P3) = n´umero de solu¸c˜oes com x1 ≥ 4 ∧ x3 ≥ 7 = C(3 − 1 + 0, 0) = 1 ▶ N(P2P3) = n´umero de solu¸c˜oes com x2 ≥ 5 ∧ x3 ≥ 7 = 0 ▶ N(P1P2P3) = n´umero de solu¸c˜oes com x1 ≥ 4 ∧ x2 ≥ 5 ∧ x3 ≥ 7 = 0 Ent˜ao N(P′ 1P′ 2P′ 3) = N − S1 + S2 − S3 = 78 − (36 + 28 + 15) + (6 + 1 + 0) − 0 = 6 O Principio da Inclusao-Exclusao — nenhuma propriedade Exemplo 7.5.2 — o crivo de Eratostenes Quantos inteiros no [2,100] nao sao divisiveis por 2 ou 3 ou 5 ou 7? Resposta N(P{P3P3P,) = N-—Si+S.—$34+ Ss N: 99 nuimeros S1 = 0; N(Pi): — Inteiros divisiveis por 2: N(Pi) = [722] = 50; — inteiros divisiveis por 3: N(P2) = L 3. = 33; — inteiros divisiveis por 5: N(P3) = [22] = 20; inteiros — divisiveis por 7: N(Pa) = [*8°| = 14. Sz = Di; N(PiPj): Inteiros divisiveis por um produto de dois primos. S3 = Vicjex N(PiPiPx): Inteiros divisiveis por um produto de trés primos. Sa = Vicjenc) N(PiPjP.P1): Inteiros divisiveis por um produto de quatro primos. O Princ´ıpio da Inclus˜ao-Exclus˜ao – nenhuma propriedade Observa¸c˜ao O crivo ´e muito pouco usado na pr´atica. Os modernos testes de primalidade usam uma extens˜ao do seguinte teorema: Teorema* (Fermat) Se p ´e um n´umero primo, ent˜ao ap−1 mod p = 1 para todo a ∈ [1, ..., p − 1]. Contraposi¸c˜ao* Se n ´e um inteiro tal que existe um a tal que an−1 mod n ̸= 1. Ent˜ao n n˜ao ´e um n´umero primo. (Esse slide n˜ao faz parte da mat´eria.) O Principio da Inclusao-Exclusao — complemento de propriedades Exemplo 2 — O numero de func6ées sobrejetivas Suponha |A| = 6 e |B| = 3. Quantas fungdes sobrejetivas existem de A para B? 1. Podemos pensar que A = {1,2,3,4,5,6} e B = {1, 2, 3}. 2. O ndmero total de funcdes de A para B é 3°, ou seja N = 3°. 3. Defina P; como a propriedade que / nao esta na imagem de f. 4. N(P1) = |{f : A {2,3}} = 2°. Ent3o N(P1) + N(P2) + N(P3) = (2) - 2°. 5. N(P1P2) = |{f : A {3}} = 1° Entdo N(PiP2) + N(PiP3) + N(P2P3) = (3) -1° 6. N(P,P2P3) =0 N(P{P3P3) = N-Si +S — $3 = 8-()-2%+()-%-0 = 729-—19243 = 540 O Principio da Inclusao-Exclusao — complemento de propriedades Teorema 7.6.1 — O numero de fungées sobrejetivas Suponha |A| = me |B| = n. Quantas func¢ées sobrejetivas existem de A para B? Resposta: m n m n m n—1 n m n -({) on “(3)o-a —-++++4+(-1) (7s) O Princ´ıpio da Inclus˜ao-Exclus˜ao – desencontros Exemplo 4 – Amigo oculto Para organizar um amigo oculto com n pessoas, coloca-se n papeis com os nomes das pessoas numa envelope, e cada pessoa esloha um papel. Qual ´e a probabilidade que pelo menos uma pessoa escolhe um papel com seu pr´oprio nome, quando n tende ao infinito? O complemento desse problema ´e conhecido com o problema dos chapeus: n cavalheiros jogom seus chapeus no ar. Qual ´e a probabilidade que ningu´em pega seu pr´oprio chapeu. O Princ´ıpio da Inclus˜ao-Exclus˜ao – desencontros Pontos fixos e desencontros Seja f uma permuta¸c˜ao de A, ou seja, uma fun¸c˜ao bijetora de A para A. O valor a ´e chamado um ponto fixo de f se f (a) = a. Um desencontro (inglˆes: derangement, livro: permuta¸c˜ao ca´otica) ´e uma permuta¸c˜ao que n˜ao tem ponto fixo. O n´umero de desencontros de [1, n] ´e denotado Dn. Exemplo ▶ A permuta¸c˜ao [2 3 5 4 1] tem um ponto fixo, a saber 4. ▶ A permuta¸c˜ao [2 3 5 1 4] n˜ao tem ponto fixo, ent˜ao ´e um desencontro. O Princ´ıpio da Inclus˜ao-Exclus˜ao – desencontros n=2: [2 1] =⇒ D2 = 1 =⇒ D2/2! = 0, 5 n=3: [2 3 1], [3 1 2] =⇒ D3 = 2 =⇒ D3/3! = 0, 3333 n=4: 9 em 24 =⇒ D4 = 9 =⇒ D4/4! = 0, 3750 n=5: 0.36666 n=6: 0.36806 n=7: 0.36786 Vamos mostrar que Pr[desencontro] = Pr[amigo oculto da certo] = Dn/n! tende para 1/e ≈ 1/2.717281828 ≈ 0.367879 se n → ∞ O Principio da Inclusao-Exclusao — desencontros Teorema 7.6.2 O ntmero de desencontros para n objetos é 1 1 1 1 =n”lfl—-— 42-2 4..-4(-1/= D, = n![1 rt 3 31+ + (—1) nl) Prova Uma permuta¢ao f tem propriedade P; se i 6 um ponto fixo de f. Um desencontro é uma permuta¢cao que nado tem propriedade P; para todo i € {1,..., n}. Portanto Dn = N(P;P3...P4). Pelo principio de inclusdo-exclusdo temos que N(P{P3...Pn) = N —S~N(Pi) + 5> M(P;P)) — > N(PiP)Px).. i i<j i<j<k Vamos analisar os termos ao lado direito. O Principio da Inclusao-Exclusao — desencontros > N=n! > N(P;) =(n—1)!, porque fixando o valor / restam (n — 1)! permuta¢des nos demais elementos. Entdo >>, N(P:) = (7) -(n—1)! > N(P;P;) = (n— 2)!, porque fixando os valores i e j restam (n — 2)! permuta¢des nos demais elementos. Entéo >7;_, N(PiP;) = (3) -(n— 2)! > Somando m propriedades, temos que )> N(P;P;---) = (2) -(n—m)! —Se~ Substuindo na formula do slide anterior obtemos Dn = N—JT,N(Pi) + 30,-; N(PiPi) — icjck N(P;P;Px)..- = n-~()-(n-1)'4 (3) «(n= 2)! 0-4 (=1)" (") «(n= n)! = maga: (9-1)! + age (9-2)! + (- 1)" aig - 0! = ml[l-y_+a-q-o--+(-1)"4] O Princ´ıpio da Inclus˜ao-Exclus˜ao – desencontros Corol´ario lim n→∞ Dn n! = e−1 Prova Isso segue lembrando que ex = 1 + x 1! + x2 2! + x3 3! + x4 4! + · · · e substituindo x = −1. O Princ´ıpio da Inclus˜ao-Exclus˜ao – desencontros Curiosidade sobre desencontros Existe uma outra forma de se calcular Dn. Usando um argumento combinat´orio pode-se provar que, para n ≥ 3 Dn = (n − 1)(Dn−1 + Dn−2) . E sabemos que D1 = 0 e D2 = 1. Curiosidade sobre reencontros Um ponto fixo tamb´em ´e conhecido como um reencontro. Existe uma f´ormula que conta quantos pontos fixos existem para cada n. Veja https://en.wikipedia.org/wiki/Rencontres_numbers Asintoticamente, a probabilidade de k pontos fixos ´e dado pela seguinte tabela: k 0 1 2 3 4 5 e−1/0! e−1/1! e−1/2! e−1/3! e−1/4! e−1/5! .368 .368 .184 .061 .015 .003 Essa distribui¸c˜ao corresponde `a distribui¸c˜ao de Poisson com λ = 1.