Slide - Aula 11 Elementos de Análise Combinatória - Matemática Discreta 2021-2

Matematica Discreta — Aula 11 — r= Elementos de andlise combinatoria Jamil Abreu UFLA/ICET/DMM Lavras/MG Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 1/24 Princ´ıpio geral de contagem Se um experimento consiste de r etapas, onde a primeira das etapas admite n1 resultados; para cada um dos n1 resultados acima a segunda etapa admite n2 resultados; para cada um dos n1n2 resultados acima a terceira etapa admite n3 resultados, e assim por diante. Ent˜ao o experimento consiste de n1n2 · · · nr resultados. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 2 / 24 Exemplo De quantas maneiras se pode alinhar 4 objetos A, B, C e D? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 3 / 24 Solu¸c˜ao H´a 4 possibilidades de se escolher o primeiro objeto, 3 possibilidades de escolher o segundo, 2 possibilidades de se escolher o terceiro e 1 possibilidade de se escolher o quarto. Logo existem 4! = 4 · 3 · 2 · 1 = 24 maneiras de se alinhar os 4 objetos. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 4 / 24 Defini¸c˜ao Para cada natural n, n! = n · (n − 1) · (n − 2) · · · 3 · 2 · 1 ´e o fatorial de n. Convenciona-se 0! = 1. Isto faz com que v´arias f´ormulas envolvendo naturais n = 1, 2, 3, . . . continuem v´alidas para n = 0. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 5 / 24 Exemplo Um estudante da UFLA tem 12 livros, sendo 5 de C´alculo, 4 de F´ısica e 3 de Qu´ımica. De quantas maneiras ele pode organizar os livros em sua estante de modo que os livros fiquem sempre juntos por assunto? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 6 / 24 Solu¸c˜ao Supondo que a ordem da esquerda para a direita seja C´alculo, F´ısica e Qu´ımica, existem 5! maneiras de organizar os livros de C´alculo, 4! maneiras de organizar os livros de F´ısica e 3! maneiras de se organizar os livros de Qu´ımica. Logo, existem 5!4!3! maneiras de se organizar os livros na ordem acima. Como existem 3! maneiras de se permutar os assuntos, o n´umero total ´e 3!5!4!3! = 103.680. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 7 / 24 Exemplo De quantas maneiras se pode alinhar 3 objetos dentre os 5 objetos A, B, C, D e E? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 8 / 24 Solu¸c˜ao H´a 5 possibilidades de se escolher o primeiro objeto, 4 possibilidades de escolher o segundo e 3 possibilidades de se escolher o terceiro. Logo existem 5 · 4 · 3 = 60 maneiras de se alinhar os objetos da forma pedida. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 9 / 24 Observa¸c˜ao Alguns autores denominam permuta¸c˜oes de r objetos tomados dentre n objetos, como no exemplo anterior, de arranjos n a r. Nota¸c˜ao: A(n, r). (Dentre outras, como Ar n, etc.) Note que A(n, r) = n! (n − r)!. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 10 / 24 Exemplo Quantas diferentes disposi¸c˜oes h´a da palavra BATATA? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 11 / 24 Solu¸c˜ao Primeiro, note que, fossem os A’s e os T’s diferentes, por exemplo BATATA, ent˜ao haveria 6! permuta¸c˜oes (disposi¸c˜oes) diferentes destas 6 letras. Por´em, como os A’s e os T’s n˜ao s˜ao diferentes, apenas na disposi¸c˜ao acima h´a 3! outras em que apenas os A’s permutam entre si e outras 2! em que apenas os T’s permutam entre si. Logo, o n´umero de permuta¸c˜oes distintas ´e 6! 3!2! = 60. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 12 / 24 Generalizando. . . O mesmo argumento do exemplo anterior mostra que h´a n! n1!n2! · · · nr! permuta¸c˜oes distintas de n objetos em que n1 s˜ao “iguais”, n2 s˜ao “iguais”, etc. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 13 / 24 Problema Suponha que queiramos formar grupos de tamanho r a partir de n objetos. Quantos grupos s˜ao poss´ıveis? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 14 / 24 Solu¸c˜ao Supondo que a ordem ´e relevante, existem n escolhas para o primeiro objeto, (n − 1) escolhas para o segundo, (n − 2) escolhas para o terceiro e, assim por diante, de modo que existem (n − r + 1) escolhas para o r-´esimo. Portanto, o n´umero de grupos ordenados de tamanho r ´e n(n − 1) · · · (n − r + 1) = n! (n − r)!. Agora, cada grupo de tamanho r pode ser permutado r! vezes. Assim, o n´umero de grupos n˜ao ordenados (combina¸c˜oes) ´e C(n, r) def= n! (n − r)!r!. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 15 / 24 Definicao O nimero C(n, r) é comumente denotado por n nl r) (n=) Ir? que denominamos coeficiente binomial na r. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 16 / 24 Exemplo Um comitˆe de 5 pessoas deve ser formado a partir de um grupo constitu´ıdo por 4 homens e 7 mulheres. 1 Quantos comitˆes h´a ao todo? 2 Quantos comitˆes h´a que sejam formados por 2 homens e 3 mulheres? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 17 / 24 Solucao . 11 . LA @ Existem ao todo (5) maneiras de se formar um comité. . 4 ys 7 nos @ Existem (5) possiveis escolhas de 2 homens e (3) possiveis escolhas de 3 mulheres. Logo, ha 4 7 2 3 maneiras de se escolher 2 homens e 3 mulheres para compor o comité. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 18 / 24 Exemplo Numa f´abrica de antenas produziu-se numa certa manh˜a n antenas das quais m eram defeituosas e n − m eram funcionais. Por algumas raz˜ao, o gerente determinou que as antenas fossem alinhadas de modo que n˜ao houvesse duas antenas defeituosas lado a lado. De quantas maneiras essa disposi¸c˜ao pode ser feita? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 11 19 / 24 Solucao Uma maneira é dispor as n — m antenas funcionais na forma -1-1.1_...1_1_ onde “1” denota uma antena funcional e “_” denota um local vago entre duas antenas funcionais, onde se pode colocar uma antena defeituosa. Ha n— m-+ 1 lugares vagos, dos quais podemos selecionar m onde alocar antenas defeituosas. Logo, ha n—-m+4+1 m possiveis disposicdes em que nado ha duas antenas defeituosas lado a lado. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 20 / 24 Uma identidade fundamental A identidade n n-1 n-1 = + r=1,2,...,n é fundamental e pode ser demonstrada analiticamente. Ela também pode, como muitas outras, ser estabelecida por um argumento combinatorio. Considere n objetos e distingua um entre eles. O ndimero de grupos de tamanho r é igual ao de grupos de tamanho r que contém o objeto mais o de grupos que nao contém o tal objeto. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 21/24 A identidade anterior os permite construir o tridngulo de Pascal: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 G) @ Ge Gt) G) A n-ésima linha fornece os coeficientes do bin6dmio de Newton: “.(n ni n—k_k (ey =o (f)xhyh k=0 Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 22/24 Exemplos 2 2 2 (x+y)? _~ xy? +4 xty? 4 x°y? 0 1 2 = x? + 2xy + y?; 3 3 3 3 3 3,0 21 1,2 0,3 (x+y) (5) *(Q)%y + G)ey + (G)*v = x3 + 3x?y + 3xy? + y?3; Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 23 / 24 Exemplo n n n n wae =". De fato, ambos os lados sao (1 + 1)”. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 11 24/24