Contagem / Análise Combinatória

Prévia do material em texto

19/03/2017
1
CONTAGEM
II - CONTAGEM
A análise combinatória é o ramo da matemática que trata de
contagem então quando associamos essa ideia a programação
notaremos que este conteúdo será importante sempre que
temos recursos finitos.
Podemos citar como exemplo o que acontece quando temos o
problema de espaço de armazenamento em um banco de
dados ou quando precisamos determinar quantos usuários uma
determinada configuração de servidor pode suportar.
1 - Princípio da Multiplicação
Muitos problemas de contagem podem ser resolvidos a partir
de uma árvore de possibilidades. A teoria de árvore será
trabalhada em programação.
Ex.: Uma criança pode escolher uma entre duas balas, uma
rosa e outra preta, e um entre três chicletes, um amarelo,
outro verde e outro branco. Quantos conjuntos diferentes a
criança pode ter?
Podemos resolver o problema, separando a escolha dos doces
em 2 etapas sequenciais.
Escolher primeiro a bala e depois o chiclete:
Pela árvore, percebe-se que existem 2 x 3 = 6 possibilidades:
{R,A} {R,V} {R,B} {P,A} {P,V} {P,B}
Mesmo que a sequencia de eventos fosse trocada, o número de
possibilidades seria o mesmo, 3 x 2 = 6.
Esse exemplo ilustra o fato de que o número total de resultados
possíveis para uma sequência de eventos pode ser obtido
multiplicando-se o número de possibilidades do primeiro evento
pelo número do segundo.
19/03/2017
2
1 - Princípio da Multiplicação
 Se existem n1 resultados possíveis para um primeiro evento e n2
para o segundo, então existem n1.n2 resultados possíveis para
a sequência dos dois eventos.
Ex.: A última parte do seu número de telefone possui 04 dígitos.
Quanto desses números de 04 dígitos existem?
O primeiro pode ser escolhido entre 0 a 9, há 10 possibilidades
para a primeira opção.
As seguintes também terão cada uma 10 opções. Usando o
princípio da multiplicação, devemos multiplicar essas
possibilidades para cada tarefa.
10 . 10 . 10 . 10 = 10.000 números diferentes.
Se um elemento não puder ser usado de novo (não são permitidas
repetições), o número de possibilidades é afetado.
1 - Princípio da Multiplicação
Ex.: No sistema brasileiro de placas de carro, cada placa é
formada por três letras e quatro algarismos. Quantas placas onde
o número formado pelos algarismos seja par, podem ser formadas?
Existem 26 letras.
26 x 26 x 26 = 17.576  parte das letras
Para que o numero formado seja par, teremos de limitar o ultimo
algarismo à um numero par.
10 x 10 x 10 x 5 = 5.000  parte dos algarismos, note que na
última casa temos apenas 5 possibilidades, pois queremos um
número par (0 , 2 , 4 , 6 , 8)
Agora é só multiplicar as partes: 17.576 x 5.000 = 87.880.000
Logo, existem 87.880.000 placas onde a parte dos algarismos
formem um número par.
1 - Princípio da Multiplicação
Ex.: Para montar um computador, temos 3 diferentes tipos de
monitores, 4 tipos de teclados, 2 tipos de impressora e 3 tipos de
"CPU".
Para saber o numero de diferentes possibilidades de
computadores que podem ser montados com essas peças,
somente multiplicamos as opções:
3 x 4 x 2 x 3 = 72
Então, têm-se 72 possibilidades de configurações diferentes.
Exercícios
18) Quantos números de três algarismos podem ser formados
utilizando elementos do conjunto {1, 2, 3}
19) Quantos números de três algarismos diferentes (distintos)
podem ser formados utilizando elementos do conjunto
{1, 2, 3}
20) Em uma prova havia 4 itens para que os alunos
respondessem V (verdadeiro) ou F (falso). De quantas
maneiras diferentes um aluno que vai “chutar” todas as
respostas poderá responder esses itens?
21) Um painel luminoso retangular é composto de 5 lâmpadas.
De quantas maneiras diferentes esse painel pode ser
iluminado? (considera-se o painel iluminado se, pelo menos,
uma lâmpada estiver acessa)
19/03/2017
3
2 - Princípio da Adição
 Se A e B são eventos disjuntos, com n1 e n2 resultados possíveis,
respectivamente, então o número total de possibilidades para
o evento A ou B é n1 + n2
Este princípio pode ser usado sempre para contar o número total
de possibilidades em casos disjuntos.
Ex.: Suponha que queremos selecionar uma sobremesa entre três
tortas e quatro bolos. De quantas maneiras isso pode ser feito?
Temos 2 eventos, um com 3 resultados possíveis e outro com 4.
No entanto, não temos uma sequência de dois eventos possíveis,
já que somente uma sobremesa será escolhida. O número de
escolhas possíveis será o número total de possibilidades que
temos: 3 + 4 = 7
2 - Princípio da Adição
Ex.: Um pai deseja presentear seu filho com apenas um presente,
bola ou carrinho. Chegando à loja ele encontra 9 tipos de bolas
diferentes e 10 tipos de carrinho diferentes. Quantas são as
possibilidades de escolha do presente.
Os eventos são disjuntos com n1= 9 e n2= 10 então existem
9 + 10 = 19 possibilidades de escolha
Ex.: Uma pessoa deseja comprar um veículo de uma
concessionária, que tem 23 automóveis e 14 caminhões em
estoque. Quantas escolhas possíveis a pessoa tem?
o consumidor pode escolher um carro ou um caminhão (conjuntos
disjuntos). A escolha de um automóvel tem 23 possibilidades, e a
de caminhão, 14. Pelo princípio da adição, a escolha do veículo
tem 23 + 14 = 37 possibilidades
Exercícios
22) Uma senha de usuário de um sistema computacional pode
ser formada por sequências de uma a três letras maiúsculas,
sendo que repetições são permitidas. Quantas senhas
diferentes podem existir?
23) Quantos números inteiros ímpares existem no intervalo
[10 , 99] com dígitos distintos?
3 - Princípio da Casa de Pombos
O Principio da casa de pombos recebe este nome estranho devido
a seguinte ideia:
 Se mais do que k pombos pousarem em k casas de pombos,
então pelo menos uma casa de pombos ficará com mais de um
pombo.
Se mais do que k itens são distribuídos em k caixas, então pelo
menos uma caixa conterá mais de um item.
Ex.: Quantas pessoas precisam estar no mesmo quarto para se
garantir que pelo menos duas pessoas tem o sobrenome iniciado
pela mesma letra ?
Existem 26 letras no alfabeto. Se tiverem 27 pessoas então
haverá 27 letras iniciais que devem ser distribuídas entre os 26
quartos; por isso, pelo menos um quarto conterá duas pessoas
com o sobrenome iniciado pela mesma letra.
19/03/2017
4
Exercícios
24) Quantas rolagens de dado (um dado de 6 faces) são
necessárias para se ter certeza que um mesmo número vai
cair duas vezes?
25) Existem N pessoas em uma sala. Quantas pessoas são
necessárias para se ter certeza de que 3 nasceram no mesmo
mês?
26) Em uma caixa há 12 bolas de mesmo tamanho: 3 brancas,
4 vermelhas e 5 pretas. Uma pessoa, no escuro, deve retirar n
bolas da caixa e ter a certeza de que, entre elas, existem 3
da mesma cor. Qual o menor valor de n para que se tenha
essa certeza?
FATORIAL DE UM NÚMERO NATURAL
 Dado um número natural n  2, chama-se fatorial de n, ao
número indicado por n! tal que
n! = n . (n-1) . (n-2) . (n-3)...1
ou seja, é o produto de todos os números naturais, de n até 1.
OBS.: 1! = 1 e 0! = 1
Ex.:
6! = 6.5.4.3.2.1 = 720
3! . 4! = (3.2.1).(4.3.2.1) = 6.24 = 144
(3!)² = (3.2.1)² = 6² = 36
(3!)! = (3.2.1)! = 6! = 6.5.4.3.2.1 = 720
6!
2! 3!
=
6.5.4.3!
2.1.3!
=
120
2
= 60
Exercícios
27) Determine:
a) 5!
b) 6! + 4!
c) (3!)² - (3²)!
d)
10!
7!
e)
100!
98!
28) Calcule a soma das raízes da equação (5x-7)! = 1
4 - Arranjo, Permutação e Combinação 
Nas situações envolvendo problemas de contagem algumas
situações os cálculos tendem a se tornar complexos e
trabalhosos.
Para facilitar o desenvolvimento de tais cálculos, alguns
métodos e técnicas foram desenvolvidos ao longo dostempos no intuito de determinar agrupamentos nos
problemas de contagem, veremos alguns destes métodos a
seguir.
19/03/2017
5
4.1 - Arranjo
 É um grupo formado com p elementos escolhidos de uma
coleção com n elementos, sendo p < n de forma que os p
elementos sejam distintos entre si pela ordem ou pela
espécie. Os arranjos podem ser simples ou com repetição.
Ex.: Dado o conjunto B = {2, 4, 6, 8}. Podemos determinar os
agrupamentos de dois elementos do conjunto B, ou seja, são:
{(2,4), (2,6), (2,8), (4,2), (4,6), (4,8), (6,2), (6,4), (6,8), (8,2),
(8,4), (8,6)}
observe que cada arranjo é diferente do outro. Portanto, são
caracterizados pela natureza dos elementos e pela ordem como
pode ser observado abaixo.
Pela natureza dos elementos: (2,4) ≠ (4,8)
Pela ordem dos elementos: (1,2) ≠ (2,1)
4.1 – Arranjo Simples
 É um arranjo que não permite a repetição de qualquer
elemento em cada grupo de p elementos. O número de arranjos
simples é dado pela fórmula:
𝐴𝑛
𝑝 = 𝐴𝑛,𝑝 =
𝑛!
𝑛 − 𝑝 !
Ex.: Seja Z={A,B,C,D}
Os arranjos simples desses 4 elementos tomados 2 a 2 são 12
grupos que não podem ter a repetição de qualquer elemento mas
que podem aparecer na ordem trocada.
n = 4 e p = 2
𝐴4,2={AB,AC,AD,BA,BC,BD,CA,CB,CD,DA,DB,DC}
𝐴4,2 =
4!
4−2 !
=
4!
2!
=
4 .3 .2!
2!
= 12
Exercícios
30) 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?
29) Quais e quantas são as possibilidades de dispor as 5 vogais
A,E,I,O,U em grupos de 2 elementos diferentes?
31) Um número de telefone é formado por 8 algarismos.
Determine quantos números de telefone podemos formar com
algarismos diferentes, que comecem com 2 e terminem com 8?
4.1.1 – Arranjo com Repetição
 É um arranjo em que todos os n elementos podem aparecer
repetidos em cada grupo de p elementos. O número de arranjos
com repetição é dado pela fórmula:
𝐴𝑟(𝑛,𝑝) = 𝑛
𝑝
Ex.: Seja C={A,B,C,D}. Os arranjos com repetição desses 4
elementos tomados 2 a 2 são 16 grupos onde aparecem elementos
repetidos em cada grupo. Todos os agrupamentos estão no
conjunto:
n = 4 e p = 2
Ar={AA,AB,AC,AD,BA,BB,BC,BD,CA,CB,CC,CD,DA,DB,DC,DD}
𝐴𝑟(4,2) = 4
2 = 16
19/03/2017
6
Exercícios
32) Formar números de 2 algarismos usando {1,2,3,4,5}, sem
repetição e com repetição.
33) Qual o total de placas de carro que podem ser construídas
com 4 dígitos?
34) Qual o total de placas de carro que podem ser construídas
com 3 letras do alfabeto brasileiro e 4 dígitos?
35) Quatro amigos dirigem-se a uma pastelaria para comprarem,
cada um, um bolo. Nessa pastelaria existem 7 bolos diferentes à
escolha. De quantas maneiras diferentes pode ser feita a escolha
dos bolos?
4.1.2 – Arranjo condicional
 É um arranjo em que todos os elementos aparecem em cada
grupo de p elementos, mas existe uma condição que deve ser
satisfeita acerca de alguns elementos. O número de arranjos
condicionais é dado pela fórmula:
𝐴𝑐 = 𝐴 𝑛1,𝑝1 . 𝐴 𝑛−𝑛1,𝑝−𝑝1
Ex.: 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}?
n = 7 e p=4
o subconjunto escolhido tem n1=3 elementos e este subconjunto será formado
com p1=2
PABC= {AB,BA,AC,CA,BC,CB} e PDEFG= {DE,DF,DG,ED,EF,EG,FD,FE,FG,GD,GE,GF}
𝐴𝑐 = 𝐴(3,2) . 𝐴(7−3,4−2) = 𝐴(3,2) . 𝐴 4,2 =
3!
3 − 2 !
.
4!
4 − 2 !
=
3!
1!
.
4!
2!
= 3.2.4.3 = 72
Exercícios
36) Com as letras A, B, C, D, E, F e G quantos anagramas de
quatro letras distintas podem ser formados?
Desses, quantos terminam por vogal?
37) Com os algarismos 0,1,2,3,4,5,6,7,8,9, tomados 6 a 6,
quantos números podem ser formados tendo nas duas posições
iniciais algarismos que são números ímpares?
4.2 – Permutação
Quando formamos agrupamentos com n elementos, de forma que
os n elementos sejam distintos entre si pela ordem. As
permutações podem ser simples, com repetição ou circulares.
4.2.1 - Permutação simples
 Podemos considerar a permutação simples como um caso
particular de arranjo, onde os elementos formarão
agrupamentos que se diferenciarão somente pela ordem.
P = n!
Ex.: Seja C={A,B,C}. As permutações simples desses 3 elementos
são 6 agrupamentos que não podem ter a repetição de qualquer
elemento em cada grupo mas podem aparecer na ordem trocada.
Todos os agrupamentos estão no conjunto:
P={ABC,ACB,BAC,BCA,CAB,CBA}
n = 3 => n = 3! = 3.2.1 = 6
19/03/2017
7
Exercícios
38) Quantos anagramas podemos formar a partir da palavra
ORDEM?
39) De quantas maneiras diferentes podemos dispor um
conjunto de 4 objetos distintos?
40) Considere a palavra PARTO.
a) Quantos anagramas podemos formar com essa palavra?
b) Quantos anagramas começam com uma consoante e
terminam com uma vogal?
4.2.2 – 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, damos o
nome de permutação com elementos repetidos.
𝑃𝑛
𝑎,𝑏… =
𝑛!
a! 𝑏!…
Ex.: Quantos anagramas podem ser formados com a palavra
MARAJOARA?
M AAAA RR J O
n = 9 a = 4 b = 2 => a ordem importa e com repetições
𝑃9
4,2 =
9!
4! 2!
=
9.8.7.6.5.4!
4! .2.1
= 7560
Exercícios
41) Quantos anagramas podem ser formados com a palavra
ITALIANA?
42) Quantos anagramas podem ser formados com a palavra
BARREIRA, sendo que deverá começar com a letra B?
43) Calcule quantos anagramas podemos construir com a
palavra CATALANA.
44) Calcule quantos anagramas podemos construir com a
palavra MATEMÁTICA.
4.2.3 – Permutação circular
 Este tipo de permutação ocorre quando temos grupos com n
elementos distintos formando um círculo. O número de
permutações circulares é dado pela fórmula:
𝑃𝑐 = 𝑛 − 1 !
Ex.: De quantos modos distintos as pessoas do conjunto {A,B,C,D}
poderão sentar-se junto a uma mesa circular (pode ser retangular)
para realizar o jantar sem haver repetição das posições?
n = 4
𝑃𝑐 = 4− 1 ! = 3! = 6
19/03/2017
8
Exercícios
45) De quantas maneiras seis crianças podem se organizar
para brincar de roda?
46) De quantas maneiras oito pessoas podem se organizar em
uma roda para fazer uma oração?
47) Pedro e Júlia são 2 crianças de um total de 8 que, de mãos
dadas, brincam de roda. De quantas maneiras elas podem
brincar ficando Ana e Pedro sempre lado a lado?
48) Qual o número de maneiras que uma família de 5 pessoas
podem se sentar em uma mesa com o pai e mãe juntos?
4.3 – Combinações simples 
 É uma combinação em que não ocorre a repetição de
qualquer elemento em cada grupo de p elementos. O
número de combinações ´e dado pela fórmula:
𝐶𝑝
𝑛 = 𝐶𝑛,𝑝=
𝑛
𝑝
=
𝑛!
𝑝! 𝑛 − 𝑝 !
Ex.: Considerando o conjunto {A,B,C,D}, qual o número de
combinações simples com p = 2 ?
𝐶4,2 =
4
2
=
4!
2! 4 − 2 !
=
4!
2! 2!
=
4.3.2!
2.1.2!
=
12
2
= 6
Exercícios
51) Em uma sala de aula existem 12 alunas, onde uma delas
chama-se Carla, e 8 alunos, onde um deles atende pelo nome
de Luiz. Deseja-se formar comissões de 5 alunas e 4 alunos.
Determine o número de comissões, onde simultaneamente
participam Carla e Luiz.
49) Com 12 bolas de cores distintas, posso separá-las de
quantos modos diferentes em saquinhos, se o fizer colocando
4 bolas em cada saco?
50) Um fabricante de sorvetes possui a disposição 7
variedades de frutas tropicais do nordeste brasileiro e
pretende misturá-las duas a duas na fabricação de sorvetes.Quantos serão os tipos de sorvete disponíveis?
4.3.1 – Combinação com repetição
 É uma combinação em que todos os elementos podem
aparecer repetidos em cada grupo até p vezes. O
número de combinações com repetição é dado pela
fórmula:
𝐶𝑛+𝑝−1,𝑝 =
𝑛 + 𝑝 − 1
𝑝
Ex.: Uma sorveteria dispõe de 5 sabores de sorvetes em massa. De
quantas maneiras uma pessoa pode saborear 2 bolas?
n = 5 e p = 2 => a ordem não importa e pode haver repetições
𝐶5+2−1,2 =
5+ 2 − 1
2
=
6
2
=
6!
2! 6 − 2 !
=
6!
2! 4!
=
6.5.4!
2.1.4!
=
6.5
2.1
=
30
2
= 15
19/03/2017
9
Exercícios
52) Podendo escolher entre 5 tipos de queijo e 4 marcas de
vinho, de quantos modos é possível fazer um pedido num
restaurante, com duas qualidades de queijo e 3 garrafas de
vinho?
53) De quantas maneiras, uma oficina pode pintar cinco
automóveis iguais, recebendo cada um, tinta de uma única cor,
se a oficina dispõe apenas de três cores e não quer mistura-las?
54) Uma cantina serve, numa promoção, pratos com 3 porções
de alimentos que podem ser: arroz, feijão, purê, couve ou
omelete. De quantas formas distintas posso montar um prato,
sabendo que o cliente pode escolher qualquer alimento
disponível inclusive mais de uma porção do alimento, desde
que tenha exatamente 3 porções em cada prato?