Baixe o app para aproveitar ainda mais
Prévia do material em texto
10/29/13 1 Contagem, Permutações e Combinações Matemá.ca Discreta II (Cap. 6 Rosen) André Câmara (andrecamara@deinfo.ufrpe.br) • Teorema • Uma declaração que pode ser demonstrada verdadeira • Formados por uma ou mais premissas e uma conclusão • Podem ser chamados também de fatos ou resultados • Demonstramos que um teorema é verdadeiro através de uma prova Terminologia • Axioma • Declarações assumidas como verdadeiras (ex.: x=x) • Lemma • Teorema menos importante (usado como passo intermediário em uma prova) • Corolário • Teorema estabelecido diretamente a par.r do teorema provado • Conjectura • Declaração assumida como verdadeira, baseados em evidências parciais, argumentos heurís.cos, ou intuição de especialista • Quando provadas, tornam-‐se Teoremas Terminologia (cont.) • Princípios básicos de contagem • Regra do Produto: • Suponha que um evento E pode ocorrer de m formas diferentes, e , independentemente deste evento, um segundo evento F pode ocorrer de n maneiras. • Então, E ou F podem ocorrer de mn maneiras. Revisão: Combinatória Regra do Produto • Exemplo: • Uma empresa com apenas dois funcionários aluga um andar de um prédio com 12 escritórios. • De quantas formas podemos atribuir estas salas aos dois funcionários? • R: Atribuir uma sala ao funcionário 1 (que pode ocorrer de 12 formas diferentes) e atribuir uma sala ao funcionário 2 (de 11 formas diferentes) • Pela regra do produto, temos: 12 11 = 132 formas diferentes Exemplo 2 • Quantas sequências de bit diferentes com tamanho 7 existem? • R: Cada um dos 7 bits pode ser preenchido de 2 maneiras (0 ou 1) • 2*2*2*2*2*2*2 = 27 = 128 10/29/13 2 Exemplo 3 • Existem 26 escolhas para cada uma das três letras maiúsculas e 10 escolhas para cada um dos 3 dígitos. Quantas placas podem ser geradas? • R: 26*26*26*10*10*10 = 17.576.000 placas possíveis Exemplo 4 • Qual o valor de k após a execução deste código (n1, n2, ... nm são inteiros posi.vos): • R: n1* n2*...* nm • Suponha que um evento E pode ocorrer de m formas diferentes, e um segundo evento F pode ocorrer de n maneiras diferentes, e suponha também que ambos eventos não podem ocorrer simultaneamente. • Então, E ou F podem ocorrer de m+n formas. Regra da soma Exemplo 1 • Suponha que ou um docente ou um aluno será escolhido como representante de um comitê universitário. Este comitê pode ser formado de quantas maneiras diferentes se existem 37 professores e 83 alunos? • R: Existem 37 maneiras de escolher um professor e 83 maneiras de escolher um aluno. Estas escolhas são independentes uma da outra, portanto existem 37+83 = 120 maneiras diferentes. Exemplo 2 • Qual o valor de k após a execução do seguinte trecho de código (n1, n2, ... nm são inteiros posi.vos): • R: n1+ n2+ ... + nm • Para 3 ou mais eventos... E1 à n1 E2 à n2 E3 à n3 ... Estendendo... Regra da soma: (dois eventos não ocorrem ao mesmo tempo) Num. maneiras = n1 + n2 + n3 + ... Regra da mul5plicação: (eventos ocorrem um após o outro) Num. maneiras = n1 n2 n3 ... 10/29/13 3 • Suponha que uma universidade tem 3 disciplinas diferentes de história, 4 disciplinas diferentes de literatura, e 2 disciplinas diferentes de sociologia. a) O número m de formas que um estudante pode escolher os cursos é: m = (3)(4)(2) = 24 b) O número m de formas que um estudante pode escolher apenas um dos cursos é: m = (3) + (4) + (2) = 9 Exemplo 3 Exemplo: contando endereços IP • Na internet, cada computador possui um endereço chamado endereço IP. • No IPv4, este endereço é composto de 32 bits • ne.d=número da rede • hos.d=número do host Exemplo: contando endereços IP • Classe A: redes grandes • 0 seguido por 7-‐bits para rede e 24-‐bits para hosts • ne.d não pode ser 1111111 • Classe B: redes médias • 10 seguido por 14-‐bits para rede e 16-‐bits para hosts • Classe C: redes menores • 110 seguido de 21-‐bits para rede e 8-‐bits para hosts • 11111111 e 00000000 tem uso especial e não podem ser designados como end. de host válidos Exemplo: contando endereços IP • Quantos endereços IP estão disponíveis na internet? • R: Seja x o número de endereços disponíveis • xA = números de endereços da Classe A • xB = números de endereços da Classe B • xC = números de endereços da Classe C • x = xA + xB + xC Exemplo: contando endereços IP • xA = 27 – 1 = 127 redes (rede 1111111 é indisponível) • Para cada rede existem 224-‐2 = 16.777.214 hosts • xA = 127 * 16.777.214 = 2.130.706.178 • xB = 214 = 16.384 redes • Para cada rede existem 216-‐2 = 65.534 hosts • xB= 16.384 * 65.534 = 1.073.709.056 • xC = 221 = 2.097.152 redes • Para cada rede existem 28-‐2 = 254 hosts • xC = 2.097.152 * 254 = 532.676.608 • x = 3.737.091.842 endereços Princípio da Inclusão-‐Exclusão • Ou “Regra da Subtração” • Suponha que uma tarefa possa ser feita de uma dentre duas maneiras, mas algumas dessas maneiras são comuns entre eles. • Não podemos usar a regra da soma! • Devemos subtrair as formas que se repetem, para que não sejam contadas duas vezes • “Se uma tarefa pode ser feita de n1 ou n2 maneiras, então o número de formas de se realizar a tarefa é n1+n2 menos o número de formas de se realizar a tarefa que são comuns às duas maneiras”. • Sejam A e B conjuntos finitos • Teorema • Para quaisquer conjuntos finitos A, B e C 10/29/13 4 Exemplo 1 • Encontre o número de estudantes matriculados em pelo menos uma das aulas de Francês, Alemão e Inglês, dado que: • 65 estudam Francês, 20 estudam Francês e Alemão • 45 estudam Alemão, 25 estudam Francês e Inglês, • 42 estudam Inglês, 15 estudam Alemão e Inglês • 8 estudam todas as três línguas Exemplo • Ou por diagramas de Venn 10 28 12 8 18 7 17 F A I n(F∪A∪ I ) = n(F)+ n(A)+ n(I ) −n(F∩G)− n(F∩ I )− n(A∩ I )+ n(F∩A∩ I ) = 65+ 45+ 42− 20− 25−15+8 =100 Exemplo 2 • Quantas strings de bits de tamanho 8 começam com 1 ou terminam com dois bits 00? formas formas formas Pode estar dentro de ambos os conjuntos de soluções n = 128+64-‐32 = 160 Regra da divisão • Existem n/d maneiras de se realizar uma tarefa se ela pode ser feita usando um procedimento que pode ser realizado de n maneiras, e para cada maneira w, exatamente d das n maneiras correspondem à maneira w. Exemplo • De quantas maneiras diferentes 4 pessoas podem se sentar em torno de uma mesa circular, onde duas arrumações são consideradas a mesma quando cada pessoa tem o mesmo vizinho da esquerda e o mesmo vizinho da direita? Exemplo • R: Rotulando os assentos: • Temos 4 formas de escolher quem vai sentar no assento 1 • 3 para o assento 2, ... • 4! = 24 maneiras das pessoas sentarem • Considerar apenas as maneiras com vizinhos diferentes! • 4 formas diferentes de selecionar a pessoa do assento 1 à 24/4 = 6 maneiras Assento 1 Assento 2 Assento 3 Assento 4 10/29/13 5 Diagrama de Árvore • Uma forma comum de representar todas as saídas de uma sequência de eventos • Ex.: A = {1,2}, B={a,b,c}, C={x,y} n=(2)(3)(2)=12 Diagrama de Árvore • Exemplo: • Strings de bits de tamanho 4 sem 1`s consecu.vos Princípio da Casa de Pombos • Muitos resultados na teoria combinatória são versões diferentes do mesmo problema: “Se n casas de pombos são ocupadas por n+1 ou mais pombos, então pelo menos uma casa é ocupada por mais de um pombo” Exemplos • Suponha que um departamento contém 13 professores • Então dois dos professores nasceram no mesmo mês • Suponha que um saco de lavanderia contém muitas meias vermelhas, brancas e azuis. • Então é necessário pegar apenas 4 meias (pombos) para ter certeza de obter um par com uma única cor (casa de pombo) Exemplos • Mostre que em um conjunto de 6 aulas existem duas que são ministradas no mesmo dia. Assuma que as aulas não são ministradas nos finais de semana. • Temos 5 dias úteis durante a semana e temos 6 aulas. Se todo dia tem uma aula, então serão 5 aulas por semana, sobrando 1 aula que será colocada no mesmo dia de outra. Exemplos • Mostre que em um conjunto de 5 inteiros (não necessariamente consecu.vos) existem 2 com o mesmo resto quando dividido por 4. • Os possíveis restos quando dividimos um número por 4, são: 0, 1, 2, 3 (4 restos) • Se tenho 5 inteiros, então quando divididos por 4 terão 5 restos. Como temos 4 restos dis.ntos 2 serão iguais. 10/29/13 6 Exemplos • Em um conjunto de 367 pessoas, pelo menos quantas pessoas fazem aniversário no mesmo dia? • Pelo menos 2, pois só temos no máximo 366 dias possíveis Exemplos • Encontre o número mínimo de elementos que são necessários ser re.rados do conjunto S = {1,2,3,...9} para que se tenha certeza que dois dos números somados resultam em 10 • Aqui as casas de pombos são os 5 conjuntos {1,9}, {2,8}, {3,7}, {4,6}, {5} • Portanto, qualquer escolha de 6 elementos de S garante que 2 dos números somados resultam em 10 Generalizando • Se n casas de pombo são ocupadas por kn+1 ou mais pombos, onde k é um inteiro posi.vo, então pelo menos uma casa de pombo é ocupada por k+1 ou mais pombos. Exemplos • Encontre o número mínimo de estudantes em uma turma de modo quese tenha certeza de que 3 deles nasceram no mesmo mês • Aqui, n=12 é o número de casas de pombos • K+1 devem ocupar a mesma casa (mes) • k+1 = 3, portanto k=2 • Entre kn+1 = 25 estudantes (pombos), três deles serão nascidos no mesmo mês Exemplos • Suponha que um saco de lavanderia contém muitas meias vermelhas, brancas e azuis. Ache o número de meias que se deve escolher a fim de se obter 2 pares (4 meias) das mesma cor. • n=3 cores (casas de pombos) • k+1 = 4 (meias da mesma cor, ou pombos ocupando a mesma casa) • k=3 • kn+1 = 3*3+1 = 10 • Dentre quaisquer 10 meias, 4 tem a mesma cor PERMUTAÇÕES E COMBINAÇÕES 10/29/13 7 Algumas funções importantes • Função Fatorial • O produto dos inteiros posi.vos de 1 a n (inclusive) é denotado por n! (“n fatorial”) n! = 1 2 3 4 ... (n-‐2) (n-‐1) n • Importante: • 0! = 1 • 1! = 1 • n! = n(n-‐1)! Fatorial Exemplos • Exemplo 1: • Exemplo 2: • Observe que: Permutações • Qualquer arranjo de um conjunto de n objetos em uma dada ordem é chamada de uma permutação • BDCA, DCBA e ACDB são permutações de A,B,C,D • Qualquer arranjo de r ≤ n destes objetos em uma dada ordem é chamada de uma r-‐permutação dos n objetos, r a r • BAD, ACB, DBC são permutações das 4 letras 3 a 3 • AD, BC, CA são permutações das 4 letras 2 a 2 Permutações • Normalmente estamos interessados apenas no número de permutações, sem necessitar lista-‐las • O número de permutações de n objetos r a r é denotado por: P(n,r) • Alguns livros também u.lizam nPr , Pn,r ou (n)r Permutações • Teorema • Prova: • Primeiro elemento: n opções • Segundo elemento: n-‐1 opções • ... • r-‐ésimo elemento: n-‐(r-‐1) = n-‐r+1 • Pela regra do produto, chegamos ao Teorema r termos Exemplo 1 • Encontre o número m de permutações de seis objetos, A, B, C, D, E, F, selecionando-‐se 3 a cada momento (3 a 3). • Palavras com três letras usando apenas as seis letras dadas, sem repe.ção 10/29/13 8 Permutações • Corolário • Se r = n, então existem n! permutações dos n objetos • Exemplo • Letras A, B, C • 3! = 6 permutações • ABC, ACB, BAC, BCA, CAB, CBA Permutações com Repetições • Nas permutações anteriores, não há repe.ção de objetos • Muitas vezes, queremos saber o número de permutações de n objetos, dos quais alguns podem se repe.r • Exemplo • “BABBY” à “B1 , A , B2 , B3 , Y” • 5! = 120 • Algumas permutações possíveis são Permutações com Repetições • O fato é que existem 3! = 6 formas diferentes de preencher as três primeiras posições com os três B’s • Isso é verdade para cada conjunto de três posições em que os B’s podem aparecer • Teorema: n1, n2, n3, ... à número de repe.ções Permutações com Repetições • De fato, no exemplo anterior, o que teremos é • “BABBY” • “BENZENE” Amostras Ordenadas • Amostragem com reposição • n n n n ... n (r fatores) = nr • Amostragem sem reposição (r-‐permutação) Exemplo • 3 cartas são escolhidas uma após a outra de uma pilha de 52 cartas. Encontre o número m de formas que isto pode ser feito: a. Com reposição b. Sem reposição m = (52) (52) (52) = 140.608 m = P(52,3) = (52) (51) (50) = 132.600 10/29/13 9 Combinatória • “Arte da contagem” • Permite definir o número de objetos em um conjunto rapidamente Combinações • Seja S um conjunto com n elementos. • Uma combinação destes n elementos selecionando-‐se r a cada vez é qualquer seleção de r objetos (sem ordem) • r-‐combinação • Subconjunto de S com r elementos • C(n,r) • Ou nCr , Cn,r , Crn Exemplo • Encontrar o número de combinações de 4 objetos A, B, C, D, sendo selecionados 3 por a cada vez • Cada combinação corresponde a 3! = 6 permutações dos objetos Exemplo (cont.) • O número de combinações mul.plicado por 3! nos dá o número de permutações: • Sendo P(4,3) = 4 3 2 = 24 e 3!=6, temos C(4,3) = 4 ou Combinações • Teorema Ou seja, C(n, r) = nr ! " # $ % & Exemplo • Um fazendeiro compra 3 vacas, 2 porcos, e 4 galinhas de um homem que tem 6 vacas, 5 porcos e 8 galinhas. • Qual o número m de escolhas que o fazendeiro tem? 10/29/13 10 Exemplo • Considere que uma moeda seja lançada 5 vezes. De quantas formas pode-‐se ter três caras? • Combinação (ordem não importa) • Determine o número de formas que uma moeda pode cair se lançada 5 vezes. • O resultado pode ser: • 5 caras, 4 caras, 3 caras, 2 caras, 1 cara, 0 cara Exemplo • Determine o número de formas que uma moedapode cair se lançada 5 vezes. • O resultado pode ser: • 5 caras, 4 caras, 3 caras, 2 caras, 1 cara, 0 cara • O Mesmo que 2 x 2 x 2 x 2 x 2 = 32 = 25 Ou seja, n k ! " # $ % & k=0 n ∑ = 2n Exemplo • De quantas maneiras um comitê, cons.tuido por 3 homens e 2 mulheres, pode ser escolhido entre 7 homens e 5 mulheres? • Homens podem ser escolhidos de • Mulheres podem ser escolhidas de
Compartilhar