Matematica Discreta

Prévia do material em texto

Matemática
discreta
licenciatura em
matemática
L
IC
E
N
C
IA
T
U
R
A
 E
M
 M
A
T
E
M
Á
T
IC
A
 - E
S
T
R
U
T
U
R
A
S
 A
L
G
É
B
R
IC
A
S
U
A
B
 / IF
C
E
S
E
M
E
S
T
R
E
 6
Ministério da Educação - MEC
Coordenação de Aperfeiçoamento 
de Pessoal de Nível Superior
Universidade Aberta do Brasi l
Instituto Federal de Educação, 
Ciência e Tecnologia do Ceará
MINISTÉRIO DA EDUCAÇÃO
Universidade Aberta do Brasil
Instituto Federal de Educação, Ciência e Tecnologia do Ceará
Diretoria de Educação a Distância
Fortaleza, CE
2012
Licenciatura em Matemática 
Matemática Discreta
Marcos Antônio de Macedo
Créditos
Presidente
Dilma Vana Rousseff
Ministro da Educação
Aloizio Mercadante Oliva
Secretário da SEED
Carlos Eduardo Bielschowsky
Diretor de Educação a Distância
João Carlos Teatini
Reitor do IFCE
Cláudio Ricardo Gomes de Lima
Pró-Reitor de Ensino
Gilmar Lopes Ribeiro
Diretora de EAD/IFCE e Coordenadora 
UAB/IFCE
Cassandra Ribeiro Joye
Vice-Coordenadora UAB 
Cristiane Borges Braga
Coordenadora do Curso de
Tecnologia em Hotelaria
Fabíola Silveira Jorge
Coordenadora do Curso de 
Licenciatura em Matemática
Priscila Rodrigues de Alcântara
Elaboração do conteúdo
Marcos Antônio de Macedo
Colaboradora
Lívia Maria de Lima Santiago
Equipe Pedagógica e Design Instrucional
Ana Claúdia Uchôa Araújo
Andréa Maria Rocha Rodrigues
Carla Anaíle Moreira de Oliveira
Cristiane Borges Braga
Eliana Moreira de Oliveira
Gina Maria Porto de Aguiar Vieira
Glória Monteiro Macedo
Iraci Moraes Schmidlin
Irene Moura Silva
Isabel Cristina Pereira da Costa
Jane Fontes Guedes
Karine Nascimento Portela
Lívia Maria de Lima Santiago
Luciana Andrade Rodrigues
Márcia Roxana da Silva Régis
Maria Irene Silva de Moura
Maria Vanda Silvino da Silva
Marília Maia Moreira
Saskia Natália Brígido Batista
Equipe Arte, Criação e Produção Visual
Benghson da Silveira Dantas
Cícero Felipe da Silva Figueiredo
Elson Felipe Gonçalves Mascarenha
Germano José Barros Pinheiro
Gilvandenys Leite Sales Júnior
José Stelio Sampaio Bastos Neto
Lucas de Brito Arruda
Marco Augusto M. Oliveira Júnior 
Equipe Web
Benghson da Silveira Dantas 
Fabrice Marc Joye
Herculano Gonçalves Santos
Lucas do Amaral Saboya
Samantha Onofre Lóssio 
Tibério Bezerra Soares
Revisão Textual
Aurea Suely Zavam
Nukácia Meyre Araújo de Almeida
Revisão Web
Antônio Carlos Marques Júnior
Débora Liberato Arruda Hissa
Saulo Garcia
Logística
Francisco Roberto Dias de Aguiar
Secretários
Breno Giovanni Silva Araújo
Francisca Venâncio da Silva
Auxiliar
Ana Paula Gomes Correia
Bernardo Matias de Carvalho
Charlene Oliveira da Silveira
Nathália Rodrigues Moreira
Virgínia Ferreira Moreira
Wagner Souto Fernandes
https://creativecommons.org/licenses/by-nc-sa/4.0
Macedo, Marcos Antônio de.
 Matemática Discreta / Marcos Antônio de Macedo; Coordenação 
Cassandra Ribeiro Joye. - Fortaleza: UAB/IFCE, 2012.
122p. : il. ; 27cm.
ISBN 978-85-475-0006-1
1. MATEMÁTICA DISCRETA. 2. ANÁLISE COMBINATÓRIA. 3. 
TEORIA DOS GRAFOS. I. Joye, Cassandra Ribeiro (Coord.). II. Instituto 
Federal de Educação, Ciência e Tecnologia do Ceará – IFCE. 
III. Universidade Aberta do Brasil – UAB. IV. Título.
CDD – 510
M141m
Catalogação na fonte: Islânia Fernandes Araújo (CRB 3 nº 917)
SUMÁRIO
AULA 2
AULA 3
AULA 4
Apresentação 7
Referências 121
Tópico 1
Tópico 2
Tópico 1
Tópico 2
Tópico 1
Tópico 2
Tópico 3
Tópico 1
Tópico 2
Currículo 123
Análise Combinatória I 8
Princípio da Contagem e Arranjos Simples 9
Permutação Simples e Combinação Simples 16
AULA 1
Análise Combinatória II 23
Permutação Circular e Combinatória Completa 24
Permutações Caóticas e os Lemas de Kaplansky 30
Coeficientes Binomiais, Triângulo de Pascal e 
Números de Fibonacci 36
Coeficientes Binomiais Triângulo de Pascal 37
Binômio de Newton 43
Números de Fibonacci 48
Conjuntos e Relações 51
Conjuntos 57
Relações Binárias de A em B 57
6 Matemát ica D isc re ta
AULA 5
AULA 7
AULA 8
Tópico 1 
Tópico 2
Introdução ao Cálculo de Probabilidades 65
Probabilidade Condicional 72
Conceitos de Grafos 97
Definição de isomorfismo e exemplos de grau 
de um vértice, complemento, caminho e circuito 
101
Ciclos Eulerianos e Ciclos Hamiltonianos 112
Árvores 115
Tópico 1
Tópico 2
Tópico 1
Tópico 2
Noções de Probabilidade 64
Grafos 96
Árvores 111
Múltiplos, Divisores e Primos 79AULA 6
Tópico 1
Tópico 2
Múltiplos e Divisores 80
Fatoração em Primos, MDC e MMC 86
7
APRESENTAÇÃO
Caro(a) aluno(a),
Esta disciplina é planejada para proporcionar ao aluno uma base razoável sobre os conceitos 
da Matemática usados na Matemática Discreta. Discutiremos vários resultados e métodos da 
Matemática Discreta nas áreas de combinatória, da teoria dos números, por meio de divisores 
e primos, da probabilidade e teoria dos grafos.
 Nas três primeiras aulas, serão apresentadas as ferramentas da análise combinatória, inclusive 
aquelas não encontradas com muita frequência nos livros didáticos, mas que julgamos de 
grande importância quando se estudam técnicas de agrupamentos. 
Na quarta aula, embora o assunto sobre conjunto tenha sido trabalho de modo sucinto, 
procuramos dar um tratamento um pouco mais formal e com isso acreditamos que estaremos 
fornecendo um conjunto de mecanismos para que o aluno possa manipular de modo 
adequado a linguagem da teoria dos conjuntos.
Procuramos, na aula 5, recordar e introduzir algumas noções de múltiplos divisores e primos, 
enunciando alguns dos seus teoremas mais relevantes com suas respectivas demonstrações. 
As duas últimas aulas são dedicadas a um conceito muito relevante, principalmente na 
ciência da computação, e que fornece suporte a um conjunto de operações relacionadas à 
Matemática Discreta. Trata-se de Grafos, que representa um elemento da Matemática Discreta 
com um grande grau de aplicabilidade em matemática, informática, engenharia da indústria, 
entre outros campos do saber. 
 
APRESENTAÇÃO
8 Matemát ica D isc re ta
AULA 1 Análise Combinatória I
Caro(a) aluno(a),
Nesta primeira aula, estudaremos a Análise Combinatória, que é um conjunto de 
ferramentas que nos permite agrupar e contar os elementos de um conjunto finito 
sem necessariamente enumerá-los.
No tópico 1, será apresentada a técnica de contagem básica encontrada nos livros 
didáticos, que é “o Princípio Fundamental da Contagem”, e apresentaremos os 
tipos de agrupamentos nas suas versões mais simples, que são o arranjo simples, 
combinação simples e permutação simples. No segundo tópico, concluiremos 
nosso estudo sobre o uso dessas ferramentas apresentando o arranjo com 
repetição, combinação completa e a permutação com repetição. No entanto, a 
análise combinatória possui em seu quadro de ferramentas outras técnicas não 
tão frequentes em livros didáticos. Tais técnicas, que julgamos fundamentais na 
resolução de alguns problemas, serão estudadas na aula 2.
Objetivos
• Desenvolver a capacidade de raciocínio lógico e organizado
• Compreender a análise combinatória
• Analisar estruturas e relações discretas
9
Neste tópico, apresentaremos as técnicas de contagem que nos permitirão determinar o número de elementos de conjuntos formados a partir de certas regras, sem que haja a necessidade de 
contar elemento por elemento, o que seria uma atividade no mínimo exaustiva e, 
em alguns casos, impossível. Iniciaremos definindo uma ferramenta bastante eficaz 
nas demonstrações de proposições relacionadas ao conjunto dos números naturais, 
que é o Princípio da Indução Finita.
1.1 PRINCÍPIO DA INDUÇÃO FINITA
O Princípio da Indução é uma ferramenta eficiente quando se pretende 
demonstrar fatos referentes aos números naturais. Dessa forma, vamos iniciar 
nosso estudo conhecendo seu significado e como utilizá-la na demonstração de 
proposições.
Seja N = {1 , 2 , 3 , 4 , 5 , ... , n , ... } o conjunto dos 
números naturais e P(n) uma determinada proposição relativa 
aos números naturais. O Princípio da Indução determina que: 
• Se P(1) for verdadeira, ouseja, se p(n) for verdadeira para o número 1 
(condição inicial) e supondo P(n) ser verdadeira para todo n (hipótese 
de indução), implica P(n + 1) também ser verdadeira. Então a 
propriedade P(n) é verdadeira para todo número natural n.
TÓPICO 1 Princípio da Contagem e Arranjos Simples
ObjetivOs
• Compreender o conceito básico de contagem através do 
Princípio Fundamental da Contagem
• Definir Arranjos Simples
• Conhecer alguns problemas com a aplicação do Princípio 
Fundamental da Contagem
AULA 1 TÓPICO 1
Matemát ica D isc re ta10
Vejamos alguns casos:
ExEmplo 1:
Vamos provar que a soma dos n primeiros números naturais é dada por 
n (n 1)
S(n) 
2
+
= .
Solução:
Temos 
n (n 1)
S(n) 1 2 3 4 . . . (n-1) n 
2
+
= + + + + + + = 
Condição inicial: Observamos de imediato que S(1) se verifica, pois 
1 (1 1)
S(1) 1
2
+
= =
Hipótese de indução: Supondo-se 
k (k 1)
S(k) 
2
+
= ; se S(k 1)+ for 
verdadeiro, então a proposição vale para todos os números reais. 
Dessa forma 
k (k 1)
S(k) 1 2 3 4 . . . k 
2
+
= + + + + + = (*)
Aumentando um termo do lado esquerdo da igualdade (*), temos
 
( )
(k 1) (k 2)
S(k 1) 1 2 3 4 . . . k k 1
2
+ +
+ = + + + + + + + = e, fazendo
(k 1) n+ = , chegamos a
n (n 1)
S(n)
2
+
= .
ExEmplo 2:
Prove que a soma dos n primeiros números ímpares é dada pela expressão 
2S(n) n=
Solução:
Temos 2S(n) 1 3 5 . . . (2n-1) n= + + + + = 
Condição inicial: Observamos que S(1) é imediato.
Hipótese de indução: Supondo-se 2S(k) k= ; se S(k 1)+ for verdadeiro, 
então a proposição vale para todos os números reais. 
Dessa forma 2S(k) 1 3 5 5. . . 2k-1 k= + + + + =
11
Aumentando um termo do lado esquerdo da igualdade acima, 
temos
 
( ) 2S(k 1) 1 3 5 . . . 2k 1 (2k 1)+ = + + + + + = + , que equivale 
a 2S(k 1) 1 3 5 . . . (2k 2 1) (2k 1)+ = + + + + + - = + ou, ainda, 
2S(k 1) 1 3 5 . . . [2(k 1) 1] (2k 1)+ = + + + + + - = + . Fazendo (k 1) n+ = , 
chegamos a 2S(n) 1 3 5 . . . (2n-1) n= + + + + = , o que prova nossa relação.
1.2 PRINCÍPIO FUNDAMENTAL DA CONTAGEM - PFC
Vamos introduzir essa técnica com o seguinte problema:
ExEmplo 3:
Uma mulher dispõe de 3 saias 1 2 3(s , s , s ) e 4 blusas 1 2 3 4(b , b , b ,b ) . De 
quantos modos é possível vesti-la com uma saia e uma blusa?
Solução:
É fácil ver que há 4 modos de vesti-la nos quais a saia é s1 , outros 4 nos 
quais a saia é s2 e outros 4 nos quais a saia é S3. O número de modos é, portanto, 
4 4 4 3 4 12+ + = ´ = .
O exemplo acima ilustra o “Princípio Fundamental da Contagem”, que diz:
Se uma ação é composta por várias etapas dependentes uma das outras, o número 
de possibilidades possível de realizar essa ação é o produto de possibilidades de cada etapa.
Assim, para o problema anterior, a ação “vestir-se com uma saia e uma blusa” 
é composta por duas etapas:
1ª etapa: vestir uma blusa (três possibilidades)
2ª etapa: vestir uma saia (quatro possibilidades)
Assim, há 3x4=12 modos de vesti-la. Veja abaixo a descrição de todos os modos.
1 1(b , s ), 1 2(b , s ), 1 3(b , s ), 2 1(b , s ), 2 3(b , s ), 3 2(b , s ), 3 3(b , s ), 4 1(b , s ),
4 2(b , s ), 4 3(b , s ).
ExEmplo 4:
Quantas centenas podem ser formadas com os algarismos 0, 1, 2, 3, 4, 5 e 6?
Solução:
A ação de formar uma centena é composta por três etapas:
1ª etapa: colocar o algarismo das centenas (entre os sete algarismos devemos 
escolher um dos seis para compor o algarismo das centenas, já que o número não 
pode iniciar com “zero”.
AULA 1 TÓPICO 1
Matemát ica D isc re ta12
 
6 7 7
Assim, temos 6 possibilidades para o primeiro número, 7 possibilidades para 
o algarismo das dezenas e 7 modos de escolher o algarismo das unidades. Pelo 
Princípio da Contagem, temos:
6.7.7 = 294 centenas.
ExEmplo 5:
Quantas centenas com algarismos distintos podem ser formadas com os 
algarismos 0, 1, 2, 3, 4, 5 e 6?
Solução:
A ação de formar uma centena é composta por três etapas:
1ª etapa: colocar o algarismo das centenas (entre os sete algarismos devemos 
escolher um dos seis para compor o algarismo das centenas, já que o número não 
pode iniciar com “zero”
 
6 6 5
Assim, temos 6 possibilidades para o primeiro número, 6 possibilidades para 
o algarismo das dezenas (não podemos repetir elementos) e 5 modos de escolher 
o algarismo das unidades já que, dos sete números já foram escolhidos dois . Pelo 
Princípio da Contagem, temos:
6.6.5 = 130 centenas.
1.3 ARRANJOS SIMPLES
Os Arranjos Simples são agrupamentos 
sem repetições em que um grupo se torna 
diferente do outro pela ordem ou pela natureza 
dos elementos componentes. 
Assim, cada centena (agrupamento) do 
exemplo 5 representa um arranjo simples, pois, 
embora apresentem os mesmos algarismos, as 
centenas 235 e 352 são diferentes e com todos 
os algarismos distintos. Já no exemplo 4, cada 
v o c ê s a b i a?
A Combinatória surgiu da necessidade que os 
homens tiveram em calcular maneiras seguras 
de ganharem em certos jogos de azar, tais como 
baralho, dados e moedas. O grande precursor da 
combinatória foi Arquimedes (século III a.C).
13
centena (grupo) não constitui um arranjo simples, pois apresenta algarismos 
repetidos, como é o caso da centena 444 ou 332. Esse tipo de agrupamento será 
estudado no próximo tópico.
ExEmplo 6:
Quantos arranjos simples, a partir de n 
elementos, são possíveis formar com p elementos 
distintos? 
Solução:
Devemos a partir de n elementos, formar 
grupos com p elementos distintos, com p n.£ 
Pelo Princípio Fundamental da Contagem 
(PFC), temos: 
n.(n 1).(n 2).(n 3) . . . [n-(p 1)]- - - + (**)
multiplicando o numerador e o denominador da expressão (**) por ( )!n p- temos: 
n.(n 1).(n 2).(n 3) . . . [n-(p 1)].(n-p)! n !
(n p)! (n p)!
- - - +
=
- -
Assim n,p
n!
A
(n p)!
=
-
 em que n,pA se lê: 
“Arranjo de n elementos tomados de p a p”
 ExErcícioS rESolvidoS
1. Quantos são os gabaritos possíveis 
de um teste de 8 questões de 
múltipla-escolha com quatro 
alternativas por questão?
rESolução:
Existem 4 possibilidades de escolha para a primeira questão; a segunda, 
quatro possibilidades, etc. Assim, pelo PFC, temos 4.4.4. . . .4=48.
2. Vamos determinar a quantidade de números com quatro dígitos com 
as seguintes características:
a) São maiores que 3600 e têm todos os dígitos distintos.
b) São maiores que 3600 e não têm os dígitos 4, 5 e 8.
AULA 1 TÓPICO 1
at e n ç ã o !
Para resolvermos problemas de arranjos simples 
tanto podemos usar a técnica de multiplicar entre 
si os números de possibilidades das etapas (como 
vimos nos exemplos 4 e 5) como podemos usar 
a fórmula n,p
n!
A
(n p)!
=
-
, muito embora na 
maioria das situações seja aconselhável usar o 
primeiro caso.
g u a r d e b e m i s s o !
A técnica para contar agrupamentos em que 
os grupos diferem pela ordem dos elementos é 
chamada “Princípio Fundamental da Contagem”; 
por sua vez, cada grupo recebe o nome de arranjo 
simples.
Matemát ica D isc re ta14
rESolução:
a) Vamos contar os números separadamente, da seguinte forma: 
Se o número começar com 3, 4 ou 5, há 4 modos de selecionar o segundo; 8, o 
terceiro; e 7, o quarto. Há, portanto 3.4.8.7 672= números começados por 3, 4 ou 
5. Se o número começar com 6, 7, 8 ou 9, há 3 modos de selecionar o segundo; 8, o 
terceiro; e 7, o quarto. Há, portanto 4.3.8.7 672= números começados por 6, 7, 8 
ou 9. Assim temos 672 672 1344+ = .
Observe que o problema poderia ter sido resolvido usando a fórmula n,p
n!
A
(n p)!
=
-
a . Se o número começar com 3, 4 ou 5, há 4 modos de selecionar o segundo; 8, o terceiro; 
e 7, o quarto. Há, portanto, 3,1 4,1 8,1 7,1A . A . A . A ou 
3! 4! 8! 7!
 . . . 
(3-1)! (4-1)! (8-1)! (7-1)!
 
que corresponde a 672 números começados por 3, 4 ou 5. Se o número começar com 6, 
7, 8 ou 9, há 3 modos de selecionar o segundo; 8, o terceiro; e 7, o quarto.Há, portanto, 
4,1 3,1 8,1 7,1A . A . A . A ou 
4! 3! 8! 7!
 . . . 
(4-1)! (3-1)! (8-1)! (7-1)!
, o que corresponde a 672. 
Assim 672+672=1344.
 
b) Para o primeiro algarismo, temos 4 possibilidades, 3 para o segundo, 
7 para o terceiro e 7 para o quarto número. Há, portanto, 4.3.7.7=588. 
Porém, se o segundo algarismo for 6, os dois últimos não podem ser zero. Dessa 
forma o número 3600 foi contado indevidamente. A resposta é 588-1=587.
3. Sacam-se sucessivamente e sem reposição três cartas de um baralho de 
52 cartas. Quantas são as extrações possíveis nas quais a primeira carta 
é de paus, a segunda carta é 2 e a terceira não é 8.
rESolução:
Vamos dividir as extrações em três etapas:
i) a primeira carta é um 2 de paus.Neste caso há 1 modo de selecionar a 
primeira carta, 3 modos de selecionar a segunda carta (já que temos apenas quatro 
2 e a de paus já foi escolhida) e 46 modos de selecionar a terceira carta.
ii) a primeira carta é um 8 de paus. Neste caso há um modo de escolher 
a primeira carta, 4 maneiras de escolher a segunda e 47 maneiras de escolher a 
terceira carta.
iii) a primeira carta é de paus (com exceção do 2 de paus e 8 de paus que já 
foram escolhidos). Neste caso há 11 maneiras de escolher a primeira carta, 4 modos 
de escolher a segunda carta e 46 maneiras de escolher a terceira carta.
15
Assim, temos: 1.3.46 1.4.47 11.4.26 2350+ + = .
4. Qual a soma dos divisores inteiros positivos de 3600?
rESolução:
Decompondo 3600 em fatores primos, chegamos a 4 2 23600 2 . 3 . 5= . 
Os divisores inteiros e positivos de 3600 são números do tipo m n z2 . 3 . 5 , com 
m {0, 1, 2, 3, 4}, Î n {0, 1, 2}, Î z {0, 1, 2}.Î Assim queremos encontrar 
m n z(2 . 3 . 5 ). S =å Para z 0, z 1 e z 2 = = = temos:
m n 0 m n 1 m n 2(2 . 3 . 5 ) (2 . 3 . 5 ) (2 . 3 . 5 )S = + +å å å = 
m n m n m n(2 . 3 ) 5 (2 . 3 ) 25 (2 . 3 )+ +å å å
 
= m n31. (2 . 3 ) å
Para n 0, n 1 e z 2 = = = temos:
m 0 m 1 m 2S 31. (2 . 3 ) (2 . 3 ) (2 . 3 ) é ù= + +ê úë ûå å å = 
m m m31.( 2 3 2 9 2 )+ +å å å ou ( )m m mS 31.13 2 2 2= + +å å å
= ( )1 2 3 4403 . 1 2 2 2 2+ + + + = 403.31 S 12.493Þ = . Se quiséssemos 
determinar apenas o número de divisores, teríamos 5.3.3=45, pois m pode ser 
selecionado de 5 modos, n de 3 modos e z de 3 modos.
Chegamos ao final do tópico 1. Pudemos conhecer a principal ferramenta da 
análise combinatória que é o Princípio Fundamental da Contagem e iniciarmos o estudo 
sobre os tipos de agrupamentos. No próximo tópico, introduziremos mais dois tipos de 
agrupamentos que são denominados por combinação simples e permutação simples.
AULA 1 TÓPICO 1
16 Matemát ica D isc re ta
TÓPICO 2 Permutação Simples e Combinação Simples
ObjetivOs
• Conhecer duas ferramentas básicas da combinatória que 
são: permutação simples e combinação simples
• Propiciar a manipulação do Princípio Fundamental da 
Contagem no cálculo das permutações simples e combi-
nações simples
Neste tópico apresentaremos dois tipos de agrupamentos: a permutação simples e a combinação simples, cujos problemas envolvendo esses dois tipos de agrupamentos podem ser 
resolvidos utilizando-se o Princípio Fundamental da Contagem (PFC). Você, aluno, 
deve ter em mente que usar o PFC para determinar número de agrupamentos com 
elementos distintos é equivalente a usar a fórmula 
n!
.
(n p)!-
2.1 PERMUTAÇÃO SIMPLES
Para introduzir o tema acima, vamos considerar o seguinte problema: 
Quantas centenas são possíveis formar com os algarismos 1, 2 e 3? Observe que 
cada centena é uma forma de ordenar os números 1, 2 e 3. Dessa maneira, para o 
primeiro algarismo, temos 3 modos de escolha, 2 para o algarismo das dezenas e 1 
modo de escolha para o algarismo das unidades. Pelo PFC, a resposta é 3.2.1=3!=6
Seguindo o mesmo raciocínio, é fácil verificar que existem n! formas de 
ordenar o conjunto 1 2 3 n(a , a , a , . . . ,a ) , pois existem n modos de escolher o objeto 
que ocupara a primeira posição, n-2 modos de escolher o que ocupara o segundo 
lugar, . . . , 1 modo de escolher o objeto que ocupará o último lugar. Portanto temos 
n (n-1) (n-2). . . 2.1 n!= .
• Cada ordenação dos n objetos distintos é chamada permutação simples 
dos n objetos e é representada por nP n !=
17
• Cada permutação simples de n objetos distintos nada mais é do que 
um arranjo simples em que n p ,= ou seja, n , p nn p A P= Þ = . 
Assim, n n , n
n!
P A n!
(n n)!
= = =
-
 a. 
oS rESolvidoS
1. Quantos são os anagramas da palavra DISCRETA:
a. que começam por consoantes e terminam por vogal?
b. que têm as letras I, C, T juntas nessa ordem?
c. que têm as letras I, C, T juntas em qualquer ordem?
d. que têm a letra S em 2º lugar e a letra D em 3º lugar?
e. que têm a letra T em 2º lugar ou a letra R em 3º lugar?
Solução:
a) Há 5 modos de escolher a consoante que será a primeira letra do anagrama 
e 3 modos de escolher a última letra do anagrama. Em seguida, há 6! modos 
de organizar as demais letras entre a primeira e a última. Assim, pelo PFC 
temos: 5.3.6!=10800.
b) Vamos considerar ICT uma única letra. Assim, temos: 6!=720.
c) Considerando ICT uma única letra, temos 6!. Em seguida escolhemos a 
ordem em que as letras I, C e T aparecerão, 3!. Dessa forma, pelo PFC a 
resposta é 3!.6!=6.720=4320.
d) Temos 1 modo de escolher a 2ª letra e 1 modo de escolher a 3ª letra do 
anagrama. Depois há 6! modos de organizar o restante das letras. Pelo PFC, 
6!.1.1=720.
e) Vamos considerar dois conjuntos A e B. A é o conjunto dos anagramas que 
têm a letra T na segunda posição e B é o conjunto dos anagramas que têm R 
na terceira posição. Queremos determinar o número de anagramas que têm T 
na segunda posição ou R na terceira posição, portanto queremos determinar 
n(A B).È
n(A)=7!, n(B)=7! e n(A B) 6!Ç = 
Assim, usando a fórmula 
n(A B) n(A) n(B)-n(A B)È = + Ç , chegamos a:
n(A B) 7! 7! 6! 6!(7 7 1) 9360È = + - = + - = .
2. Permutam-se de todas as maneiras possíveis os algarismos 1, 2, 3, 5 e 8 
e escrevem-se os números, dessa forma formados, em ordem crescente. 
Pergunta-se:
AULA 1 TÓPICO 2AULA 1 TÓPICO 2
Matemát ica D isc re ta18
a. qual lugar ocupa o número 38512?
b. qual número ocupa o 61º lugar?
c. qual o 76º algarismo escrito?
d. qual a soma dos números formados?
Solução:
a) Vamos contar quantos números antecedem o 385129. Começados por 1 
temos 4!=24 começados por 2 temos 4!=24 começados por 31 temos 3!=6 
começados por 32 temos 3!=6 começados por 35 temos 3!=6 começados por 
381 temos 2!=2 começados por 382 temos 2!=2 
O maior número formado começado por 382 é o número 38251, que, por sua 
vez, ocupa a 70ª posição, já que 2.24+3.6+2.2=70. Assim, 38512 é o 71º lugar.
b) Há 4!=24 números começados por 1, 4!=24 números começados por 2, 
3!=6 números começados por 31, 3!=6 números começados por 32. Até aqui 
temos 2.4!+2.3!=60. O 61º número é 35128. 
c) Considerando que cada número tem 5 algarismos e 76, quando dividido por 
5, dá 15 e deixa resto 1, podemos concluir que 15.5=75 algarismos formam 
exatamente 15 números e o 76º algarismo é o primeiro algarismo do 16º número. 
Para se determinar o 16º número, observamos que: 
3!=6 começam com 12, 3!=6 começam com 13, 2!=2 começam com152 e 2!=2 
começam com 153. Logo, o 16º número é 15382 e a resposta é 1.
d) Nas casas das unidades desses números aparecem apenas os algarismos 
1, 2, 3, 5 e 8. Cada um deles 4!=24 vezes. Assim, a soma das unidades é 
24(1 2 3 5 8) 456.+ + + + = A soma das dezenas é feita de forma semelhante, 
ou seja, a soma das dezenas é 456 dezenas que dá 4560. Seguindo esse 
raciocínio, a soma das centenas é 45600; a soma das unidades de milhar é 
456000 e, para finalizar, a soma das dezenas de milhar é igual a 4560000. 
Assim, temos 456 4.560 45.600 456.000 4.560.000 5.066.616+ + + + = .
3. Quantassão as permutações dos números (1, 2, 3, . . . , 8) nas quais o 
2 está à direita do 1 e à esquerda do 6?
Solução:
Os 8, 2A
 
nos dão todas as formas possíveis de organizar 1, 2 e 6 nas oito 
posições existentes. Considerando que, para cada modo de arrumar 1, 2 e 6 em três 
determinadas posições, apenas uma está na ordem desejada, dividimos 8, 3A por 
3!. Por outro lado, para cada forma de organizar 1, 2 e 6 na ordem desejada, temos 
19
permutação das cinco restantes. Assim, temos:
 
8, 3A 8! 8!. 5 ! . 5 ! 6720
3! 5! 3! 3!
= = =
4. De quantos modos podemos dividir 12 pessoas em 3 grupos de 4 pessoas 
cada?
Solução:
A divisão pode se feita colocando as 12 pessoas em fila e dividindo-as de 
modo que um dos grupos seja formado pelas 4 primeiras pessoas, outro formado 
pelas 4 últimas e o terceiro grupo formado pelas 4 pessoas restantes. 
Há 12! modos de colocar as pessoas em fila, porém, neste caso, algumas 
divisões e alguns grupos foram contados indevidamente: 
Considere a divisão abcd/efgh/ijlm . Ela é idêntica a abcd/ijlm/efgh que 
por sua vez é idêntica a ijlm/abcd/efgh (as divisões formadas são as mesmas). 
Observe que, para cada divisão, temos 3! divisões semelhantes. Da mesma forma, 
o grupo o abcd , por exemplo, possui 4! grupos semelhantes. Assim, para cada 
grupo, temos 4! grupos idênticos. Em suma, na contagem 12!, cada divisão foi 
contada 3! vezes e cada grupo contado 4! vezes. A resposta é 
12!
5.775
4! 4! 4! 3!
= 
A seguir, introduziremos o conceito de um tipo de agrupamento cuja técnica 
de resolução nos permitirá resolver problemas com este de maneira simples: a 
combinação simples.
2.2 COMBINAÇÃO SIMPLES 
Para introduzir a ideia de combinação 
simples, vamos considerar o seguinte problema: 
Quantos subconjuntos com 3 elementos possui o 
conjunto {a,e,i,o,u}?
rESolução:
Considerando que queremos formar 
grupos com 3 elementos a partir de 5 elementos, 
temos 5 modos de colocar a primeira letra nesse 
conjunto, depois 4 modos de colocar a segunda letra e 3 três modos de colocar a 
terceira letra. Assim, pelo PFC, temos 5.4.3=60. Porém alguns subconjuntos foram 
contados mais de uma vez, já que o PFC calcula o número de arranjo simples e os 
AULA 1 TÓPICO 2
v o c ê s a b i a?
Palíndromos podem ser palavras ou números 
que são iguais quando lidos de frente para trás e 
de trás para frente. Alguns exercícios de análise 
combinatória envolvem palíndromos. Vejam 
alguns exemplos: ANA, MUSSUM, RADAR, ZE 
DE LIMA RUA LAURA MIL E DEZ, ROMA ME 
TEM AMOR.
Matemát ica D isc re ta20
arranjos diferem um do outro pela ordem de seus elementos. Na nossa contagem os 
grupos {a,e,i} e {e,i,a}foram contados como se fossem distintos. Cada grupo com 3 
elementos gera 3! grupos idênticos. A resposta é 
5.4.3
10
3!
= . Os subconjuntos são: 
{a,e,i}, {a,e,o}, {a,e,o}, {a,i,o}, {a,i,u}, {a,o,u}, {e,i,o}, {e,i,u}, {e,o,u},
{i,o,u}.
Definição: Considere um conjunto com n elementos 1 2 3 nA {a ,a , a , . . . , a }= . 
Chama-se combinação simples dos n elementos tomados de p a p e se indica por
n pC , qualquer subconjunto de A com p elementos.
Vamos determinar o número de subconjuntos com p elementos do conjunto 
com n elementos. A escolha do 1º elemento pode ser feita de n modos; a do 2º, 
de (n 1)- modos, e assim em diante. A escolha do p-ésimo elemento pode ser 
feita de [(n p)-1]- modos. Ao usar o PFC, estamos calculando a quantidade 
de arranjos em que os grupos diferem pela ordem. Dessa forma, para cada 
subconjunto com p elementos, temos p! subconjuntos idênticos. Então basta 
dividir nosso produto por n!, ou seja, n p
n.(n 1).(n 2).....[(n p) 1]
C , 
p!
- - - -
= , mas 
n!
n.(n 1).(n 2).....[(n p) 1]
(n-p)!
- - - - = , então n p
n!
C , 
p!(n-p)!
=
ExErcícioS rESolvidoS
1. Uma comissão formada por 4 homens e 3 mulheres deve ser escolhida 
em um grupo de 7 homens e 6 mulheres. Quantas comissões podem ser 
formadas?
rESolução:
Devemos selecionar 4 homens, o que pode ser feito de 7 4C , modos, 
e 3 mulheres, o que pode ser feito de 6 3C , maneiras. Pelo PFC temos: 
7 4 6 3
7! 6!
C , . C , . 700
4! 3! 3! 3!
= =
 
2. Quantas diagonais possui um dodecaedro regular?
21
rESolução:
O dodecaedro regular é um poliedro formado por 12 pentáCada linha (aresta, 
diagonal da face ou diagonal do poliedro) representa uma combinação do número 
de vértices tomados de dois a dois. Um dodecaedro possui 12 faces pentagonais, 
V vértices e A arestas. 
Considerando as 12 faces, cada uma com 5 arestas, chegaríamos a 12.5=60 
arestas, resultado falso, pois cada aresta é comum a duas faces, logo o número de 
faces é 60/2=30.
Por outro lado, cada face tem 
n(n 3) 5(5 3)
5
2 2
- -
= = diagonais, portanto 
temos um total 5.12=60 diagonais da face. Vamos usar a relação de Euler para 
determinar o número de vértices: V-A F 2 V-30 12 2 V 20 + = Þ + = Þ = .
O número de diagonais do poliedro é, portanto,
 
20, 2
20!
C -(x y) (30 60) 100
2! 18!
+ = - + = , em que 60´= é o número de diagonais 
de todas as faces e 30y = é o número de arestas do poliedro.
3. Quantos são os números naturais de 6 dígitos nos quais o dígito 3 e o 
9 figuram exatamente 2 vezes cada?
Solução: 
Inicialmente vamos contar aqueles números que começam com zero e depois 
descontá-los do total. 
A primeira casa deve ser ocupada pelo zero; há 1 modo de fazer isso. Há 5 2C ,
modos de escolher as casas que serão ocupadas pelo algarismo 3; depois disso há 
3, 2C modos de escolher as casas que serão ocupadas pelo algarismo 9. Finalmente a 
8 maneiras de preencher a casa restante. Assim, 5 2 3 21 . C , . C , . 8 240= números 
nessas condições começam com zero. Agora vamos determinar todos os números 
com a condição exigida, inclusive os que começam com zero. Há 6 2C , modos de 
escolher as casas que serão ocupadas pelo algarismo 3. Em seguida, há 4 2C , modos 
de escolher as casas que serão ocupadas pelo algarismo 9. Finalmente, pelo PFC, 
há 8.8=64 modos de escolher as duas casas restantes que serão preenchidas pelos 
8 algarismos restantes. Assim 6 2 4 2C , . C , . 64 5760=
 
começam com zero ou não. 
A resposta é 5760-240=5520.
AULA 1 TÓPICO 2AULA 1 TÓPICO 2
Matemát ica D isc re ta22
4. Vamos resolver o problema anterior considerando 4p = , de modo mais 
simples usando a fórmula n,p
n!
C .
p!(n p)!
=
-
 O enunciado do problema é 
o seguinte: De quantos modos podemos dividir 12 pessoas em 3 grupos 
de 4 pessoas cada?
rESolução:
Há 12, 4C modos de formar o 1º grupo; 8, 4C modos de formar o 2º grupo e 
4, 4C modos de formar o 3º grupo. Pelo PFC, temos 12, 4 8, 4 4, 4C . C . C , mas, ao 
tomarmos três grupos e mudarmos a ordem, a divisão permanece a mesma, assim 
devemos dividir o produto por 3!.
A resposta é 12, 4 8, 4 4, 4
C . C . C
5.775
3!
=
Nesta aula, estudamos a aplicação do Princípio Fundamental da Contagem 
(PFC) nos modelos mais simples de agrupamentos. Na próxima aula, introduziremos 
outros tipos de agrupamentos mais complexos e adequaremos o PFC para a resolução 
de problemas que envolvam esses agrupamentos.
23
Olá, aluno(a)!
Nesta aula, daremos continuação ao estudo da análise combinatória, apresentando 
outras ferramentas diferentes daquelas estudadas na aula 1, mas de muita 
importância quando se pretende ter um conhecimento mais específico e completo 
da análise combinatória.
Objetivo
• Ampliar os conhecimentos básicos de análise combinatória
AULA 2 Análise Combinatória II
AULA 2
24 Matemát ica D isc re ta
TÓPICO 1 Permutação Circular e Combinação Completa
ObjetivOs
• Estender o conceito de permutação e de combina-
ção
• Compreender a forma mais específica e completa 
desses elementos
Na primeira aula estudamosa combinação simples e a permutação simples que, como vimos, são agrupamentos nos quais não há elementos repetidos. Neste tópico estudaremos os mesmos tipos 
de agrupamentos (combinação e permutação), porém com a possibilidade de ocorrer 
elementos repetidos.
1.1 PERMUTAÇÃO CIRCULAR
Vamos iniciar este tópico, introduzindo o conceito de permutação circular 
com o seguinte problema: de quantos modos se podem colocar n objetos distintos 
em n lugares situados à mesma distância um do outro em torno de um círculo, 
considerando obviamente equivalentes as disposições que possam coincidir pela 
rotação do círculo. Por exemplo, se tivermos os objetos A, B, C, D e E, nesta ordem, 
em torno de um círculo, as posições A, B, C, D e E são equivalentes às posições 
B, C, D, E e A; C, D, E, A e B, etc. Iremos calcular a quantidade de permutações 
circulares de n objetos distintos que representaremos por (PC)n. Assim, se n 3= 
temos 3P 3! 6= = maneiras de colocar 3 objetos distintos em 3 lugares, como mostra 
a figura 1.
25
Podemos observar que as três primeiras disposições podem coincidir entre si por 
rotação e os mesmo acontece com as três últimas disposições, de maneira que (PC)3=2.
Note que nas permutações simples, os lugares que os objetos ocupam fazem 
diferença, enquanto que nas permutações circulares o que interessa na verdade 
é apenas a posição relativa entre os objetos. Podemos ver que nas três primeiras 
posições temos a sequência no sentido anti-horário: A, B e C, ao passo que as três 
últimas posições obedecem a sequência A, C, B no sentido anti-horário.
Se não levássemos em conta a equivalência entre as posições que possam 
coincidir por rotação, teríamos 3! disposições. Considerando a equivalência, cada 
permutação circular dá origem a 3 disposições. Assim, 
3
3.(3 1)!3!
(PC) (3 1)! 2!=2 1=2
3 3
-
= = = - = ´
Podemos analisar o problema também de outra forma: considerando que o 
que importa realmente é a posição relativa entre os elementos, usando o PFC, temos 
1 modo de colocar o primeiro objeto; 1 modo para colocar o segundo objeto e dois 
modos para colocar o terceiro objeto, ou seja, o terceiro objeto pode ser colocado 
imediatamente depois do primeiro ou imediatamente depois do segundo (antes 
do primeiro). Assim, usando o princípio da contagem, temos 1.1.2 2= ou temos 
3(PC) 2= modos de dispor os três objetos em círculo.
De maneira geral, considerando n objetos, temos 1 modo de colocar 
o primeiro; há 1 modo de colocar o segundo objeto; há 2 modos de colocar o 
terceiro objeto; há 3 modos de colocar o quarto objeto. Por fim, há (n-1) modos de 
colocar o enésimo objeto. Dessa forma, pelo Princípio Fundamental da contagem 
n(PC) 1.1.2.3.4...(n 1)= - que equivale a:
n(PC) (n 1)!= - .
AULA 2 TÓPICO 1
Figura 1: Permutação circular dos elementos A, B e C
Matemát ica D isc re ta26
ExEmplo1: 
De quantos modos podemos dispor 5 
pessoas em torno de uma mesa circular?
Solução:
Considerando que o que de fato importa 
é a posição relativa das pessoas entre si, temos 
5(PC) (5 1)! 4! 24= - = = . 
ExEmplo 2: 
De quantos modos 5 homens e 5 mulheres 
podem sentar-se numa mesa circular, de modo 
que pessoas do mesmo sexo não fiquem juntas?
Solução: 
Há 5(PC) (5 1)! 4! 24= - = = modos de formar uma roda com mulheres. Depois 
disso, os 5 homens devem ser postos nos 5 lugares entre as mulheres, o que pode 
ser feito de 5! modos. Assim, temos 4!. 5! 24 . 120 2.880.= = 
ExEmplo 3:
De quantos modos n casais podem formar uma roda de ciranda de modo que 
cada homem permaneça ao lado de sua mulher?
Solução:
n(PC) (n 1)!= - m de formar uma roda com as n mulheres. Em seguida, para 
cada um dos n maridos há dois modos de entrar na roda: a direita ou a esquerda de 
sua mulher. Assim, a resposta é n(n 1)! 2 .- 
1.2 COMBINAÇÃO COMPLETA
Vamos introduzir o conceito de Combinação completa, analisando o seguinte 
problema: de quantos modos é possível comprar 5 sorvetes numa sorveteria que 
ofereça 8 sabores? 
Cada modo de compra dos 5 sorvetes representa um agrupamento que 
chamamos de combinação com repetição ou combinação completa de classe 5, de 
8 objetos, representada por 8, 5CR . Há duas formas de interpretar este problema:
• A primeira forma é imaginar a solução como o número de modos de 
v o c ê s a b i a?
A necessidade de calcular o número de 
possibilidades existentes nos jogos gerou o estudo 
dos métodos de contagem. Grandes matemáticos 
se ocuparam com o assunto: o italiano Niccollo 
Fontana (1500-1557), conhecido como Tartaglia, e 
os franceses Pierre de Fermat (1601-1665) e Blaise 
Pascal (1623-1662).
27
escolher 5 objetos entre os 8 objetos distintos, podendo escolher o 
mesmo objeto mais de uma vez ou não escolher, obviamente, um 
certo objeto. Dessa forma, a diferença entre a combinação simples 
de n elementos tomados de p a p ( n,pC ), estudada na aula anterior, 
e a combinação completa de classe p de n objetos ( n,pCR ) reside no 
fato de que, no primeiro caso, os elementos p devem ser distintos, 
ao passo que no segundo caso os elementos p podem ser distintos ou 
não. Assim, por exemplo, se considerarmos os elementos a, b, c e d, 
as combinações completas de classe 3 são
aaa aab bba cca dda abc bbb aac bbc ddb ccb abd
ccc aad bbd ccd acd ddc ddd bcd,
ou seja, 4, 3CR 20.=
• Outra forma de interpretar o problema do sorvete é a seguinte:
Para efetuar a compra devemos escolher valores para as variáveis
1 2 3 4 8x , x , x , x , . . ., x , em que 1x é a quantidade que vamos comprar de sorvetes 
do primeiro sabor, 2x é a quantidade de sorvetes do segundo sabor e assim em diante. 
Considerando que as variáveis 1 2 3 4 8x , x , x , x , . . ., x representam quantidades 
de sorvetes, então todas elas devem ser valores inteiros e não negativos (dessa 
forma estamos incluindo o zero). 
Assim, comprar 5 sorvetes em uma sorveteria que oferece 8 sabores é tomar uma 
solução em inteiros e não negativos da equação 1 2 3 4 8x x x x . . . x 5+ + + + + =
Vamos à resolução da equação.
Para tornar mais simples o raciocínio, vamos considerar as figuras 2, 3 e 4 abaixo.
Nas figuras 2, 3 e 4 estão representadas soluções da equação
1 2 3 4 8x x x x . . . x 5+ + + + + = , em que cada bola representa uma unidade 
no valor da incógnita, e cada traço é usado para separar duas incógnitas. Assim, 
por exemplo, na figura 2, 1 2 7x x x 1,= = = enquanto 3 4 6 8x x x x 0= = = = 
e 5x 2.= Na figura 3, 1 6 8x x x 1,= = = 2 3 4 7x x x x 0= = = = e 5x 2.= Na 
figura 4 temos outra solução da equação 1 2 3 4 8x x x x . . . x 5+ + + + + = em 
que 1 4 6 7 8x x x x x 0,= = = = = 2 5x x 1= = e 3x 3.=
AULA 2 TÓPICO 1
Matemát ica D isc re ta28
Figura 2 – representação de uma solução da equação 1 2 3 4 8x x x x . . . x 5+ + + + + =
Figura 3- representação de uma solução da equação 1 2 3 4 8x x x x . . . x 5+ + + + + = 
Figura 4- representação de uma solução da equação 1 2 3 4 8x x x x . . . x 5+ + + + + =
Podemos observar que para formar uma solução devemos arrumar em fila 
de 5 bolas (pois em cada solução o total de unidades nas incógnitas é 5) e 6 traços 
(para separar 8 incógnitas, usamos 7 traços). Assim o número total de soluções são 
as permutações dos 12 elementos (5 bolas e 7 traços) com 5 e 7 repetições, ou seja 
( )
 5,7
5 7
12!
P 792
5!7!+
= = .
Portanto, a equação 1 2 3 4 8x x x x . . . x 5+ + + + + = tem 792 solução 
ou há 792 formas de comprar 5 sorvetes numa sorveteria que ofereça 8 sabores 
diferentes. 
De modo geral, para calcular o número de combinações completas de classe 
p a partir de n elementos distintos ( )n, pCR ou encontrar o número de soluções da 
equação 1 2 3 4 nx x x x . . . x p+ + + + + = , teríamos p bolas e (n-1) traços. Logo, 
 p, n-1
n, p (p n 1) n p 1, pCR P C+ - + -= = 
 ou n, p n p 1, pCR C .+ -=
ExErcícioS rESolvidoS 
1. Quantas são as soluçõesinteiras e não negativas de 6?x y z+ + =
Solução:
3, 6 3 6 1, 6 8,6
8!
CR C . C 28
6!.2!+ -
= = = =
29
2. De quantos modos podemos comprar 3 refrigerantes em uma 
supermercado onde há 5 tipos de refrigerantes?
Solução:
5, 3 5 3 1, 3 7,3
7!
CR C . C 35
3!.4!+ -
= = = = p
3. Quantas são as soluções inteiras e não negativas da inequação 
6?x y z+ + £ 
Solução:
Considerando que 6,x y z+ + £ então 6,x y z+ + = 5,x y z+ + = 
4,x y z+ + = 3,x y z+ + = 2,x y z+ + = 1 ex y z+ + = 0.x y z+ + = Assim, 
temos:
3, 6 3, 5 3, 4 3, 3 3, 2 3, 1 3, 0CR CR CR CR CR CR CR+ + + + + + =
8 , 6 7 , 5 6 , 4 5 , 3 4 , 2 3 , 1 3 , 0C C C C C C C+ + + + + + =
8! 7! 6! 5! 4! 3! 3!
6! 2! 5! 2! 4! 2! 3! 2! 2! 2! 2! 3!
+ + + + + + =
 
28 21 15 10 6 3 1 84+ + + + + + = . 
Podemos resolver esta inequação de outra forma.
Tendo em vista que 6,x y z+ + £ então 6 .x y z w+ + + = logo, temos 
que encontrar a solução da equação 4, 6CR 
ou seja 4, 6 9, 6
9!
CR C 84
6! 3!
= = =
4. Quantas são as soluções inteiras da equação 18x y z+ + = em que 
1, y 1 e z 1 x ³ ³ ³ .
Solução:
Para garantirmos que as incógnitas x, y e z sejam maiores que 1, devemos 
ter: x 1 a, y 1 b e z 1 c.= + = + = + Assim, a equação 18x y z+ + = fica 
a b c 15.+ + = Resolvendo-a, chegamos a 3, 15CR 136=
Chegamos ao final do tópico 1. Nele estudamos duas técnicas de contagem 
de suma importância ao estudo de combinatória. Consideramos que sem elas 
a resolução de muitos problemas (não triviais) que envolvem combinação e 
permutação torna-se ainda mais complicada. No próximo tópico continuaremos 
nossos estudos sobre resolução de problemas envolvendo análise combinatória e 
apresentaremos mais duas técnicas de agrupamento.
AULA 2 TÓPICO 1
30 Matemát ica D isc re ta
TÓPICO 2 Permutações Caóticase os Lemas de Kaplansky
ObjetivOs
• Proporcionar ao aluno um conhecimento sobre técnicas 
de permutações caóticas
• Desenvolver o raciocínio combinatório através dos 
estudos dos Lemas de Kaplansky para resolução de 
problemas
Embora existam outras ferramentas relacionadas às permutações e combinações, como por exemplo, 
as “permutações especiais”, que envolvem outras 
definições, vamos nos limitar apenas ao estudo 
de dois tipos de técnicas de agrupamentos que 
são as Permutações Caóticas, também conhecida 
como desarranjo e os Lemas de Kaplansky . 
2.1 PERMUTAÇÕES CAÓTICAS
Uma permutação dos algarismos ( )1, 2, . . . ,n é dita caótica quando nenhum 
elemento está no seu lugar de origem após as permutações. Por exemplo, 5467 e 4576 
representam permutações caóticas, ao passo que 5467 e 5746 não é. Para calcular 
o número de permutações caóticas de n elementos, que será representado por nD 
consideremos iA 
que representa o conjunto de permutações dos n elementos em 
que o número i ocupa o i-ésimo lugar com { }i 1, 2, 3, . . . , nÎ .
Devemos calcular o número de elementos do conjunto F de permutações 
de { }1, 2, 3, . . . , n que pertencem a exatamente zero dos conjuntos 
1 2 3 nA , A , A , . . . , A . Assim, 
( )0S # n!= F = e
s a i b a m a i s !
O trabalho de Kaplansky em Matemática é amplo, 
embora na maior parte esteja em áreas de Álgebra. 
Ele fez grandes contribuições para a teoria dos 
anéis, teoria dos grupos e teoria de campo. Fonte: 
<http://www.apprendre-math.info/portugal/
historyDetail.htm?id=Kaplansky>.
31
( ) ( ) ( )
n n
1 i
i 1 i 1
S # A n-1 ! n n-1 ! n!
= =
= = = =å å
( ) ( ) ( )2 i j n,2
1 i j n 1 i j n
n!
S # A A n-2 ! C n-2 !
2£ < £ £ < £
= Ç = = =å å
( )3 i j k
1 i j k n
S # A A A
£ < < £
= Ç Çå . . . nn n n!S C (n n)! n!= - = . 
Em que ( )i# A representa o número de elementos do conjunto iA . 
Assim, o número de elementos de F que pertencem a exatamente zero dos 
conjuntos 1 2 3 nA , A , A , . . . , A 
é 
 
n 0
k k
0 0 k 0 k
k 0
a ( 1) C S
-
+ +
=
= -å 
 
n
k
0 k
k 0
a ( 1) S
=
= -å
 ( )n0 0 1 2 3 na S S S S ... 1 S= - + - + + -
 
n
0
n ! n ! n!
a n ! n ! . . . ( 1)
2 3 n!
= - + - + + - 
( )n
0
11 1 1 1 1
a n ! . . .
0! 1! 2! 3! 4! n!
é ù-ê ú= - + - + - +ê úê úë û
Dessa forma, o número de permutações caóticas de {1, 2, 3, . . ., n} é:
( )n
n
11 1 1 1 1
D n ! . . .
0! 1! 2! 3! 4! n!
é ù-ê ú= - + - + - +ê úê úë û
Exemplo: O número de permutações caóticas dos números 1, 2, 3, 4 e 5 é:
5
1 1 1 1 1 1
D 5 !
0! 1! 2! 3! 4! 5!
é ù
= - + - + - =ê ú
ê úë û
1 1 1 1
120 1 1 46
2 6 24 120
æ ö÷ç - + - + - =÷ç ÷çè ø
ExErcício rESolvido: 
Quantas são as permutações dos elementos ( )1, 2, 3, 4, 5, 6, 7, 8 que tem 
exatamente 3 elementos no seu lugar primitivo?
Solução:
A quantidade de possibilidades ou o número de modos de escolher os 
elementos que ocuparão o seu lugar primitivo é 8, 3C . Depois disso, os outros cinco 
elementos devem ser arrumados caoticamente, o que pode ser feito de 5D modos. 
AULA 2 TÓPICO 2
Matemát ica D isc re ta32
Assim, temos:
8, 3 5
8! 1 1 1 1 1 1
C . D .5 ! 
3!.5 ! 0! 1! 2! 3! 4! 5!
æ ö÷ç= - + - + - ÷ç ÷çè ø
8, 3 5C . D 56 . 44 2. 464.= =
2.2 LEMAS DE KAPLANSKY
Os Lemas de Kaplansky são ferramentas utilizadas em problemas em que 
se pretende calcular o número de subconjuntos com p elementos, a partir de 
um conjunto que possui n elementos, considerando que esses subconjuntos não 
tenham elementos consecutivos.
Assim, por exemplo, para n=8 e p=3, podemos obter a partir de
{ } 1, 2, 3, 4, 5, 6 os seguintes subconjuntos nos quais não há elementos 
consecutivos: { } 1, 3, 6 , { } 1, 3, 5 , { } 1, 4, 6 e { } 2, 4, 6 . 
Poderíamos chegar à conclusão de que há quatro subconjuntos de 
elementos consecutivos { } 1, 2, 3, 4, 5, 6 sem a necessidade de enumerá-los. 
Vamos usar o seguinte raciocínio: ao formar um subconjunto, marcamos com o 
símbolo " "Ä os elementos que farão parte do conjunto, e com o símbolo ö" ", 
os elementos que não farão parte do conjunto. Assim, por exemplo, { } 1, 3, 5 
é representado pela sequência ö ö ö" "Ä Ä Ä e { } 2, 4, 6 representado 
por ö ö ö " "Ä Ä Ä são sequências válidas enquanto que a sequência 
ö ö ö " "Ä Ä Ä não é considerada válida, pois representa o subconjunto 
{ } 2, 3, 6 , que possui os elementos 2 e 3 consecutivos. 
Dessa forma, para formar subconjuntos com 3 elementos não consecutivos 
devemos colocar três sinais Ä e três sinais ö em fila, de sorte que não haja dois 
sinais Ä consecutivos. Assim, temos 1 modo de colocar os sinais ö e 4, 3C 
modos de colocar os três sinais Ä nos quatro lugares restantes. Assim, pelo PFC 
temos 4, 31 . C 4= subconjuntos de três elementos não consecutivos do conjunto 
{ } 1, 2, 3, 4, 5, 6 .
De modo geral, temos p sinais Ä e (n-p) sinais ö para organizar o conjunto, 
de tal forma que não haja dois sinais Ä consecutivos. Assim, temos 1 modo de 
arrumar os sinais ö e n-p 1, pC + modos de colocar os símbolos . Ä Portanto, 
podemos enunciar os lemas de Kaplansky:
Primeiro Lema de Kaplansky: O número de subconjuntos de { } 1, 2, 3, . . . ,n nos 
quais não há elementos consecutivos é n-p 1, pf(n,p) C .+=
33
ExErcício rESolvido: 
1. Considere uma fila de 10 cadeiras nas quais devem se sentar 4 
mulheres, de modo que não fiquem duas mulheres sentadas em 
cadeiras adjacentes. De quantas maneiras isso pode ser feito?
Solução:
Esse problema é composto por duas etapas: na primeira etapa, 
devemos escolher 4 cadeiras não consecutivas, o que pode ser feito de 
10-4 1, 6 7, 6
7!
f(10,4) C C 7.
6!.1!+
= = = = Na segunda etapa, devemos verificar de 
quantas formas podemos sentar as 4 mulheres nas quatro cadeiras escolhidas, 
o que pode ser feito de 4! modos diferentes. Assim, pelo PFC temos: P4! . 
4 . 10-4 1, 6 4 7, 6
7!
f(10,4) P C P C 4! 24.7 168.
6!.1!+
= = = = =
dEmonStração:
Vamos supor que os elementos do conjunto { } 1, 2, 3, . . . ,n estão 
organizados em círculo como mostra a figura 5. 
Figura 5 – Elementos em circulo
Podemosobservar que os elementos dispostos desta forma torna o 1 
e o n consecutivos. Agora vamos determinar o número de modos de formar p 
subconjuntos de { } 1, 2, 3, . . . ,n em que não haja números consecutivos. O 
número total de subconjuntos será a soma do número de subconjuntos nos quais 
o elemento “1” figura, com o número de subconjuntos nos quais o elemento “1” 
não figura.
AULA 2 TÓPICO 2
Segundo Lema de Kaplansky: O número de subconjuntos de { } 1, 2, 3, . . . ,n com p 
elementos nos quais não há elementos consecutivos é, considerando 1 e n como consecutivos, 
é dado por n-p, p
n
g(n,p) . C .
n p
æ ö÷ç ÷=ç ÷ç ÷ç -è ø
Matemát ica D isc re ta34
Para formar os subconjuntos nos quais o elemento “1” faz parte, 
devemos escolher p-1 elementos do conjunto { } 1, 2, 3, . . . ,n-1 para serem 
os companheiros do número “1” no subconjunto. Não podem ser escolhidos 
elementos consecutivos. O número de maneiras resultantes dessa organização é 
n-3-(p-1) 1, p-1 n p 1, p-1f (n-3;p-1) C C .+ - -= =
Para formar os subconjuntos nos quais o elemento “1” não faz parte, devemos 
escolher p elementos em { } 2, 3, . . . ,n , não podendo ser escolhidos elementos 
consecutivos. Isso pode ser feito de n-1-p 1 n p, pf(n-1,p) C C .+ -= = Assim a resposta é
( )
( ) ( )
( )
( )n-p-1, p-1 n p, p
n p 1 ! n p !
C C
p 1 ! n 2p ! p! n 2p !-
- - -
+ = +
- - - 
( ) ( )
( )n-p-1, p-1 n p, p
n p 1 ! p n-p !
C C
p! n 2p !-
- - +
+ =
-
( )
( )
( )n-p-1, p-1 n p, p
p n-p
C C n p 1 !
p! n 2p !-
+
+ = - -
- 
( )
( )n-p-1, p-1 n p, p
n p 1 ! 
C C n 
p! n 2p !-
- -
+ =
-
( )
( )n-p-1, p-1 n p, p
n p ! n
C C 
n p p! n 2p !-
é ùæ ö -÷ç ê ú÷+ =ç ÷ ê úç ÷ç - -è ø ê úë û
n-p-1, p-1 n p, p n-p, p
n
C C C
n p-
æ ö÷ç ÷+ =ç ÷ç ÷ç -è ø
ExErcício rESolvido
Seis pessoas devem se sentar em 12 cadeiras postas em torno de uma mesa 
circular. De quantas maneiras isso pode ser feito se não deve haver ocupação 
simultânea de duas cadeiras consecutivas? 
Solução:
O número de maneiras de escolher as cadeiras que serão usadas é 
12 6, 6
12
f (12, 6) .C 
12-6 -
= Þ 6, 6f (12, 6) 2. C = Þ f (12, 6) 2.=
Escolhidas as cadeiras, há 6!=720 modos de indicá-las para as 6 pessoas. 
Assim, pelo PFC temos 2 x 720=l440 modos de sentar 6 pessoas numa mesa circular 
com 12 lugares, de modo que não se tenha duas cadeiras consecutivas ocupadas.
Nesta aula estudamos algumas técnicas de contagem que não aparecem com tanta 
frequência nos livros didáticos, porém de grande importância no enriquecimento de 
nossos conhecimentos matemáticos
35AULA 2 TÓPICO 2
at i v i d a d e d e a p r o f u n d a m e n t o
1. De quantos modos podemos formar uma roda de ciranda com 8 
crianças, de modo que duas determinadas crianças não fiquem 
juntas?
2. Quantas são as soluções inteiras e não negativas de x y z 9?+ + < 
3. Quantas são as soluções inteiras da equação x y z 10+ + = em 
que 2, y 2 e z 2x ³ ³ ³ ? 
4. Quantas são as permutações dos elementos ( )1, 2, 3, 4, 5, 6, 7 que 
tem exatamente 4 elementos no seu lugar primitivo?
5. De quantas formas 6 homens podem se sentar numa fila de 14 
cadeiras, de tal forma que não fiquem dois homens sentados em 
cadeiras vizinhas?
6. Quantos são os anagramas da palavra PARAGUAI que não possuem 
duas letras A consecutivas?
36 Matemát ica D isc re ta
AULA 3 Coeficientes Binomiais, Triângulo de Pascal e 
Números de Fibonacci
Caro(a) aluno(a), agora que estamos familiarizados com as ferramentas básicas 
da análise combinatória, daremos continuidade aos nossos estudos através dos 
Coeficientes Binomiais, Triângulo de Pascal e dos Números de Fibonacci.
No primeiro tópico, definiremos os coeficientes binomiais assim como algumas de 
suas propriedades e veremos como tais coeficientes e suas propriedades estão 
relacionados ao triângulo de Pascal através de alguns teoremas. No segundo 
tópico, veremos que a utilização dos coeficientes binomiais no desenvolvimento 
de potências do binômio do tipo ( x y )
n+ , sendo n um número natural, pode 
tornar o processo bem menos cansativo do que estamos habituados. Finalmente, 
no terceiro tópico concluiremos nossa aula com os Números de Fibonacci. Estes 
nos mostram relações fascinantes com a natureza.
Objetivos
• Desenvolver potências do binômio (x + y), utilizando os coeficientes binomiais
• Compreender os conceitos sobre o Triângulo de Pascal e algumas 
propriedades relacionadas
• Conhecer a sequência dos Números de Fibonacci
37
Vamos iniciar este tópico com algumas definições:(i) O coeficiente binomial, também chamado de número binomial de um número n, na classe p, com n p,³ 
representado por 
n
 ,
p
æ ö÷ç ÷ç ÷ç ÷çè ø
 consiste no número de combinações de n termos, 
tomados de p a p, ou seja, 
n n . (n-1) . (n-2). . . (n-p 1)n!
p p!(n p)! p!
æ ö +÷ç ÷= =ç ÷ç ÷ç -è ø
. 
Em que n é o numerador e p, o denominador.
(ii) Dois números binomiais de mesmo numerador são ditos complementares 
quando a soma dos denominadores é igual ao numerador. Assim, 
8 8
 e 
2 6
æ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
 são complementares, pois 6+2=8. De um modo geral 
n n
 e 
p n-p
æ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
são complementares, pois p (n-p) n.+ =
1.1 PROPRIEDADES DOS COEFICIENTES BINOMIAIS
a. Dois números binomiais complementares são iguais. 
Para justificar esta afirmação, basta desenvolver o segundo lado da equação
n n
 
p n-p
æ ö æ ö÷ ÷ç ç÷ ÷=ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
. Assim, 
[ ]
n n! n!
 
n-p (n-p)! n-(n-p) ! p!(n p)!
æ ö÷ç ÷ = =ç ÷ç ÷ç -è ø
 .
TÓPICO 1 Coeficientes Binomiais Triângulo de Pascal
ObjetivOs
• Conhecer os Coeficientes Binomiais
• Relacionar os Coeficientes binomiais e algumas de suas 
propriedades ao triângulo de Pascal
AULA 3 TÓPICO 1
Matemát ica D isc re ta38
b. Relação de Stifel.
A relação de Stifel, também conhecida como regra de Pascal, é representada 
pela igualdade 
n 1 n n
 
p 1 p p 1
æ ö æ ö æ ö+ ÷ ÷ ÷ç ç ç÷ ÷ ÷= +ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç+ +è ø è ø è ø
.
Vamos justificar esta propriedade com o seguinte problema:
Considere um conjunto A que possui n 1+ elementos, um dos quais é 
x. O número de subconjuntos de A com p 1+ elementos é dado por n 1, p 1C + + .
. 
Outra forma de representar a solução desse problema é somando o número de 
subconjuntos nos quais x aparece como número de subconjuntos nos quais x não 
figura, ou seja, igualando as duas expressões, temos n 1, n 1 n, p n, p 1 C C C+ + = += + ou 
seja 
n 1 n n
 
p 1 p p 1
æ ö æ ö æ ö+ ÷ ÷ ÷ç ç ç÷ ÷ ÷= +ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç+ +è ø è ø è ø
.
ExEmplo:
Para resolvermos a equação 
5a-15 5a-15 5a-14
 
2a 2a 1 a-1
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷+ =ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç+è ø è ø è ø , utilizaremos a 
relação de Stifel. Vejamos:
5a-15 5a-15 5a-14 5a-14 5a-14
 
2a 2a 1 2a 1 2a 1 a 1
æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷+ = Þ =ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç ç+ + + -è ø è ø è ø è ø è ø
Pela propriedade dos binomiais complementares, temos que:
( ) ( )
 5a-14 5a-14
 2a 1 a 1 5a 14
2a 1 a 1
æ ö æ ö÷ ÷ç ç÷ ÷= Þ + + - = -ç ç÷ ÷ç ç÷ ÷ç ç+ -è ø è ø
Resolvendo a equação encontrada, teremos o valor de a:
( ) ( ) 2a 1 a 1 5a 14 3a 5a - 14 -2a -14 a 7+ + - = - Þ = Þ = Þ =
c. Para todo n natural têm-se: n
n n n n
. . . 2
0 1 2 n
æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷+ + + + =ç ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷ç ç ç çè ø è ø è ø è ø 
Para justificarmos a propriedade acima, vamos considerar o seguinte problema: 
um conjunto A tem n elementos. Quantos são os subconjuntos desse conjunto? 
Solução:
Com 1 elemento temos n, 1C ; com 2 elementos, temos n, 2C elementos; com 3 
elementos, temos n, 3C . . . com n elementos, temos n, nC . Além desses, temos mais 
39
1 conjunto que é o vazio. Assim o número de subconjuntos de um conjunto com 
n elementos é n, 1 n, 2 n, 3 n,n1 C C C . . . C (*).=+ + + + + Outra forma de resolver este 
problemaé imaginando que a ação de formar um subconjunto é formada por várias 
etapas em que devemos decidir, em cada etapa, se um dado elemento pertencerá ou 
não ao subconjunto. Dessa forma, para o primeiro elemento, temos 2 possibilidades 
(ele pertencerá ou não pertencerá ao subconjunto); para o segundo elemento, 
temos também duas possibilidades e assim em diante. Seguindo esse raciocínio 
para os demais elementos e usando o Principio Fundamental da Contagem, temos: 
2x 2 x 2 x . . . x 2 ( n vezes ), ou seja n2 (**). Igualando os resultados (*) e (**), temos: 
n
n, 1 n, 2 n, 3 n,n1 C C C . . . C 2=+ + + + + = ou 
n
n n n n
. . . 2
0 1 2 n
æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷+ + + + =ç ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷ç ç ç çè ø è ø è ø è ø
.
ExEmplo:
Uma casa tem 6 portas. De quantos modos pode ser aberta essa casa? 
Solução:
Há 6, 1C maneiras de abrir a casa, usando apenas uma só porta; 6, 2C 
maneiras de abrir a casa, usando duas portas, e assim em diante. A resposta é: 
6
6, 1 6, 2 6, 3 6, 6
6 6 6
 C C C . . . C . . . 2 1 63
1 2 6=
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷+ + + + = + + + = - =ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç çè ø è ø è ø
l
1.2 O TRIÂNGULO DE PASCAL
O triângulo de Pascal ou triângulo aritmético é formado por números 
binomiais que têm diversas relações entre si. Algumas dessas relações que são as 
propriedades dos números binomiais já estudadas no início deste tópico, e outras 
que julgamos irrelevantes para nossa disciplina podem ser encontradas nos livros 
didáticos de Matemática para o ensino médio. De todo modo, muitas dessas relações 
foram descobertas pelo próprio Pascal, o que justifica o nome que lhe é dado. 
O triângulo de Pascal é organizado em linhas e colunas (figura 1 ), de tal modo 
que o numerador n do número binomial represente a linha em que o elemento se 
encontra, e o denominador p do número binomial represente a coluna em que o 
elemento se encontra. Veja figura 1.
AULA 3 TÓPICO 1
Matemát ica D isc re ta40
0
 
0
1 1
 
0 1
2 2 2
 
0 1 2
3 3
 
0
æ ö÷ç ÷ç ÷ç ÷çè ø
æ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç çè ø è ø è ø
æ ö÷ç ÷ç ÷ç ÷çè ø
3 3
 
1 2 3
 ............................................
n n n n n n
 ... 
0 1 2 3 4
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç çè ø è ø è ø
æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç çè ø è ø è ø è ø è ø
 
n
 1ª Forma
æ ö÷ç ÷ç ÷ç ÷çè ø
0
 
0
1 1
 
0 1
2 2 2
 
0 1 2
3 3 3 3
 
0 1 2 3
............................
æ ö÷ç ÷ç ÷ç ÷çè ø
æ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç çè ø è ø è ø
æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷ç ç ç çè ø è ø è ø è ø
................
n n n n n n
 ... 
0 1 2 3 4 n
 2ª Forma
æ ö æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç çè ø è ø è ø è ø è ø è ø
ou
Figura 1: Triângulo Aritmético ou Triângulo de Pascal
Acima estão as duas formas triangulares que são abordadas por diferentes 
autores. Para efeito de clareza, adotaremos a 2ª forma. Entretanto, antecipamos: 
não fazemos distinção quanto às propriedades, uma vez que as linhas são formadas 
pelos mesmos números. 
0
linha 0 
0
1 1
linha 1 
0 1
2 2 2
linha 2 
0 1 2
3 3 3
linha 3 
0 1 2
æ ö÷ç ÷ç ÷ç ÷çè ø
æ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç çè ø è ø è ø
æ ö æ ö æ÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø è
3
 
3
............................................
n n n n n
linha n . . . 
0 1 2 3 n
 
ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çø è ø
æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç ç÷ ÷ ÷ ÷ ÷ç ç ç ç çè ø è ø è ø è ø è ø
 
Coluna 0
Coluna 1
Coluna 2
Coluna 3
Coluna n
Figura 2:As linhas são as filas horizontais, e as colunas, as filas verticais
41
Ao substituirmos cada coeficiente 
binomial pelo seu valor, obteremos:
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
. . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 PROPRIEDADES DO TRIÂNGULO DE PASCAL
Apresentaremos quatro propriedades que estão relacionadas com o Triângulo 
de Pascal, em seguida, na intenção de fixarmos o conteúdo e esclarecermos as 
possíveis dúvidas, veremos alguns exercícios resolvidos.
a. Toda linha do Triângulo de Pascal começa e termina com 1.
Justificativa: Esses elementos são do tipo 
n n 
 1 e 1
0 n 
æ ö æ ö÷ ÷ç ç÷ ÷= =ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
b. Partindo da segunda linha, podemos construir o Triângulo de Pascal, 
aplicando a relação de Stifel.
Vejamos o exemplo ilustrativo abaixo:
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
. . . . . . . . . . . . . . . . . . . . . . . . . .
2 2
1 2 3
0 1
3
3
1
æ öæ ö÷ ÷ç ç÷ ÷= + =ç ç÷ ÷ç ç÷ ÷ç çè øè ø
æ ö÷ç ÷=ç ÷ç ÷çè ø
Figura 3:Triângulo de Pascal aplicando a relação de Stifel
c. Em qualquer linha do triângulo de Pascal, os coeficientes equidistantes 
dos extremos são iguais.
Justificativa: Propriedade dos binomiais complementares. 
Veja abaixo o exemplo ilustrativo.
Na linha 7 do Triângulo de Pascal, temos:
7 7 7 7 7 7 7 7
 1 7 21 35 35 
0 1 2 3 4 5 6 7
æ ö æ ö æ ö æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ Ûç ç ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç ç çè ø è ø è ø è ø è ø è ø è ø è ø

 21 7 1



at e n ç ã o !
O Triângulo de Pascal também é conhecido como 
Triângulo Aritmético de Tartaglia, e recebe estes 
nomes em homenagem a Nicolo Fontana Tartaglia, 
matemático italiano (1500-1557) e Blaise Pascal, 
matemático, filósofo e físico francês (1623-1662).
AULA 3 TÓPICO 1
Matemát ica D isc re ta42
d. A soma dos elementos da linha n é igual 2n.
n = 0 1 1 = 20
n = 1 1 1 1 + 1 = 21
n = 2 1 2 1 1 + 2 + 1 + 4 = 22
n = 3 1 3 3 1 1 + 3 + 3 + 1 = 8 = 23
n = 4 1 4 6 4 1 1 + 4 + 6 + 4 + 1 = 16 = 24
ExErcícioS rESolvidoS
1. Calcule a soma dos elementos da linha 11ª linha do triângulo de Pascal. 
Solução:
A linha 11ª linha do triângulo de Pascal é a linha 10, já que a primeira linha 
é a linha zero, assim:
 
10
10 10 10 10 10 10
. .. 2 1024
0 1 2 3 8 9
æ ö æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷+ + + + + + = =ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç çè ø è ø è ø è ø è ø è ø
.
2. O produto dos dois primeiros elementos de uma linha do triângulo de 
Pascal é igual a 32. Qual é o terceiro elemento da linha seguinte? 
rESolução:
Vimos que o primeiro elemento de qualquer linha é sempre igual a 1. Daqui, 
conseguimos deduzir que o segundo elemento, da linha mencionada, é 32.
Basta observamos o comportamento dos dois primeiros elementos de algumas 
linhas do Triângulo de Pascal, para afirmarmos que na linha 33, o segundo elemento 
é 32.
Porém, o que queremos é o terceiro elemento da linha seguinte, ou seja, da 
linha 34.
Linha 34: 
34 34 34 34 34 34
 ... 
0 1 2 3 33 34
æ ö æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç çè ø è ø è ø è ø è ø è ø
Temos, como terceiro elemento, o coeficiente binomial 
34 34!
 561
2 2!(34-2)!
æ ö÷ç ÷ = =ç ÷ç ÷çè ø
Nesse tópico, tivemos a oportunidade de dispor, com a utilização de algumas 
propriedades,de uma tabela (figura 1) que contém os valores dos coeficientes 
binomiais que serão utilizados como ferramenta no desenvolvimento de alguns 
binômios que serão estudados no tópico seguinte. 
43
Neste tópico, começaremos analisando algumas situações, pois nossa intenção é partir da necessidade de facilitar o desenvolvimento de algumas potências. 
Situação I - O desenvolvimento de n( x y )+ para alguns valores de n são:
• 0( x y ) 1+ =
• 1( x y ) 1x 1y+ = +
• 2 2 2 2 2( x y ) (x y).(x y) x xy yx y 1x 2xy 1y+ = + + = + + + = + +
• 3 2 2 2( x y ) (x y) .(x y) (1x 2xy 1y ).(x y)+ = + + = + + +
3 3 2 2 3 ( 1) 1x 3x y 3xy 1yxÞ + = + + +
Percebemos que, na medida em que o natural n cresce, o processo de 
desenvolvimento torna-se cada vez mais cansativo.
ExEmplo 1: 
Podemos desenvolver 3( x y )+ , da seguinte forma:
3( x y ) (x y) . (x y) . (x y)+ = + + +
Se aplicarmos a propriedade distributiva, em cada um dos fatores 
escolheremos x ou y. Assim, cada termo do desenvolvimento envolve um produto 
de três letras.
Para uma melhor compreensão, visualizemos na figura 1 o “Diagrama de 
Árvore”.
TÓPICO 2 Binômio de Newton
ObjetivO
• Utilizar os coeficientes binomiais no desenvolvimento de 
potências do tipo (ax+b)n
AULA 3 TÓPICO 2
Matemát ica D isc re ta44
 Figura 1: Arvore das possibilidades para o desenvolvimento (x+y)3
O resultado da potência 3( x y )+ é obtido pela soma dos termos encontrados, ou 
seja, 3 3 2 2 3( x y ) x 3x y 3xy y+ = + + + (mesmo resultado encontrado anteriormente).
Através deste exemplo podemos retirar as seguintes informações:
• Existe apenas uma maneira de se obter 3x , que é pelo produto x.x.x , 
ou seja, seu coeficiente é 
3
1 ;
0
æ ö÷ç ÷= ç ÷ç ÷çè ø 
• Existe três maneiras de se obter 2x y , que é pelo produto x.y.x , x.x.y
e y.x.x, ou seja, seu coeficiente é 
3
3 ;
1
æ ö÷ç ÷= ç ÷ç ÷çè ø 
• Existe três maneiras de se obter 2xy , que é pelo produto y.y.x , x.y.y
e y.x.y, ou seja, seu coeficiente é 
3
3 ;
2
æ ö÷ç ÷= ç ÷ç ÷çè ø 
• Existe apenas uma maneira de se obter 3y , que é pelo produto y.y.y , 
ou seja, seu coeficiente é 
3
1 ;
3
æ ö÷ç ÷= ç ÷ç ÷çè ø 
Em resumo: 
3 3 2 2 3
3 3 3 3
(x y) x x y x y y
0 1 2 3
æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷+ = + + +ç ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷ç ç ç çè ø è ø è ø è ø
De um modo geral, a potência n(x y)+ , com 
x, y RÎ e n NÎ
 
é conhecida como Binômio 
de Newton. Para desenvolvê-la, devemos efetuar 
o produto: 
n vezes
(x y) . (x y) . ... . (x y)+ + +

at e n ç ã o !
Vimos que o número de combinações de n 
elementos tomados p a p é dado por 
n!
p! (n p)!-
. Porém, existem outras formas de indicar esse 
cálculo, que são:
p
nC ou 
n
p
æ ö÷ç ÷ç ÷ç ÷çè ø
.
45
Assim, iremos obter a seguinte fórmula:
n n 0 n - 1 1 n - 2 2
n - 3 3 n - k k n
n n n
( x y ) x y x y x y
0 1 2
n n n
 x y ... x y ... xy
3 k n
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷+ = + + +ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç çè ø è ø è ø
æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷+ + + +ç ç ç÷ ÷ ÷ç ç ç÷ ÷ ÷ç ç çè ø è ø è ø
O coeficiente de n - k kx y é dado pelo número de combinações de n elementos, 
tomados k a k, onde n e k são naturais, com n ≥ k, e é chamado de número binomial 
de n sobre k.
Aqui, dizemos que n é o numerador e k o denominador do número 
binomial.
Percebe-se que os expoentes do x decrescem, de 1 em 1 unidade, e os 
expoentes do y crescem até n, também de 1 em 1 unidade.
ExEmplo 2: 
O binômio ( )32 2a 2b+ é dado por:
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )0 1 2 33 2 1 02 2 2 2
3 3 3 3
 . 2a . 2b . 2a . 2b . 2a . 2b . 2a . 2b
0 1 2 3
æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷+ + +ç ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷ ÷ç ç ç çè ø è ø è ø è ø
Utilizado a fórmula de combinação, junta a algumas operações básicas, 
obtemos:
( )32 3 2 2 4 6 2a 2b 8a 24 a b 24 ab 8b+ = + + +
ExEmplo 3:
No desenvolvimento de 8(a b) ,+ os 
coeficientes do 3º e do 7º termos são iguais. 
JuStificativa:
Os coeficientes do 3º e do 7º termos são 
dados por 
8 8
 e ,
2 6
æ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
 respectivamente, que, 
pela Propriedade dos binomiais complementares, 
são iguais, uma vez que 2 + 6 = 8.
v o c ê s a b i a?
A linha n do Triângulo de Pascal é composta pelos 
coeficientes binomiais do desenvolvimento do 
Binômio de Newton ( )n x y + , para os valores 
crescentes de n.
AULA 3 TÓPICO 2
Matemát ica D isc re ta46
ExErcícioS rESolvidoS
No desenvolvimento de ( )15 x y ,+ qual o 9º termo? 
rESolução:
Recorrendo à fórmula do Binômio de Newton, descobriremos que o termo é 
dado por 15 - 8 8
15
 x y
8
æ ö÷ç ÷ç ÷ç ÷çè ø
, ou seja, o 9º termo o binômio ( )15 x y + é 7 86 435 x y .
2. Desenvolva ( )5 2x y - , utilizando a fórmula do Binômio de Newton. 
rESolução:
Podemos enxergar o binômio acima da seguinte forma: ( )
5
2 x yé ù+ -ë û , 
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
( )( ) ( )
5 2 35 4 3 2
4 5
5 5 5 5
2x -y 2x 2x -y 2x -y 2x -y 
0 1 2 3
5 5
 2x -y -y
4 5
æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ç ç ç çé ù ÷ ÷ ÷ ÷+ = + + + +ç ç ç ç÷ ÷ ÷ ÷ë û ç ç ç ç÷ ÷ ÷ ÷ç ç ç çè ø è ø è ø è ø
æ ö æ ö÷ ÷ç ç÷ ÷+ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
 
Logo,
( )5 5 4 3 2 2 3 4 5 2x y 32x 80 x y 80 x y 40 x y 10 xy y- = - + - + -
3. Desenvolva e simplifique a potência 
41
 a b
2
æ ö÷ç + ÷ç ÷çè ø .
rESolução:
4 0 1 2
4 3 2
3 4
1 0
4 4 41 1 1 1
 a b a b a b a b
0 1 22 2 2 2
4 41 1
 a b a b
3 42 2
æ ö æ ö æ öæ ö æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷+ = + + +ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷÷ ÷ ÷ ÷ç ç ç çç ç ç÷ ÷ ÷ç ç çè ø è ø è ø è øè ø è ø è ø
æ ö æ öæ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷+ç ç÷ ÷ç ç÷ ÷÷ ÷ç çç ç÷ ÷ç çè ø è øè ø è ø
Partindo da propriedade dos binomiais complementares, não é necessário 
calcular todos os “números binomiais”. Analisemos, especificamente, a situação 
abaixo:
4 0 1 2
4 3 2
3 4
1 0
4 4 41 1 1 1
 a b a b a b a b
0 1 22 2 2 2
4 41 1
 a b a b
3 42 2
æ ö æ ö æ öæ ö æ ö æ ö æ ö÷ ÷ ÷ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷+ = + + +ç ç ç÷ ÷ ÷ ÷ç ç ç ç÷ ÷ ÷÷ ÷ ÷ ÷ç ç ç çç ç ç÷ ÷ ÷ç ç çè ø è ø è ø è øè ø è ø è ø
æ ö æ öæ ö æ ö÷ ÷ç ç÷ ÷ç ç÷ ÷+ç ç÷ ÷ç ç÷ ÷÷ ÷ç çç ç÷ ÷ç çè ø è øè ø è ø
47
Veja que 
4 4
0 4
æ ö æ ö÷ ÷ç ç÷ ÷=ç ç÷ ÷ç ç÷ ÷ç çè ø è ø 
e 
4 4
1 3
æ ö æ ö÷ ÷ç ç÷ ÷=ç ç÷ ÷ç ç÷ ÷ç çè ø è ø
 e lembre-se de que n, p
n!
C
p!(n p)!
=
-
 
Simplificando, temos: 
4
4 3 2 2 3 41 3 1 1 a b a 2 a b a b a b b
2 2 2 16
æ ö÷ç + = + + + +÷ç ÷çè ø
4. No desenvolvimento de ( )15x 3y- qual é a soma de todos os coeficientes? 
rESolução:
( ) ( ) ( ) ( ) ( )2 3 4 55 5 4 3 2
5 5 5 5 5 5
( x 3 y ) x x -3y x -3y x -3y x -3y -3y
0 1 2 3 4 5
æ ö æ ö æ ö æ ö æ ö æ ö÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷- = + + + + +ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç ç÷ ÷ ÷ ÷ ÷ ÷ç ç ç ç ç çè ø è ø è ø è ø è ø è ø
( ) ( ) ( ) ( ) ( )2 3 4 55 5 4 3 2( x 3 y ) 1.x 5. x -3y 10. x -3y 10. x -3y 5. x -3y -3y- = + + + + +
5 5 4 3 2 2 3 4 5( x 3 y ) x -15 x y 90 x y -270 x y 405 xy -243 y- = + +
Os coeficientes de ( )15x 3y- são:
 
1, (-15), 90, (-270), 405 e (-243) .
Sendo assim, a soma é: 1+ (-15) + 90 + (-270) + 405 + (-243) = -32
Vimos neste tópico que os coeficientes binomiais nos ajudam no 
desenvolvimento de algumas potências, que são conhecidas como Binômio de 
Newton. No próximo tópico, conheceremos a sequência de Fibonacci, assim como 
algumas relações entre os números que compõe essa relação.
AULA 3 TÓPICO 2
48 Matemát ica D isc re ta
TÓPICO 3 Números de Fibonacci
ObjetivOs
• Conhecer a sequência dos números de Fibonacci e algu-
mas relações entre os números desta sequência
• Entender as aplicações dos números de Fibonacci na 
natureza
Neste tópico, iremos trabalhar com os números de Fibonacci, que recebem este nome em homenagem ao matemático italiano, Leonardo de Pisa, mais conhecido como Fibonacci. Teremos ainda 
a oportunidade de analisarmos algumas importantes propriedades, assim como as 
relações existentes entre estesnúmeros.
Iniciaremos nosso estudo através do seguinte problema:
Quantos pares de coelhos podem ser gerados em um casal de coelhos durante 
um ano?
Abaixo estão listadas as condições de vida destes coelhos.
• No primeiro mês temos um casal de coelhos. Estes dois coelhos 
acabaram de nascer. 
• Um coelho só atinge a maturidade sexual 
ao fim de um mês. 
• O período de gestação de um coelho dura 
um mês. 
• Ao atingirem a maturidade sexual, a fêmea 
irá dar à luz todos os meses. 
• A mãe irá dar um casal de coelho todos os 
meses. 
• Os coelhos nunca morrem. 
Seguindo as condições de vida, citadas acima, analisemos o comportamento 
do número de pares de coelhos que surgem ao longo dos quatro primeiros meses:
1º mês: um casal inicial de coelhos (chamemos de casal 1);
s a i b a m a i s !
No endereço http://www.educ.fc.ul.pt/icm/
icm99/icm41/suc-fib.htm você poderá encontrar 
o desenvolvimento, passo a passo, do nosso 
problema.
http://www.educ.fc.ul.pt/icm/icm99/icm41/suc-fib.htm
http://www.educ.fc.ul.pt/icm/icm99/icm41/suc-fib.htm
49
2º mês: o casal 1 acaba de atingir a idade sexual;
3º mês: o casal 1 + o novo casal (casal 2);
4º mês: o casal 1 dá origem a mais um casal 
(casal 3), porém o casal 2 acaba de atingir a idade 
sexual.
Através desta linha de raciocínio e, sempre 
de acordo com as condições de vida citadas, 
chegaremos à seguinte sequência de inteiros 
positivos:
Tais números mostram, respectivamente, a quantidade de pares de coelhos 
nos meses 1, 2, 3, 4, ... . 
Veja que f1 = f2 = 1 e f n = f n - 1 + f n – 2 para n > 2
rElação EntrE oS númEroS dE fibonacci E o triângulo dE paScal
Vimos, no tópico anterior, que o Triângulo de Pascal pode ser substituído 
pelos seus respectivos valores. Fazendo algumas observações, Leonardo de Pisa 
percebeu que os mesmo números que surgiram no “problema dos coelhos”, também 
surgiram através da soma de vários números binomiais, veja a seguir:
algunS tEorEmaS rElacionadoS aoS númEroS dE fibonacci
a) A soma dos n primeiros números de Fibonacci é igual a f
 n + 2
 – 1
dEmonStração:
Analisando a sequência, temos que:
 f1 = f3 – f2 = f3 – 1 , f2 = f4 – f3 ... enfim, fn = fn+2 – fn+1
v o c ê s a b i a?
Leonardo de Pisa escreveu, em 1202, um livro 
denominado Liber Abacci, que chegou a nós, 
graças à sua segunda edição de 1228. A teoria 
contida neste livro é ilustrada com muitos 
problemas, sendo que um destes problemas é 
justamente O problema dos pares de coelhos.
AULA 3 TÓPICO 3
Matemát ica D isc re ta50
Somando, ordenadamente, todas essas n igualdades e simplificando, obtemos:
n
i n 2
1
 f f 1+= -å
2. A soma dos n primeiros números de Fibonacci, com índices ímpares, é igual a f
2n
3. Soma dos n primeiros números de Fibonacci , com índices pares é igual f
2n+1
-1
4. A soma dos quadrados dos n primeiros números de Fibonacci é igual a f
n 
f 
n+1 
;
algumaS propriEdadES doS númEroS dE fibonacci
1. Dois números de Fibonacci consecutivos são primos entre si.
dEmonStração:
Precisamos mostrar que mdc (fn , fn+1) = 1. Assim sendo, recorreremos ao 
algoritmo de Euclides:
 
n 1 n n 1
n n 1 n 2
4 3 2
3 2
f 1.f f
f 1.f f
. . . . . . . . 
 f 1.f f
 f 2.f 0
+ -
- -
= +
= +
= +
= +
Logo, o mdc ( )n 1 2, f 1nf f+ = =
 2. O mdc de dois números de Fibonacci também é um número de Fibonacci.
3. Se /m nf f , então /m n e m e n são números de Fibonacci.
4. Soma dos quadrados de dois números de Fibonacci consecutivos também 
é um número de Fibonacci.
Nessa aula vimos que desenvolver o Binômio de Newton, recorrendo 
ao Triângulo de Pascal, que é decorrência do estudo do nosso primeiro tópico 
- Coeficientes Binomiais - é uma forma mais rápida de se chegar ao seu resultado. 
Também tivemos oportunidade de conhecermos os Números de Fibonacci e alguns 
teoremas e propriedades.
51
Caro(a) aluno(a),
Nesta aula, pretendemos proporcionar a você uma base razoável a respeito 
da teoria dos conjuntos, bem como ajudá-lo a construir conhecimentos sobre 
os métodos que relacionam dois conjuntos. No primeiro tópico, faremos um 
estudo sobre alguns conceitos de conjuntos e, no tópico seguinte, estudaremos 
as relações binárias que são usadas em muitos ramos da matemática, como 
aritmética, geometria, álgebra linear, ciência da computação, assim como no 
conceito de funções, na teoria dos grafos (que serão estudados mais adiante), etc.
Objetivos
• Familiarizar-se com a linguagem correta da teoria dos conjuntos
• Conhecer mecanismos que permitam relacionar dois conjuntos, como é o 
caso da relação binária
AULA 4 Conjuntos e relações
AULA 4
52 Matemát ica D isc re ta
TÓPICO 1 Conjuntos
ObjetivOs
• Compreender o uso da linguagem da teoria dos conjuntos
• Realizar operações com conjuntos
• Conhecer as notações mais importantes da teoria dos 
conjuntos
Neste tópico, vamos recordar essencialmente algumas notações que são usadas para conjuntos. Vamos considerar a noção de conjuntos como primitiva, partindo do princípio de que um 
conjunto é composto por elementos, que são objetos materiais abstratos que têm 
alguma propriedade em comum. Usamos letras maiúsculas para nomear conjuntos e 
minúsculas quando nos referirmos aos seus elementos. Para indicar que o elemento 
a é um elemento do conjunto A escrevemos Aa Î . 
Os conjuntos podem ser especificados basicamente de três modos:
1ª) através do diagrama (chamado diagrama de Venn), utilizado quando 
se pretende representar um conjunto finito com uma quantidade relativamente 
reduzida de elementos;
2ª) por extensão, que consiste em exibir todos os elementos que os constituem;
3ª) indicando uma propriedade que caracteriza os seus elementos. 
Assim, por exemplo, as três formas de representar o conjunto dos números 
Rx Î tais que o quadrado de x somado com triplo de x mais 2 seja nulo, são:
1ª) { }1, 2
2ª) { }2R / 3 2 0x x xÎ + + =
3ª) escrevendo os elementos no interior de um “balão” (diagrama de Venn)
53
Figura 1 – Diagrama de Venn
1. algumaS notaçõES importantES
 Sejam A e B conjuntos, assim:
Aa Î : a pertence a A, a é elemento de A
Aa Ï : a não pertence a A
A B= : igualdade de conjuntos (qualquer que seja x, A x Bx Î Þ Î )
A BÍ : A subconjunto de B ( x, x A" Î então x BÎ )
A B:Ê A contém B ou A BÍ .
A B:Ì A é subconjunto próprio de B ( A B A BÍ Ù ¹ )
A B:É A contém propriamente o conjunto
A B:¹ A não é subconjunto de B nem B é subconjunto de A.
0{ } ou :Æ Conjunto vazio.
2. opEraçõES com conJuntoS
O conjunto dos subconjuntos de A ou conjunto das partes de A, 
representado por ( )P A ou A2 é o conjunto formado por todos os subconjuntos 
de A. Qualquer conjunto A pertence ao seu conjunto dos subconjuntos, ou seja, 
A ( )P AÎ . Vejamos alguns exemplos:
{ } { } { } { } { } { } { } { }{ }P( 1, 2, 3 ) , 1 , 2 , 3 , 1, 2 , 1, 3 , 2, 3 , 1, 2, 3= Æ .
O conjunto { }( )˘?˘˘ tem 23 elementos. Também é possível se verificar que 
{ }( )( )P P 1, 2, 3 tem 322 elementos. Se A tem n elementos, ( )P A tem 2n elementos. 
Com efeito, se A tem n elementos, para formar cada subconjunto, deve-se decidir 
qual(is) elemento(s) farão parte do subconjunto P(A). Assim, o primeiro elemento 
tem duas possibilidades: ou faz parte ou não de um determinado subconjunto de 
AULA 4 TÓPICO 1
Matemát ica D isc re ta54
A. Para o segundo elemento, também há duas possibilidades. Seguindo o mesmo 
raciocínio para os demais elementos. Por último, temos 2 possibilidades para o 
n-ésimo elemento. Dessa forma, pelo Princípio Fundamental da Contagem (PFC), 
temos: 2x2x2x...x2 (n vezes) que dá 2n.
Um conjunto A não vazio é finito se e somente se existir uma bijeção de A em 
{ } x N/x nÎ < , n NÎ . Assim n é chamado cardinal de A, cuja notação é “#A ”, e 
representa o número de elementos de A. Dessa forma o cardinal 
do conjunto vazio é zero.
A interseção do conjunto A com o conjunto 
B representada por A BÇ é composta pelos elementos 
que pertencem a A e B simultaneamente. Assim:
{ }A