Contagem Matemática Aplicada a Computação

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO 
Aula 4: Contagem 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Contagem 
AULA 4: Contagem 
Matemática 
Combinatória 
Contagem 
Situações do Cotidiano: 
1. Combinações de roupa 
2. Rotas e caminhos 
3. Cardápio 
4. Formações de grupos 
5. Competições etc. 
… … 
Principio da Multiplicação Principio da Adição 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Arranjos 
 
Ideia: São caracterizados pela natureza e pela ordem dos elementos escolhidos. 
 
Exemplo: B = {2, 4, 6, 8}. Grupos de dois elementos do conjunto B. 
 
 {(2,4), (2,6), (2,8), (4,2), (4,6), (4,8), (6,2), (6,4), (6,8), (8,2), (8,4), (8,6)} 
 
 
2 4 
6 
8 
⁞ 
Arranjos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Arranjos 
 
Pela natureza dos elementos: (2,4)  (4,8) 
Pela ordem dos elementos: (1,2)  (2,1) 
 
Arranjos simples 
 
Arranjos simples de n elementos tomados p a p , onde n = 1 e p é um número natural tal que p = n, 
serão todos os grupos de p elementos distintos, que diferem entre si pela ordem e pela natureza 
dos p elementos que compõem cada grupo. 
 
Notação: Ap n 
Arranjos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Arranjos simples 
 
Usando o Princípio Multiplicativo 
 
n elementos dos quais queremos tomar p ou podemos dizer temos n objetos com os quais 
queremos preencher p lugares. 
10 lugar 20 lugar 30 lugar … 
n n - 1 n - 2 … 
Lugar p 
n-(p-1) 
Princípio Multiplicativo 
 
n.(n-1).(n-2)...(n-(p-1)) maneiras diferentes 
Arranjos 
| 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Princípio Multiplicativo 
 
n.(n-1).(n-2)...(n-(p-1)) maneiras diferentes 
Arranjos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Exemplo: Em um colégio, dez alunos candidataram-se para ocupar os cargos de presidente e 
vice-presidente do grêmio estudantil. De quantas maneiras distintas a escolha poderá ser feita? 
 
Temos dez alunos disputando duas vagas, portanto, dez elementos tomados dois a dois, onde 
n = 10 e p = 2. Portanto A = 90 
⁞ 
Presidente Vice 
⁞ 
Arranjos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Arranjo com repetição 
 
Todos os elementos podem aparecer repetidos em cada grupo de p elementos. 
 
 Ar(m,p) = m
p 
 
Exemplo: Seja C = {A,B,C,D}, m = 4 e p = 2. 
 
• 4 elementos 
• tomados 2 a 2 
• 16 grupos (com repetição). 
 
 Ar(4,2) = 4
2 = 16. 
Arranjos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Arranjo condicional 
Todos os elementos aparecem em cada grupo de p elementos, mas existe uma condição que 
deve ser satisfeita acerca de alguns elementos. 
 
 N=A(m1,p1).A(m-m1,p-p1) 
 
Exemplo: Quantos arranjos com 4 elementos do conjunto {A,B,C,D,E,F,G}, começam com duas 
letras escolhidas no subconjunto {A,B,C}? 
 
• m = 7 letras, 
• taxa é p = 4, 
• subconjunto escolhido tem m1 = 3 
• taxa que este subconjunto será formado é p1 = 2. 
 
Com as letras A,B e C, tomadas 2 a 2, temos 6 grupos que estão no conjunto: 
 N=A(3,2).A(7-3,4-2)=A(3,2).A(4,2)=6×12=72. 
Arranjos 
| 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Permutação simples 
 
Caso particular de arranjo, onde os elementos formarão agrupamentos que se diferenciarão 
somente pela ordem. 
 
Exemplo: As permutações simples dos elementos P, Q e R são: PQR, PRQ, QPR, QRP, RPQ, RQP. 
 
Permutação simples: P = n! onde n! = n*(n-1)*(n-2)*(n-3)*....*3*2*1 
 
Permutação 
| 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Permutação com elementos repetidos 
 
A cada um dos agrupamentos que podemos formar com certo número de elementos onde, ao 
menos um deles ocorre mais de uma vez tal que a diferença entre um agrupamento e outro se dê 
pela mudança de posição entre seus elementos. 
 
Exemplo: Quantos anagramas podemos formar com a palavra ARARA ? 
 
Note: 5 letras porém 2 letras distintas. 
A = 3 vezes 
R = 2 vezes. 
Permutação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Permutação com elementos repetidos 
 
 
Letra R: P2 = 2! = 2 
 
20/ 2 = 10, que é o número total de permutações das letras da palavra ARARA, sem considerarmos 
as permutações das letras A entre si, e das letras R também entre elas mesmas. 
 
P(3,2) 5 = 5! / (3! 2!) = 10 
𝑃3 = 3! = 6 
𝑃5 = 5! = 120 
 
𝑃3 / 𝑃5 = 20 que é o número de permutações, já desconsiderando-se as permutações entre as três 
letras A. 
Permutação 
| 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Permutação Circular 
 
Exemplo: Uma família é composta por seis pessoas: o pai, a mãe e quatro filhos. Em um restaurante, 
essa família vai ocupar uma mesa redonda. Em quantas disposições diferentes essas pessoas podem 
se sentar em torno da mesa de modo que o pai e a mãe fiquem juntos? 
 
• pai e mãe devem ficar juntos, (único bloco) 
• 5 elementos. 
• pai está à esquerda da mãe. 
 
Permutação circular (Pc) com 5 elementos 
 
Pc
5 = (5-1)! = 4! = 4.3.2.1 = 24 
• pai à direita da mãe = mais 24 posições diferentes. 
 
Portanto, o número total de disposições é 48. 
Permutação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Combinações simples 
 
Combinações simples de n elementos tomados p a p, onde n = 1 e p é um número natural tal que 
p = n, são todas as escolhas não ordenadas de p desses n elementos. 
 
Cp n= n . (n -1) (n -2) ... (n - (p-1)) / ( p. (p -1) ... 3.2.1) = A
p n / p! = n ! / (n-p)! p! 
 
• combinação: conjunto com p elementos da n-upla original 
• arranjo: p-upla com os elementos da n-upla original 
• combinação apenas escolhemos os p elementos 
• arranjo além da escolha temos que permutar os elementos escolhidos. 
 
Usaremos: 
• arranjo ou permutação quando a ordem for importante 
• combinação quando a ordem não for importante. 
Combinação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Exemplo: (AFA 1999) Quatro pontos não coplanares determinam, exatamente, quantos 
planos? 
 
Solução: três pontos não coplanares determinam um único plano, assim cada subconjuntos de três 
pontos dos quatro dados determinam um único plano, então: 
 
 
 Cp n= 4! / (3! (4 - 3)! = 4 
egeom.blogspot.com 
Combinação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Combinação com repetição 
 
 
Todos os elementos podem aparecer repetidos em cada grupo até p vezes. 
 
 
Cr(m,p)=C(m+p-1,p) 
 
 
 
 
 
Exemplo: Seja C={A,B,C,D}, m = 4 e p = 2. As combinações tomados 2 a 2 são 10 grupos que têm 
todas as repetições possíveis de elementos em grupos de 2 elementos não podendo aparecer o 
mesmo grupo com a ordem trocada. 
Combinação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Combinação com repetição 
 
 
Exemplo: Seja C={A,B,C,D}, m = 4 e p = 2. As combinações tomados 2 a 2 são 10 grupos que têm 
todas as repetições possíveis de elementos em grupos de 2 elementos não podendo aparecer o 
mesmo grupo com a ordem trocada. 
 
16 elementos: Cr={AA,AB,AC,AD,BA,BB,BC,BD,CA,CB,CC,CD,DA,DB,DC,DD} 
 
 
Excluir deste conjunto 6 grupos: AB=BA, AC=CA, AD=DA, BC=CB, BD=DB e CD=DC 
 
 Cr={AA,AB,AC,AD,BB,BC,BD,CC,CD,DD} 
Cálculo: Cr(4,2)=C(4+2-1,2)=C(5,2)=5!/[2!3!]=10 
Combinação 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Sugestão de resolução dos exercícios propostos. 
 
1 - De quantas maneiras podemos dividir 10 rapazes em dois grupos de cinco? 
 
 
Primeiro grupo : 𝐶10,5 modos. 
Segundo grupo: 5 pessoas e só há uma maneira de formar o segundo grupo. 
Portanto: 𝐶10,5 . 1 
 
Observação: contamos cada divisão duas vezes. 
 
Exemplo: divisão dos rapazes nos dois grupos {a, b, c, d, e} e {f, g, h, i, j} = {f, g, h, i, j} e {a, b, c,d, e} 
Exercícios Propostos 
MATEMÁTICAAPLICADA A COMPUTAÇÃO 
AULA 4: Contagem 
Sugestão de resolução dos exercícios propostos. 
 
2- Em época de eleição para o grêmio estudantil do colégio, houve 12 candidatos aos cargos de 
presidente, vice-presidente e secretário. De quantos modos diferentes estes candidatos poderão 
ocupar as vagas deste grêmio? 
 
Solução: Como há 3 vagas diferentes, a ordem importa, então teremos: 
 
• 12 possibilidades de candidatos para primeira vaga, 
• 11 possibilidades de candidatos para a segunda vaga e 
• 10 possibilidades de candidatos para a terceira vaga. 
 
 
Portanto há 12 x 11 x 10 = 1320 modos diferentes desses candidatos ocuparem as vagas deste grêmio. 
Exercícios Propostos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Sugestão de resolução dos exercícios propostos. 
 
3- Juquinha tem 8 calças e 5 camisetas diferentes. De quantas maneiras Juquinha pode escolher 
2 peças de roupa? 
 
 Teremos 3 “tipos” de escolha: 
 
• 2 calças, 
• 2 camisas 
• 1 calça e uma camisa. 
 
 
 
Se forem 2 calças: (8 x 7)/2 = 28 maneiras de escolher duas peças de roupa. 
 Se forem duas camisas: (5 x 4)/2= 10 maneiras de escolher duas peças de roupa. 
 Se forem uma calça e uma camisa: 8 x 5 = 40 maneiras de escolher duas peças de roupa. 
 
Princípio aditivo e somamos todas essas possibilidades: 28 + 10 + 40 = 78 possibilidades de escolha. 
dreamstime.com 
Exercícios Propostos 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Indicação de Leitura 
AULA 4: Contagem 
Indicação de Leitura Específica 
 
• Recomendamos a leitura do capítulo referente Teoria de Conjuntos no material didático. 
• Acesse a Biblioteca Virtual da Estácio e pesquise mais exercícios nos livros de Teoria de Conjuntos 
disponíveis. 
 
Recomendação de leitura no material didático: 
MINELLI, Juliano. Matemática Discreta. 1. ed. Rio de Janeiro: SESES, 2015, p. 11-19. 
 
Sugestão de material: 
http://www.univasf.edu.br/~jorge.cavalcanti/Mat_Disc_Parte08.pdf 
http://www.univasf.edu.br/~jorge.cavalcanti/Mat_Disc_Parte08.pdf 
http://www.matematicadidatica.com.br/PrincipioFundamentalContagem.aspx 
 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Indicação de Leitura 
AULA 4: Contagem 
Indicação de Leitura Específica 
 
Sugestão de leitura: Contagem 
 
http://educacao.globo.com/matematica/assunto/matematica-basica/conjuntos.html 
 
http://www.somatematica.com.br/emedio/conjuntos.php 
 
http://pessoal.sercomtel.com.br/matematica/medio/conjuntos/conjunto.htm 
 
 
VAMOS AOS PRÓXIMOS PASSOS? 
 
 
Unidade 2 - Contagem 
 
- Arranjo 
- Permutação 
- Combinação