Princípios básicos de matemática discreta

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
Instituto de Matemática - DMPA
Profa. Virgínia Maria Rodrigues
Matemática Discreta I – 2015/2
Combinatória: Princípios Aditivo e Multiplicativo 
Princípio Multiplicativo (ou Princípio Fundamental da Contagem)
Se um evento A pode ocorrer de m maneiras diferentes e, se, para cada uma dessas m maneiras
possíveis de A ocorrer, um outro evento B pode ocorrer de n maneiras diferentes, então o número de
maneiras de ocorrer o evento A seguido do evento B é m⋅n .
Em geral, se um evento Ai pode ocorrer de mi maneiras diferentes, para i=1,2,… , n , então
esses eventos podem ocorrer, sucessivamente, de m1⋅m2⋅…⋅mn maneiras diferentes. Em linguagem de
teoria de conjuntos, se o conjunto Ai tem cardinalidade mi , para i=1,2,… , n , então o produto
cartesiano A1×A2×⋯×An = {(a1 , a2,… , an)∣a i∈Ai ,i=1,2,… , n } tem cardinalidade m1⋅m2⋅…⋅mn .
Princípio Aditivo:
Se uma tarefa pode ser realizada de n1 formas ou de n2 formas, em que nenhum elemento do
conjunto das n1 formas é igual a algum elemento do conjunto das n2 formas, então há n1+n2
formas de realizar a tarefa. 
Ou seja, se A e B são conjuntos disjuntos (isto é, A∩B=∅) com, respectivamente, m e n
elementos, então A∪B possui m+n elementos. Em geral, se A1, A2,… , An são conjuntos disjuntos
2 a 2, e se Ai possui mi elementos, para i=1,2,… , n , então a união A1∪A2∪…∪An possui
m1+m2+…+mn elementos.
Exemplos:
1. Suponha que existam vagas em 3 turmas de Cálculo II e 2 turmas de Álgebra Linear e que Virgínia
tenha horário livre para se matricular em apenas uma dessas turmas. Quantas são as
possibilidades de matrícula para ela?
2. No exemplo acima, supondo que as turmas não tenham colisão de horários, se Virgínia tiver horário
livre para se matricular em uma turma de Cálculo II e em uma turma de Álgebra Linear, quantas
são as possibilidades de matrícula que ela tem?
3. Com 5 homens e 4 mulheres, de quantos modos se pode escolher um homem e uma mulher?
4. Um marceneiro tem 20 modelos de cadeiras e 5 modelos de mesas. De quantas maneiras
podemos formar um conjunto de 1 mesa com 4 cadeiras iguais?
5. Uma bandeira é formada por 7 listras que devem ser coloridas usando apenas as cores verde, azul
e cinza. Se cada listra deve ter apenas uma cor e não se pode usar cores iguais em listras
adjacentes, de quantas formas se pode colorir a bandeira?
6. Quantos são os gabaritos possíveis de um teste de 10 questões de múltipla escolha, com 5
alternativas por questão?
7. Quantas são as linhas de telefones celulares disponíveis, sabendo que cada número é composto
de 8 dígitos e o primeiro dígito é 9? Quantas destas linhas pertencem a uma empresa cujo prefixo
é 91?
8. De quantas maneiras podemos dar 2 prêmios a uma turma com 10 alunos, de modo que os
prêmios não sejam dados a um mesmo aluno?
9. De quantas maneiras podemos dar 2 prêmios a uma turma com 10 alunos, se é permitido que
ambos sejam dados ao mesmo aluno? 
vrodrig@mat.ufrgs.br 1
10. Os professores indicaram 5 livros diferentes de Cálculo e 7 livros diferentes de Geometria. De
quantas maneiras posso escolher um de cada assunto?
11. Os professores indicaram 5 livros diferentes de Cálculo, 7 livros diferentes de Física e 10 livros
diferentes de Química. De quantas maneiras posso escolher 2 livros com a condição de que eles
não sejam da mesma matéria?
Permutações Simples:
Uma permutação de n objetos distintos é qualquer agrupamento ordenado desses objetos. De modo
que, se denotarmos por Pn o número de permutações simples de n objetos, então 
Pn=n ! .
12. Quantos anagramas podemos formar a partir da palavra ILUSTRE? Quantos deles começam por
consoante?
13. Quantos são os anagramas de 2 letras formados por uma vogal e uma consoante escolhidas
dentre 18 consoantes e 5 vogais?
14. a) Quantos são os anagramas da palavra CAPÍTULO?
b) Em quantos anagramas aparecem as vogais e consoantes intercaladas?
c) Quantos anagramas de CAPÍTULO iniciam com consoante e terminam por vogal?
d) Quantos anagramas de CAPÍTULO começam por C e terminam por O?
15. Quantos são os números de 3 algarismos distintos?
16. Quantos são os números pares de 3 algarismos distintos?
17. Quantos são os números que podemos formar com todos os dígitos 1, 1, 1, 1, 1, 1, 1, 2 e 3?
18. As senhas de uma caixa eletrônica de um determinado banco são maiores do que 100 e menores
do que 1000. Uma pessoa quer escolher sua senha entre os algarismos do número de sua conta
que é 350338430-9. Qual é o número de possibilidades que ela tem de escolher senhas com todos
os algarismos distintos?
19. Quantos são os números inteiros maiores que 64.000 que possuem 5 algarismos, todos distintos e
que não contém os dígitos 3 e 8?
20. Considerando os algarismos 1, 2, 3, 4 e 5, quantos números de 2 algarismos distintos podem ser
formados?
21. Considerando o conjunto {1,2,3, 4,5 }, quantos subconjuntos de 2 elementos podem ser
formados?
OBS: 
Como na formação de subconjuntos a ordem dos elementos não importa, devemos dividir o
resultado obtido com o princípio multiplicativo pelo número de permutações dos elementos de cada
subconjunto, para excluir as repetições.
22. Considerando os algarismos 1, 2, 3, 4 e 5, quantos números de 3 algarismos distintos podem ser
formados?
23. Considerando o conjunto {1,2,3,4,5} , quantos subconjuntos de 3 elementos podem ser
formados?
24. Quantos triângulos podemos formar a partir de 7 pontos tomados em uma circunferência?
25. Quantos são os anagramas da palavra BOTAFOGO?
26. De quantos modos podemos arrumar em fila 5 livros diferentes de álgebra, 3 livros diferentes de
análise e 2 livros de geometria, de modo que livros de uma mesma área permaneçam juntos?
2 
27. De quantos modos podemos dividir 8 objetos diferentes em um grupo de 5 objetos e um de 3
objetos?
28. Quantos subconjuntos possui um conjunto A com n elementos?
29. Qual é o valor de k após a execução do programa abaixo?
 k :=0
for i1:=1 to n1
 k :=k+1
for i2:=1 to n2
 k :=k+1
⋮
for im :=1 to nm
 k :=k+1
30. Qual é o valor de k após a execução do programa abaixo?
 k :=0
for i1:=1 to n1
 for i2:=1 to n2
⋱
 for im :=1 to nm
 k :=k+1
31. Em uma versão da linguagem BASIC, o nome de uma variável é um string de um ou dois
caracteres alfanuméricos, onde um caractere alfanumérico é uma das 26 letras do alfabeto ou um
dos 10 dígitos, sem distinção entre letras maiúsculas e minúsculas. Além disso, o nome de uma
variável deve começar com uma letra e deve ser diferente dos cinco strings de dois caracteres que
são reservados para programação. Quantos nomes diferentes de variáveis existem nessa versão
de BASIC?
32. Quantas funções existem de um conjunto com m elementos em um conjunto com n elementos? 
Quantas delas são injetoras?
33. Quantos são os divisores positivos do número N = 178.200? Quantos desses divisores são pares? 
Quantos são ímpares? Quantos são quadrados perfeitos?
34. De quantas maneiras podemos distribuir 5 objetos diferentes em 2 caixas diferentes?
35. De quantas maneiras podemos distribuir n objetos diferentes em 2 caixas diferentes?
36. De quantas maneiras podemos distribuir 5 objetos iguais em 2 caixas diferentes?
37. De quantas maneiras podemos distribuir n objetos iguais em 2 caixas diferentes?
38. De quantas maneiras podemos distribuir 5 objetos iguais em 2 caixas diferentes, de modo que
nenhuma caixa fique vazia?
39. De quantas maneiras podemos distribuir n objetos iguais em 2 caixas diferentes, de modo que
nenhuma caixa fique vazia?
40. De quantas maneiras podemos distribuir n objetos diferentes em 2 caixas diferentes, de modo que
nenhuma caixa fique vazia?
41. De quantas maneiras podemos distribuir n objetos diferentesem 2 caixas iguais, de modo que
nenhuma caixa fique vazia?
42. De quantas maneiras podemos distribuir n objetos iguais em 2 caixas iguais?
43. De quantas maneiras podemos distribuir n objetos iguais em 2 caixas iguais, de modo que
nenhuma caixa fique vazia?
44. De quantas maneiras podemos distribuir n objetos diferentes em 2 caixas iguais?
3 
Respostas:
1) 5 2) 6 3) 20
4) 100 5) 192 6) 510
7) 107 , 106 8) prêmios distintos: 90, prêmios iguais: 45 
9) prêmios distintos: 100, prêmios iguais: 55 10) 35
11) 155 12) 7 ! , 4⋅6 ! 13) 180
14) a) 8! b) 2⋅4 !⋅4! c) 16⋅6 ! d) 6 !
15) 648 16) 328 17) 72
18) 100 19) 2160 20) 20
21) 10 22) 60 23) 10
24) 35 25)
8 !
3!
26) 8640
27) 56 28) 2n 29) n1+n2+…+nm
30) n1⋅n2⋅…⋅nm 31) 957
32) nm , {n(n−1)⋅…⋅(n−m+1) , m⩽n0 , m>n 33) 120, 90, 30, 12
34) 32 35) 2n 36) 6
37) n+1 38) 4 39) n−1
40) 2n−2 41) 2n−1−1 42) ⌈ n+12 ⌉
43) ⌈ n+12 ⌉−1 44) 2n−1
4