NOTAS DE AULAS-ANÁLISE COMBINATÓRIA

Prévia do material em texto

PROFESSORA: HÉLIA TAVARES 
 
MATEMÁTICA DISCRETA 
NOTAS DE AULA: ANÁLISE COMBINATÓRIA 
 
 
Análise Combinatória : é a área da Matemática que trata dos problemas de Contagem. 
Exemplos 
a) Quanto espaço de armazenamento um determinado banco de dados usa? 
b) Quantos usuários uma determinada configuração de computador pode suportar? 
c) Quantos cálculos são efetuados por um determinado algoritmo? 
d) Quanto de memória será utilizado por um determinado programa que faz alocação dinâmica de 
memória? 
 
PRINCÍPIOS DA CONTAGEM 
1) Princípio da Multiplicação 
2) Princípio da Adição 
 
1) PRINCÍPIO DA MULTIPLICAÇÃO E ÁRVORE DE POSSIBILIDADES 
Para enunciarmos o princípio fundamental da contagem , utilizaremos um processo descritivo, chamado : 
diagrama de árvore, que ajuda na vizualização de quais e de quantas são as possibilidades.O princípio 
fundamental da contagem , permite que a contagem seja feita sem a descrição das possibilidades. 
 
Exemplos 
 
1) Um jovem possui 3 camisas (A, B, C) e 2 calças ( a, b ) usando apenas essas peças, de quantas maneiras 
diferentes este jovem pode se vestir? 
2) Considere um sistema computacional que possui quatro unidades de Entrada/Saída A, B, C e D e três 
processadores X, Y e Z. Qualquer unidade de E/S pode ser conectada a um processador. Quantas 
possibilidades existem de conectar uma unidade de E/S? 
 
Princípio da Multiplicação: Se existem n 1 resultados possíveis para um primeiro evento e n 2 
para um segundo, então existem n 1x n2 resultados possíveis para a sequência dos eventos. O princípio 
da multiplicação pode ser estendido, a uma sequência com qualquer número finito de eventos. 
 
Exemplos 
1) Quantos números de 3 algarismos, podemos formar com os números 1, 2 e 3? 
2) Quantos números de 3 algarismos distintos podemos formar com os números 1, 2 e 3? 
3) Os números de telefones de uma cidade tem 8 algarismos. Determine a quantidade máxima de 
telefones a serem instalados, sabendo que os números não podem começar por zero? 
4) Usando somente os algarismos 1, 2, 3, 4, 5 e 6: 
a) Quantos números pares de 2 algarismos podemos formar? 
b) Quantos números de 2 algarismos podemos formar? 
c) Quantos números de 2 algarismos distintos podemos formar? 
d) Quantos números de 2 algarismos pares podemos formar? 
 
 
Princípio da Adição: Se A e B são eventos disjuntos com n 1 e n 2 resultados possíveis, 
respectivamente, então o número total de possibilidades para o evento A ou B, é n1 + n 2. Também pode 
ser estendido a qualquer número finito de eventos disjuntos. 
 
Exemplos 
1) Um consumidor deseja comprar um veículo de uma concessionária. A concessionária tem 18 
automóveis e 10 caminhões em estoque. Quantas escolhas possíveis o consumidor tem? 
2) Na linguagem de programação BASIC, um identificador tem que ser uma única letra ou uma letra 
seguida de um único dígito. Quantos identificadores podemos formar? ( considere o alfabeto de 26 
letras) 
OBS. O princípio da Adição, é usado, geralmente, junto com o princípio da multiplicação 
 
1) Quantos números inteiros existem no intervalo [1, 100.000] que contém o algarismo 6 exatamente 
uma única vez? 
 
 
FATORIAL: produto 
 Representação: n! (lê-se n fatorial) N! = n(n-1)(n-2)...2x1, onde n E IN e n≥ 1 
 Obs.: 0! = 1 
 1! = 1 
 
EXEMPLOS: 
1) 7! 2) n! 3) _5!_ 4) 7! – 6! 5) (n+1)! Com n≥1 
 5! (n-2)! 3! + 2! 5! (n-1)! 
 
2) Resolva a equação: ( x+ 2 ) ! = 6 
 x! 
 
TÉCNICAS DE CONTAGEM 
Para desenvolver as técnicas de contagem vamos ver os diferentes tipos de agrupamentos: Arranjos, 
Permutações e Combinações . 
 
ARRANJOS SIMPLES: 
Exemplos 
1) Dado o conjunto A = { 1,2, 3 }, escreva todos os números de dois algarismos distintos com os 
elementos de A. 
2) Um sorteio tem 2prêmios diferentes: um carro e uma bicicleta. 10 pessoas participaram , quantas 
possibilidades ela possuem de concorrer? 
 
ARRANJOS SIMPLES: Dado um conjunto com n elementos, chama-se arranjo simples ( sem 
repetição) de p elementos distintos qualquer grupo formado por p dos n elementos (p≤n ), de modo que 
um grupo difere do outro ou pela natureza dos elementos ou pela ordem dos elementos. 
 
Indica-se : A n,p 
lê-se: arranjo: de n elementos , tomados p a p 
onde: n-número total de elementos 
 p- número total de elementos em cada grupo 
 
FÓRMULA DOS ARRANJOS SIMPLES 
 
A n, p = n! 
 (n-p)! 
 
 
 
Exemplos 
 
1) Quantos números de 2 algarismos diferentes, podemos escrever com os algarismos 1, 2, 3 e 4? 
 
2)Considere a palavra BASIC: 
a) Quantos anagramas são formados com as letras dessa palavra? 
b) Quantos deles começam por B e terminam com C? 
c) Quantos contêm as letras IC juntas e nessa Ordem? 
 
3) Quantos números pares de 4 algarismos obtemos com os algarismos 1,2,3,4,5 e 6? 
 
4) Quantos números ímpares de 4 algarismos não repetidos podemos escrever com os algarismos 1, 2, 3, 
4, 5, 6, 7, 8 e 9? 
5) Um estudante tem 5 lápis de cores diferentes. De quantas maneiras ele poderá pintar os Estados da 
região Sul do Brasil, cada um de uma cor? 
 
 
PERMUTAÇÂO SIMPLES : é o tipo de agrupamento ordenado, sem repetições, em que entram 
todos os elementos em cada grupo. 
Indicaremos o número de permutações por Pn onde n é total de elementos e lê-se: permutação de n. 
 
Permutação, nada mais é , que um caso particular de arranjo simples, onde em cada grupo 
entram todos os elementos do conjunto dado ou seja, p=n. 
 
FÓRMULA DA PERMUTAÇÃO SIMPLES : Pn= n! 
 
 
Exemplos 
 
1) Quantos números de 4 algarismos distintos podem ser formados, usando-se os algarismos 
1,3,5,e,7? 
2) Quantos anagramas tem a palavra MITO? 
 
3)a_ Quantos são os anagramas da palavra PERDÃO? 
 b- Quantos são os anagramas iniciados por P e terminados em O? 
 c- Quantos são os anagramas da palavra PERDÃO em que as letras A e O aparecem juntas e nessa 
ordem? 
 d- Quantos são os anagramas da mesma palavra em que as letras P e O aparecem nos extremos? 
 
4) De quantas maneiras uma família de 5 pessoas podem sentar-se num banco de 5 lugares ficando 
duas delas ( por exemplo, pai e mãe) sempre juntas , em qualquer ordem? 
 
 
PERMUTAÇÃO COM REPETICÕES 
A permutação de n elementos dos quais α são de um tipo; β são de outro tipo e λ de outro, com α + 
β+ λ = n é dado por: 
 
EXEMPLOS 
 
1) Quantos são os anagramas da palavra BATATA? 
2) Quantos anagramas tem a palavra PAPA? 
 
 
 
 
COMBINAÇÃO SIMPLES: é um tipo de agrupamento sem repetição em que um grupo difere do 
outro apenas pela natureza dos elementos. 
 Exemplo: 
Quantas comissões de 2 pessoas podem ser formadas com 5 alunos(A, B, C, D, e E ) de uma classe? 
 Indicaremos Combinação por: C n,p (n elementos tomados p a p) 
 
 FÓRMULA COMBINAÇÃO SIMPLES 
 
 C n, p = A n, p 
 P! 
 
C n, p - lê-se: combinação simples de n elementos p a p 
 
 
Propriedade Importante da Combinação: C n, p = C n, p-1 
 
Chama-se de igualdade das combinações complementares, e é útil para simplificar os cálculos das 
combinações. 
 
Exemplos 
 
1)Calcule: 
a) C 6,3 
b) 
c) 
 
2) De quantas maneiras diferentes um técnico pode escalar seu time de basquete tendo 12 atletas à 
sua disposição ? 
 
3) O conselho desportivo de uma escola é formado por 2 professores e 3 alunos. Candidataram-se 5 
professores e 30 alunos.De quantas maneiras diferentes esse conselho pode ser eleito? 
 
4) Num vôo da ponte aérea Rio-São Paulo há apenas 7 lugares disponíveis e um grupo de 10 pessoas 
pretende embarcar nesse vôo. De quantas maneiras é possível lotar o avião? 
 
 
 
 
CONCLUSÕES FINAIS 
 
Dado um conjunto com n elementos, vimos que há três tipos de agrupamentos que podem ser 
formados com esses elementos: ARRANJOS SIMPLES, PERMUTAÇÔES SIMPLESE 
COMBINAÇÔES SIMPLES. Chamadas simples porque são agrupamentossem elementos repetidos. 
O tipo de agrupamento quem determina é o enunciado do problema, no entanto, se isto não for 
possível, podemos usar o seguinte critério: 
 
1) Com elementos do conjunto dado fazemos um agrupamento conforme o enunciado do problema. 
2) Trocamos a ordem desses agrupamentos. 
3) Se com a ,troca da ordem tivermos um novo agrupamento, esse agrupamento será arranjo 
simples ou permutação simples caso n=p 
4) Se com a troca da ordem não tivermos um novo agrupamento, esse agrupamento será 
combinação simples 
 
 
Exemplos 
1) Quantos números de 3 algarismos distintos podemos formar com os algarismos 1, 2, 3, 4e 5? 
 
2) De quantas maneiras diferentes , pode3m ser arrumados numa prateleira 5 livros diferente? 
 
3) Quantos segmentos de extremidades, ficam determinados com os pontos A, B, C,e D? Dado 
 
 
 B 
 
 C 
 A 
 
 
 D