Slide - Análise Combinatória - Matemática Discreta - 2023-2

An´alise combinat´oria Jeroen van de Graaf DCC - UFMG Introdu¸c˜ao • Ramo da matem´atica que trata da contagem. • Em geral, a dificuldade n˜ao est´a em como contar mas o que contar. • Contagem ´e a base de teoria de probabilidade. • Em Ciˆencia da Computa¸c˜ao, quest˜oes de contagem s˜ao importantes j´a que temos uma quantidade finita de recursos. Sequˆencias • Uma sequˆencia ´e uma lista finita e ordenada de objetos ou s´ımbolos. • Dependendo do contexto, usa-se letras mai´usculos, letras min´usculas, d´ıgitos, bits ou inteiros para os elementos das sequˆencia. • (1, 2) pode representar o resultado de dois dados • (H, I, K, 0, 4, 4, 5) pode representar uma placa de carro. • Quando n˜ao houver risco de confus˜ao, pode se tirar as parˆenteses e as v´ırgulas: 12 (perigo: pode ser confundido com o n´umero doze), HIK0444. • Entender como aplicar a codifica¸c˜ao de objetos reais aparecendo em problemas usando sequˆencias muitas vezes ´e a metade da resolu¸c˜ao do problema combinat´orio ´Arvore de possibilidades • Uma ´arvore ´e um tipo particular de um grafo onde n˜ao existem ciclos. • ´E uma estrutura muito ´util para registrar todas as sequˆencias, ou seja todas as possibilidades em situa¸c˜oes em que os eventos ocorrem (ou podem ser modelados) em ordem sequencial. ´Arvore de possibilidades Exemplo 1 Regras para decis˜ao de um torneiro entre os times A e B: – Cada jogo tem sempre um vencedor – O time para ser campe˜ao deve vencer dois jogos consecutivos ou um total de trˆes jogos De quantas formas diferentes o torneio pode ser jogado? ´Arvore de possibilidades A A* A* A* A* B* B* B* B* A* B* AxB A B AxB AxB A B A B AxB AxB B A B A AxB AxB B A B A AxB AxB B A B Nota¸c˜ao: X∗ indica que o time X ´e vencedor. ´Arvore de possibilidades Exemplo 1 (continua¸c˜ao) Formas diferentes de o torneio ser jogado: 1. AA∗ 2. ABAA∗ 3. ABABA∗ 4. ABABB∗ 5. ABB∗ 6. BAA∗ 7. BABAA∗ 8. BABAB∗ 9. BABB∗ 10. BB∗ Ou seja, 10 formas diferentes. A A* A* A* A* B* B* B* B* A* B* AxB A B AxB AxB A B A B AxB AxB B A B A AxB AxB B A B A AxB AxB B A B ´Arvore de possibilidades e qual ordem usar? Ordem n´umerica Para elementos de Z etc. Ordem lexicogr´afica ▶ Imponha uma ordem nos s´ımbolos. Ex. A < B < C . . . < Z ▶ Se as duas palavras s˜ao iguais nas primeiras n posi¸c˜oes mas diferente na posi¸c˜ao n + 1, a ordem do s´ımbolo n + 1 decide. ▶ Se as duas palavras s˜ao iguais nas primeiras n posi¸c˜oe, e uma palavra termina na posi¸c˜ao n, esta vai primeiro. Primeiro tamanho; depois ordem lexicogr´afica A ordem lexicogr´afica pura n˜ao serve para mostrar que um conjunto ´e enumer´avel. Nesse caso ´e melhor primeiro ordenar por tamanho, seguido pela ordem lexicogr´afica. Princ´ıpio da multiplica¸c˜ao Exemplo 2 Dois dados representam 6 · 6 = 36 possibilidades. E n dados representam 6 · 6 · · · 6 = 6n possibilidades. Exemplo 3 O n´umero de uma placa ´e formada de LLLNNNN, ou seja, 3 letras seguidas por 4 n´umeros. Isto corresponde a 26 · 26 · 26 · 10 · 10 · 10 · 10 = 175760000 possibilidades. Princ´ıpio da multiplica¸c˜ao Exemplo 4 Um n´umero de identifica¸c˜ao ▶ formado por uma seq¨uˆencia de quatro s´ımbolos ▶ escolhidos de um conjunto formado pelas 26 letras do alfabeto e os 10 d´ıgitos. Quantos n´umeros de identifica¸c˜ao diferentes existem se repeti¸c˜ao de s´ımbolos ´e permitida? ▶ 36 poss´ıveis s´ımbolos: S = {A, . . . , Z, 0, . . . , 9}. ▶ A ordem de ocorrˆencia dos s´ımbolos ´e importante. Assim, existem 36 · 36 · 36 · 36 = 364 = 1 679 616 n´umeros de identifica¸c˜ao diferentes. Princ´ıpio da multiplica¸c˜ao Exemplo 5 Suponha o mesmo cen´ario anterior de n´umero de identifica¸c˜ao mas com a restri¸c˜ao que s´ımbolos n˜ao podem ser repetidos. Neste caso, quantos n´umeros de identifica¸c˜ao existem? 36 · 35 · 34 · 33 = 1 413 720 n´umeros de identifica¸c˜ao diferentes. Princ´ıpio da multiplica¸c˜ao – “minha” vers˜ao Considera a sequˆencia (a1, a2, . . . ak) • se houver n1 poss´ıveis s´ımbolos na primeira posi¸c˜ao, • se houver ni poss´ıveis s´ımbolos na i-´essima posi¸c˜ao, onde o n´umero n˜ao depende dos elementes escolhidos anteriormente. Ent˜ao existem n1 · n2 · . . . · nk sequˆencia diferentes. Princ´ıpio da multiplica¸c˜ao – vers˜ao do livro Se uma opera¸c˜ao consiste em k passos, sendo que • o primeiro passo pode ser executado de n1 formas diferentes, ou seja, existem n1 possibilidades para o passo 1, • o segundo passo pode ser executado de n2 formas diferentes, e assim, sucessivamente, at´e • o k-´esimo passo que pode ser executado de nk formas diferentes ent˜ao toda a opera¸c˜ao pode ser executada de n1 · n2 · . . . · nk formas diferentes. Princ´ıpio da multiplica¸c˜ao Exemplo 6 Suponha que A1, A2, A3, A4 s˜ao conjuntos com n1, n2, n3, n4 elementos respectivamente. Mostre que o conjunto A1 × A2 × A3 × A4 tem n1 × n2 × n3 × n4 elementos. (a1, a2, a3, a4) ∈ A1 × A2 × A3 × A4 Para cada um dos posi¸c˜oes 1 a 4 acima, existem n1, n2, n3, n4 formas respectivamente. Assim, pela regra da multiplica¸c˜ao existem n1 × n2 × n3 × n4 tuplas distintas no conjunto A1 × A2 × A3 × A4. Princ´ıpio da multiplica¸c˜ao Exemplo 7 Quantas strings de tamanho n pode se formar no alfabeto {0, 1}? 2n Como pode-se usar este fato para mostrar que um conjunto A de n elementos tem exatamente 2n subconjuntos? Resposta: existe um mapeamento bijetivo entre s ∈ {0, 1}n e A′ ∈ P(A), onde si = 1 ⇔ ai ∈ A′ Princípio da multiplicação Exemplo 8 Quantas vezes os comandos do trecho de programa abaixo são executados? for i ← 2 to 5 do for j ← 3 to 5 do Comandos a serem executados; endfor; endfor; – Claramente existe uma ordem para execução de cada comando. – Veja que a combinação de variáveis de controle pode ser representada por um par ordenado (i, j) que têm os seguintes valores: (2, 3), . . . ,(2, 5), (3, 3), . . . ,(3, 5), . . . ,(4, 3), . . . ,(5, 5). Assim, os comandos são executados (5 - 2) + 1 ⋅ (5 - 3) + 1 = 4 ⋅ 3 = 12 vezes. Princ´ıpio da multiplica¸c˜ao Exemplo 9 Considere o seguinte problema: As posi¸c˜oes de presidente, tesoureiro e secret´ario tˆem que ser escolhidas entre quatro pessoas A, B, C e D. Al´em disso, existem duas restri¸c˜oes: (a) A n˜ao pode ser presidente; (b) C ou D deve ser o secret´ario. Quantas escolhas distintas existem? ´E natural tentar resolver o problema usando o princ´ıpio de multiplica¸c˜ao. Uma possibilidade ´e fazer o seguinte racioc´ınio: – Existem trˆes escolhas para presidente j´a que A n˜ao pode ser; – Existem trˆes escolhas para tesoureiro de um conjunto de quatro candidatos; – Duas escolhas para secret´ario. Observe que: – O n´umero de escolhas de secret´ario depende de como o presidente e o tesoureiro s˜ao escolhidos e o valor acima n˜ao ´e correto. Princ´ıpio da multiplica¸c˜ao Exemplo 9 (continua¸c˜ao) A ´arvore abaixo mostra todas as possibilidades: Tesoureiro B C D A C D A B A B C D C C D D D C Chapa Presidente Secretário Princípio da multiplicação Exemplo 10 Quantos inteiros de três dígitos são divisíveis por 5? Observe que: – Os números inteiros candidatos estão no intervalo [100, 999]. – Os números candidatos terminam em 0 ou 5. Primeira estratégia para resolver o problema: – Os números divisíveis por 5 nesse intervalo podem ser “criados” a partir da concatenação de dígitos provenientes dos seguintes conjuntos, nessa ordem: {1, 2, 3, 4, 5, 6, 7, 8, 9}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}{0, 5} Assim, essa quantidade é dada por: 9 10 2 —––––—— ⋅ ————––—— ⋅ ————––— = 180 # possibilidades para # possibilidades para # possibilidades para o primeiro conjunto o segundo conjunto o terceiro conjunto (centena) (dezena) (unidade) Princ´ıpio da multiplica¸c˜ao Exemplo 10 (continua¸c˜ao) O problema pode ser resolvido usando o princ´ıpio de transforma¸c˜ao: use uma bije¸c˜ao para mapear o problema original para um outro problema que sabemos contar. – Enumere os n´umeros divis´ıveis por 5 nesse intervalo: 100 . . . 105 . . . 995 . . . 999 ↕ ↕ ↕ 5 · 20 5 · 21 5 · 199 – Assim, os divisores por 5 dos inteiros no intervalo [100, 999] s˜ao os n´umeros 20, 21, . . . , 199. – Portanto, a quantidade de divisores ´e dada por (199 − 20) + 1 = 180. Princ´ıpio da multiplica¸c˜ao Exemplo 11 Um pal´ındromo ´e uma palavra sim´etrica: o primeiro s´ımbolo ´e igual ao ´ultimo, etc. Quantos n´umeros pal´ındromos existem que possuem cinco d´ıgitos? d1d2d3d4d5 Vamos usar o seguinte racioc´ınio: (a) N´umero de op¸c˜oes para d1 = 9. (b) N´umero de op¸c˜oes para d2 = 10. (c) N´umero de op¸c˜oes para d3 = 10. (d) N´umero de op¸c˜oes para d4 = 1, j´a que d4 = d2. (e) N´umero de op¸c˜oes para d5 = 1, j´a que d5 = d1. § A solu¸c˜ao deste problema ´e dado por 9 · 10 · 10 Princ´ıpio da adi¸c˜ao • Existem problemas de contagem que podem ser resolvidos contando o n´umero de elementos: – na uni˜ao de dois conjuntos disjuntos, – na diferen¸ca entre dois conjuntos, e – na intersec¸c˜ao de dois conjuntos • O princ´ıpio a ser usado neste caso ´e chamado de Princ´ıpio da Adi¸c˜ao. Princ´ıpio da adi¸c˜ao Se for poss´ıvel particionar o espa¸co de todas as possiveis palavras em dois subconjuntos, sabe se que |A| = |A1| + |A2|. Em geral aplicam-se formulas como |A − B| = |A| − |B| desde que B ⊂ A |A ∪ B| = |A| + |B| − |A ∩ B| |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| Princ´ıpio da adi¸c˜ao Exemplo 12 Uma senha de usu´ario de um sistema computacional pode ser formada por seq¨uˆencias de uma a trˆes letras mai´usculas, sendo que repeti¸c˜oes s˜ao permitidas. Quantas senhas diferentes existem? Observe que: – O conjunto de todas as senhas ´e formada pelos subconjuntos de senhas de uma, duas e trˆes letras. Em cada um desses subconjuntos temos a seguinte quantidade de senhas: – Uma letra: 26 – Duas letras: 26 · 26 = 262 – Trˆes letras: 26 · 26 · 26 = 263 Assim, pelo princ´ıpio da adi¸c˜ao temos: 26 + 262 + 263 = 18 278 senhas de usu´ario diferentes. Princ´ıpio da adi¸c˜ao Exemplo 13 N´umero de maneiras de obter Q ou K de um baralho? ▶ Q: 4 maneiras ▶ K: 4 maneiras ▶ total: 8 maneiras Princ´ıpio da adi¸c˜ao Exemplo 14 N´umero de maneiras de obter Q ou carta vermelha de um baralho? ▶ Q: 4 maneiras ▶ carta vermelha: 26 maneiras ▶ a interse¸c˜ao n˜ao ´e vazia; tem dois elementos ▶ total: 4 + 26 − 2 = 28 ▶ Q preta: 2 maneiras ▶ carta vermelha: 26 maneiras ▶ agora a interse¸c˜ao ´e vazia sim ▶ total: 2 + 26 = 28 Princípio da adição Exemplo 15 Quantos números inteiros ímpares existem no intervalo [10,99] com dígitos distintos? [ ] [ Números com ] [ Dígitos das dezenas ] [ Dígitos das unidades ] − 5 [ dígitos distintos ] I II Os cinco números ímpares com dígitos iguais são 11, 33, 55, 77 e 99. Logo, deve-se subtrair 5. —{1, 2, . . . , 9}— = 9 I —{1, 3, 5, 7, 9}— = 5 II Números com dígitos distintos = 9 × 5 − 5 = 40 Princ´ıpio da adi¸c˜ao – complemento Exemplo 16 No exemplo 3 vimos que existem 364 = 1 679 616 identificadores formados por uma seq¨uˆencia de quatro s´ımbolos escolhidos de um conjunto formado pelas 26 letras do alfabeto e os 10 d´ıgitos, com repeti¸c˜ao de s´ımbolos. Dessa quantidade quantos identificadores possuem pelo menos um s´ımbolo repetido? A quantidade de identificadores com pelo menos um s´ımbolo repetido = (a quantidade de identificadores de tamanho quatro) − (a quantidade de identificadores de tamanho quatro com s´ımbolos n˜ao repetidos). Assim, o total de identificadores de tamanho quatro com pelo menos um s´ımbolo repetido ´e dado por 364 − (36 · 35 · 34 · 33) = 1 679 616 − 1 413 720 = 265 896 Princ´ıpio da adi¸c˜ao Exemplo 17 Quantos n´umeros inteiros existem no intervalo [1, 100 000] que contˆem o algarismo 6 exatamente uma ´unica vez? Princ´ıpio da adi¸c˜ao Exemplo 18 Quantos n´umeros inteiros existem no intervalo [1, 100 000] que contˆem pelo menos um algarismo 6? RESUMO Vimos at´e agora: ▶ Enumera¸c˜ao manual com ´arvores de possibilidades ou listas ordenadas; ▶ Princ´ıpio da multiplica¸c˜ao; ▶ Princ´ıpio da adi¸c˜ao. Agora ▶ Permuta¸c˜oes e permuta¸c˜oes-r ▶ Combina¸c˜oes ▶ Coeficientes binomiais RESUMO Vimos at´e agora: ▶ Enumera¸c˜ao manual com ´arvores de possibilidades ou listas ordenadas; ▶ Princ´ıpio da multiplica¸c˜ao; ▶ Princ´ıpio da adi¸c˜ao. Agora ▶ Permuta¸c˜oes e permuta¸c˜oes-r ▶ Combina¸c˜oes ▶ Coeficientes binomiais PERMUTAÇÕES Permutação Exemplo 19 Seja a sequência {a, b, c}. a Quantas permutações (anagramas) existem? 3 2 1 = 6 # possibilidades para # possibilidades para # possibilidades para o primeiro símbolo o segundo símbolo o terceiro símbolo b Quais são elas? 1. abc 2. acb 3. bac 4. bca 5. cab 6. cba Permutação: Caso padrão Considere um alfabeto com n símbolos. Quantas sequências de tamanho n existem considerando todos os elementos e onde não há repetição? Observe que: - A ordem de ocorrência dos símbolos da sequência é importante. Aplicando-se o princípio da multiplicação, temos: n (n-1) # possibilidades para # possibilidades para # possibilidades para o primeiro símbolo o segundo símbolo o n-ésimo símbolo 1 = n! Permutação-r: o caso genérico No caso genérico precisamos selecionar apenas r < n símbolo, e não todos. • Considere um alfabeto com n símbolos. Quantas sequências de tamanho r existem, com 1 ≤ r ≤ n. • Observe que: - A ordem de ocorrência dos símbolos na palavra é importante. • Aplicando-se o princípio da multiplicação, temos: n · (n-1) ··· · (n-r+1) = # possibilidades para # possibilidades para # possibilidades para o primeiro símbolo o segundo símbolo o r-ésimo símbolo n Π i = (n - r + 1) · ··· · (n - 1) · n = n! i=n−r+1 (n − r)! • Quando r = n isto se reduz ao caso anterior. (Na verdade, quando r = n − 1 isto se reduz ao caso anterior — por quê?). Permuta¸c˜ao: Caso gen´erico F´ormula permuta¸c˜ao Considere um alfabeto com n s´ımbolos e seja r tal que 1 ≤ r ≤ n. Existem P(n, r) = n! (n − r)! permuta¸c˜oes i.e. sequˆencias de s´ımbolos de tamanho r, ou seja, sequˆencias onde a ordem importa e que n˜ao h´a repeti¸c˜ao. Permuta¸c˜ao-r Quantas maneiras pode-se escolher r s´ımbolos (objetos) de um total de n s´ımbolos diferentes, se • a ordem dos s´ımbolos ´e importante, e • a repeti¸c˜ao n˜ao ´e permitida. Resposta: P(n, r) = n! (n − r)! Exemplo: senha de tamanho 4 com 36 s´ımbolos diferentes; ha 36 · 35 · 34 · 33 possibilidades. Permuta¸c˜ao Exemplo 20 Permuta¸c˜oes de letras de uma palavra: (a) De quantas formas diferentes as letras da palavra COMPUTER podem ser arranjadas numa sequˆencia? Todas as letras na palavra COMPUTER s˜ao distintas. Assim, o n´umero de formas distintas de arranjar as letras ´e o n´umero de permuta¸c˜oes de um conjunto de oito elementos, ou seja, 8! = 40 320. (b) De quantas formas diferentes as letras da palavra COMPUTER podem ser arranjadas se as letras CO devem permanecer unidas nesta ordem? Se as letras CO devem permanecer unidas existem efetivamente sete objetos a serem arranjados. Assim, o n´umero de permuta¸c˜oes ´e 7! = 5 040. Permuta¸c˜ao Exemplo 21 Permuta¸c˜oes de objetos ao redor de um c´ırculo: A Numa reuni˜ao, seis pessoas v˜ao estar sentadas `a mesa que tem formato circular. De quantas formas diferentes essas pessoas podem se sentar? Identifique as pessoas como A, B, C, D, E e F. Somente as posi¸c˜oes relativas importam j´a que n˜ao existe uma identifica¸c˜ao de assento na mesa. Por exemplo, comece com A e considere todos os arranjos das outras pessoas em rela¸c˜ao a A. As pessoas B a F podem se sentar em volta de A de todas as formas poss´ıveis. Assim, existem 5! = 120 formas de arranjar o grupo. Permuta¸c˜oes Exemplo 22 Um estudante tem: – 4 livros de sistemas operacionais; – 7 livros de programa¸c˜ao; e – 3 livros de estruturas de dados. colocados na prateleira de uma estante, dado que livros de um mesmo assunto devem ficar juntos? Observe que: – A ordem de ocorrˆencia dos conjuntos de livros na estante ´e importante. – Dentro de cada conjunto de livros a ordem tamb´em ´e importante. – O problema pode ser dividido em duas partes: n´umero de ordena¸c˜oes de conjuntos e, dentro de cada conjunto, ordena¸c˜ao dos livros. Permutações Exemplo 22 (continuação) A quantidade de ordenações de conjuntos de livros é dada por: 3 · 2 · 1 = 6 # possibilidades para # possibilidades para # possibilidades para o primeiro conjunto o segundo conjunto o terceiro conjunto (esquerda) (meio) (direita) Para cada um dos conjuntos de livros, temos as seguintes possibilidades: - Sistemas operacionais (4 livros): 4 · 3 · 2 · 1 = 4! - Programação (7 livros): 7 · 6 · ··· · 1 = 7! - Estruturas de dados (3 livros): 3 · 2 · 1 = 3! Assim, temos 6 · (4! · 7! · 3!) = 4 354 560 possibilidades de colocar os livros na estante. COMBINAÇÕES Permuta¸c˜oes X Combina¸c˜oes: a ordem importa? A ordem importa → permuta¸c˜ao ▶ Senha de tamanho 4 com 36 s´ımbolos diferentes. ▶ Diretoria com Presidente, Secret´ario, Tesoureiro, Diretor Festas, de um grupo de 36 s´ocios ▶ Sorteio de 4 bolinhas de um total de 36 bolinhas diferentes sem reposi¸c˜ao, onde a ordem importa A ordem n˜ao importa → combina¸c˜ao ▶ Equipe de quatro atl´etas de um total de 36 atl´etas. ▶ Subconjunto de tamanho 4 de um total de 36 ▶ Quantas strings de tamanho 36 tem 4 1s. ▶ Sorteio de 4 bolinhas de um total de 36 bolinhas diferentes sem reposi¸c˜ao, onde a ordem n˜ao importa Combina¸c˜ao-r Quantas maneiras pode-se escolher r s´ımbolos (objetos) de um total de n s´ımbolos diferentes, se • a ordem dos s´ımbolos n˜ao ´e importante, e • a repeti¸c˜ao n˜ao ´e permitida. Nota¸c˜ao: C(n, r). Exemplo: escolher trˆes s´ımbolos de um total de 5, ABCDE, d´a ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Outra formula¸c˜ao Quantos subconjuntos com r = 3 elementos tˆem um conjunto de n = 5 elementos? Combina¸c˜ao-r Combina¸c˜ao Permuta¸c˜ao ordem n˜ao importa ordem importa ABC ABC ACB BAC BCA CAB CBA ABD ABD ADB BAD BDA DAB DBA ABE as 6 permuta¸c˜oes de ABE ACD as 6 permuta¸c˜oes de ACD ACE as 6 permuta¸c˜oes de ACE ADE as 6 permuta¸c˜oes de ADE BCD as 6 permuta¸c˜oes de BCD BCE as 6 permuta¸c˜oes de BCE BDE as 6 permuta¸c˜oes de BDE CDE as 6 permuta¸c˜oes de CDE # total de combina¸coes = # total de permuta¸coes # total de permuta¸coes da selecao C(5, 3) = P(5, 3) 3! = 5 · 4 · 3 3 · 2 = 60 6 = 10 Combinação Fórmula combinação Quantas maneiras pode-se escolher r símbolos (objetos) de um total de n símbolos diferentes, se • a repetição de símbolos não é permitida, e • a ordem dos símbolos não é importante. Resposta: Dividimos o número de permutações P(n, r) pelo número de permutações P(r) dos símbolos escolhidos, para obter C(n, r) = P(n, r) / P(r) = n! / r!(n-r)! = (n r) Combina¸c˜ao Exemplo 23 Quantas m˜aos de 5 cartas podem ser retiradas a partir de um baralha de 52 cartas? C(52, 5) = 52! 5!47! = 52 · 51 · 50 · 49 · 48 5 · 4 · 3 · 2 · 1 = 2598960 Exemplo 24 Megasena: quantas maneiras existem para escolher 6 n´umeros do conjunto 1, . . . 60? C(60, 6) = 60! 6!54! = 60 · 59 · 58 · 57 · 56 · 55 6 · 5 · 4 · 3 · 2 · 1 = 50063860 Combinação: outra formulação Quantas subconjuntos de tamanho r existem de um conjunto com n elementos? • na definição de um conjunto, a ordem dos elementos não é importante, e • na definição de um conjunto, a repetição de elementos não muda o conjunto. Resposta: C(n, r) = n! / r!(n-r)! Corolário: ∑ (C(n, r) from r=0 to n) = 2^n Combina¸c˜ao: outra formula¸c˜ao Quantas maneiras pode-se dividir r objetos em dois grupos (onde um grupo vazio ´e permitido). • a ordem dos objetos n˜ao ´e importante, e • a repeti¸c˜ao de objetos n˜ao ´e permitida. Resposta: C(n, r) = n! r!(n − r)! Corol´ario: C(n, r) = C(n, n − r) Combina¸c˜ao: outra formula¸c˜ao Quantas strings bin´arias de tamanho n existem com exatamente r 1s (e portanto n − r 0s)? Resposta: C(n, r) = n! r!(n − r)! Prova: Existe uma bije¸c˜ao entre as strings de tamanho n e os subconjunto de um conjunto de tamanho n. Combinação Exemplo 25 Suponha que times de 5 pessoas vão ser formados de um grupo de 12 pessoas. Duas pessoas desse grupo (A e B) insistem em trabalhar conjuntamente. Assim, ao se formar um time, ou as duas pessoas estão presentes ou não. Quantos times podem ser formados? [N° total de times] = [N° de times que contêm A e B] + [N° de times que não contêm nem A nem B] I C(10, 3) = 10! / 3!.7! = 120 Os times que contêm A e B devem ter mais 3 pessoas das 10 restantes do grupo. II C(10, 5) = 10! / 5!.5! = 252 Os times que não contêm A e B devem ter 5 pessoas das 10 restantes do grupo. N° total de times = 120 + 252 = 372 Combinação Exemplo 26 Suponha o mesmo cenário anterior mas agora A e B não podem pertencer simultaneamente a um mesmo time. Quantos times podem ser formados? [Nº total de times ] = [ Nº de times com A e sem B ] + [ Nº de times com B e sem A ] + [ Nº de times sem A e sem B ] C(10,4) = \frac{10!}{4!.6!} = 210 I Os times com A e sem B devem ter mais 4 pessoas das 10 restantes do grupo (10 porque A e B estão fora II e 4 porque A é uma das 5 pessoas). C(10,4) = \frac{10!}{4!.6!} = 210 Idem ao anterior. III C(10,5) = \frac{10!}{5!.5!} = 252 Os times que não contêm A e B devem ter 5 pessoas das 10 restantes do grupo. Nº total de times = 210 + 210 + 252 = 672 Combinação Exemplo 26 Este problema também pode ser resolvido de outra forma: [Nº total de times ] = [ Nº de times com 5 pessoas ] - [ Nº de times com A e com B ] C(12,5) = \frac{12!}{5!.7!} = 792 I Total de times com 5 pessoas. C(10,3) = \frac{10!}{3!.7!} = 120 II Os times que contêm A e B devem ter mais 3 pessoas das 10 restantes do grupo. Nº total de times = 792 - 120 = 672 Combinação Exemplo 27 Suponha que o grupo de 12 pessoas seja formado por 5 homens e 7 mulheres. Quantos times de 5 pessoas podem ser formados com 3 homens e 2 mulheres? [Nº total de times ] = [ Nº de times com 3 homens ] \times [ Nº de times com 2 mulheres ] C(5,3) = \frac{5!}{2!.3!} = 10 I Total de times com 3 homens. C(7,2) = \frac{7!}{2!.5!} = 21 II Total de times com 2 mulheres. Nº total de times = 10 \times 21 = 210 Note que o princípio da multiplicação deve ser aplicado já que temos possibilidades diferentes para formação dos times. Combinação Exemplo 28 Suponha o mesmo grupo anterior. Quantos times de 5 pessoas podem ser formados com pelo menos um homem? Nº total de times = Nº de times com 5 pessoas - Nº de times com nenhum homem I C(12, 5) = 12! / 5! 7! = 792 Total de times com 5 pessoas incluindo homens e mulheres. II C(7, 5) = 7! / 5! 2! = 21 O total de times com nenhum homem é exatamente a quantidade de times formados apenas por mulheres. Nº total de times = 792 - 21 = 771 Combinação Exemplo 29 Suponha o mesmo grupo anterior. Quantos times de 5 pessoas podem ser formados com no máximo um homem? Nº total de times = Nº de times com nenhum homem + Nº de times com um homem I C(7, 5) = 7! / 5! 2! = 21 O total de times com nenhum homem é exatamente a quantidade de times formados apenas por mulheres. II C(5, 1) ⋅ C(7, 4) = 5! / 1! 4! ⋅ 7! / 4! 3! = 5 ⋅ 35 = 175 O total de times com um homem e quatro mulheres. Nº total de times = 21 + 175 = 196 Combina¸c˜ao Exemplo 30 Seja um baralho comum de 52 cartas que possui quatro naipes (♠, n, ♣, o) de 13 denomina¸c˜oes cada (A, 2, 3, . . . , 10, J, Q, K). (a) De quantas formas diferentes pode-se ter uma “m˜ao de poker” (cinco cartas) todas do mesmo naipe? – Uma “m˜ao de poker” pode ser constru´ıda em dois passos sucessivos: selecione um naipe e, em seguida, escolha cinco cartas desse naipe. Pelo princ´ıpio da multiplica¸c˜ao temos: 4 · C(13, 5) = 5 148. (b) De quantas formas diferentes pode-se ter uma “m˜ao de poker” contendo trˆes cartas de uma denomina¸c˜ao e duas cartas de uma outra denomina¸c˜ao? – Essa “m˜ao de poker” pode ser constru´ıda em quatro passos sucessivos: (1) selecione a primeira denomina¸c˜ao para as trˆes cartas (2) selecione os trˆes naipes dessa denomina¸c˜ao (3) selecione a segunda denomina¸c˜ao para as outras duas cartas (4) selecione os dois naipes dessa denomina¸c˜ao. Pelo princ´ıpio da multiplica¸c˜ao temos: 13 · C(4, 3) · 12 · C(4, 2) = 3 744. Combina¸c˜ao Exemplo 31 Dado um grid n × m, quantas caminhos existem entre a posi¸c˜ao (0, 0) (canto inferior esquerdo) at´e a posi¸c˜ao (n, m) (canto superior direito) se os ´unicos movimentos poss´ıveis s˜ao mover para a direita (D) ou para cima (C)? ... (0,0) (n,m) ... ... ... ... ... ... .. ... ... ... ... ... ... . Combinação Exemplo 31 (continuação) Cada rota pode ser expressa por uma sequência de D's e C's, sendo que existem exatamente n D's e m C's, ou seja, cada rota possui n + m passos. Existe uma bijeção entre este problema e a seguinte pergunta: Quantas string compostas de Cs e Ds e de tamanho n + m existem com exatamente n Ds? (n + m) n = (n + m)! / n! m! An´alise Combinat´oria COEFICIENTES BINOMIAIS Introdução ► As expressões \( \frac{n!}{r!(n-r)!} \) tem papel importante na matemática. ► É chamada de coeficiente binomial. ► Notação: \( \binom{n}{r} = \frac{n!}{r!(n-r)!} \) ► Vale a pena estudar suas propriedades. Exemplo (a + y)3 = (a + y)(a + y)(x + y) = (xx + xy + yx + yy)(x + y) Exemplo (x + y)3 = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y) = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy Exemplo (x + y)3 = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y) = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy = (xxx) + (xxy + xyx + yxx) + (xyy + yxy + yyx) + (yyy) Exemplo (x + y)3 = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y) = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy = (xxx) + (xxy + xyx + yxx) + (xyy + yxy + yyx) + (yyy) = C(3, 0)x3 + C(3, 1)x2y + C(3, 2)xy 2 + C(3, 3)y 3 Exemplo \((x+y)^3\)\=\( (x+y)(x+y)(x+y)\) \=\( (xx+xy+yx+yy)(x+y)\) \=\( C(3,0)x^3 + C(3,1)x^2y + C(3,2)xy^2 + C(3,3)y^3 \) \=\( \binom{3}{0}x^3+ \binom{3}{1}x^2y + \binom{3}{2}xy^2 + \binom{3}{3}y^3 \) \=\( \sum_{i=0}^{3} \binom{3}{i}x^{3-i}y^i \) Binômio de Newton \((x+y)^n\) \=\( \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \ldots \) \+\( \ldots + \binom{n}{n-1}xy^{n-1} + \binom{n}{n}y^n \) \=\( \sum_{i=0}^{n} \binom{n}{i}x^{n-i}y^i \) Triângulo de Pascal (0 0) (1 0) (1 1) (2 0) (2 1) (2 2) (3 0) (3 1) (3 2) (3 3) (4 0) (4 1) (4 2) (4 3) (4 4) (5 0) (5 1) (5 2) (5 3) (5 4) (5 5) (6 0) (6 1) (6 2) (6 3) (6 4) (6 5) (6 6) (7 0) (7 1) (7 2) (7 3) (7 4) (7 5) (7 6) (7 7) (8 0) (8 1) (8 2) (8 3) (8 4) (8 5) (8 6) (8 7) (8 8) ... By Pascal's identity: (6 4) + (6 5) = (7 5) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 ... Triângulo de Pascal ► Figura 5.4.1 do livro ► Identidade de Pascal: uma entrada é a soma das duas entradas diagonalmente em cima dela. (n+1 r) = (n r−1) + (n r) ► A soma da n-ésimo linha é 2^n. ∑(i=0 to n) (n i) = 2^n ► A soma alternada da n-ésimo linha é 0. ∑(i=0 to n) (-1)^i (n i) = 0 Identidade de Pascal Prova combinatória Considera um grupo de n+1 pessoas, e fixa uma delas, chamada A. Seja X o conjunto de todos os comitês com r membros. Podemos dividir X em duas classes: X₁, os comitês a qual A pertence; e X₂, os a qual A não pertence. X₁: Na primeira classe, dado que o comitê contém A, resta uma escolha de r−1 membros de um total de n, correspondendo a C(n,r−1) combinações. X₂: Na segunda classe, dado que o comitê não contém A, resta uma escolha de r membros de um total de n, correspondendo a C(n,r) combinações. Prova algébrica Fórmula de Pascal – Prova algébrica \(\binom{n}{r-1}\) + \(\binom{n}{r}\) = \(\frac{n!}{(r-1)!(n-r+1)!}\) + \(\frac{n!}{r!(n-r)!}\) Como conseguir um denominador comum? À esquerda falta um fator \(r\), e à direita um fator \(n-r+1\). \(\binom{n}{r-1}\) + \(\binom{n}{r}\) = \(\frac{n!}{(r-1)!(n-r+1)!}\) + \(\frac{n!}{r!(n-r)!}\) = \(\frac{r}{r} \cdot \frac{n!}{(r-1)!(n-r+1)!}\) + \(\frac{n-r+1}{n-r+1} \cdot \frac{n!}{r!(n-r)!}\) = \(\frac{r \cdot n! + n!(n-r+1)}{r!(n-r+1)!}\) = \(\frac{(n+1)!}{r!((n+1)-r)!}\) = \(\binom{n+1}{r}\)