APOSTILA DE ANÁLISE COMBINATÓRIA

Prévia do material em texto

Prof. Ms. Francisco de Assis Amaral Bastos 
 
1ª EDIÇÃO – JUN 2013 
 
 
 
 
 
 
 
 
 
NOÇÕES DE 
LÓGICA 
 
 
 
 
CONJUNTOS 
 
 
 
 
 
 
 
ANÁLISE 
COMBINATÓRIA 
 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
1 
 
NOÇÕES DE LÓGICA 
 
PROPOSIÇÃO OU SENTENÇA 
Oração DECLARATIVA que pode ser classificada como VERDADEIRA (V) ou FALSA (F). 
NEGAÇÃO 
Se p é uma proposição, sua negação é representada por ~p 
 
 
 
POSTULADO: 
 
~p tem sempre valor lógico oposto a p, ou seja, ~p é F se p é V e ~p é V se p é F. 
 
 
 
O que pode ser representado pela seguinte TABELA VERDADE: 
 
 
p ~p 
V F 
F V 
CONECTIVOS 
CONJUNÇÃO () 
p  q é a conjunção de p e q 
 
 
POSTULADO: 
 
p  q é V se p e q são ambas V, se pelo menos uma delas for F, p  q é F 
 
 
TABELA VERDADE: 
 
p q p  q 
V V V 
V F F 
F V F 
F F F 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
2 
 
DISJUNÇÃO () 
p  q é a disjunção de p e q 
 
 
 
POSTULADO: 
 
p  q é V se ao menos um delas é V, se ambas forem F, p  q é F 
 
 
 
TABELA VERDADE: 
 
 
 
 
 
 
 
CONDICIONAIS 
se...então... (→) 
p → q: se p então q 
 
 p é condição necessária para q 
 q é condição suficiente para p 
 
 
 
POSTULADO: 
 
p → q é F somente quando p é V e q é F, caso contrário p → q é V 
 
 
 
TABELA VERDADE: 
 
 
 
p q p → q 
V V V 
V F F 
F V V 
F F V 
 
p q p  q 
V V V 
V F V 
F V V 
F F F 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
3 
 
... se e somente se ... (↔) 
p ↔ q: p se e somente se q 
 
 p é condição necessária e suficiente para q 
 q é condição necessária e suficiente para p 
 se p então q e reciprocamente 
 
 
 
POSTULADO: 
 
p ↔ q é V somente quando p e q são ambas V ou ambas F, caso 
contrário p ↔ q é F 
 
 
 
TABELA VERDADE: 
 
p q p ↔ q 
V V V 
V F F 
F V F 
F F V 
PROPOSIÇOES LOGICAMENTE VERDADEIRAS E LOGICAMENTE FALSAS 
TAUTOLOGIAS 
Seja v uma proposição formada a partir de outras (p,q,r,...). A proposição v é uma TAUTOLOGIA ou PROPOSIÇÃO 
LOGICAMENTE VERDADEIRA se seu valor lógico é V, independentemente dos valores lógicos de (p,q,r,...). 
 
EXEMPLO: (p  ~p) → (q  p) 
 
p q ~p p  ~p q  p (p  ~p) → (q  p) 
V V F F V V 
V F F F V V 
F V V F V V 
F F V F F V 
CONTRADIÇÕES 
Seja f uma proposição formada a partir de outras (p,q,r,...). A proposição f é uma CONTRADIÇÃO ou LOGICAMENTE FALSA se 
seu valor lógico é F, independentemente dos valores lógicos de (p,q,r,...). 
 
EXEMPLO: p  ~p 
 
 
p ~p p  ~p 
V F F 
F V F 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
4 
 
RELAÇÕES 
RELAÇÃO DE IMPLICAÇÃO () 
“ p implica q “, ou p  q quando na tabela verdade de p e q não ocorre VF em nenhuma linha, ou seja, não se tem p V e q V 
simultaneamente. , conclui-se então, que: 
 
p  q quando p → q é V 
RELAÇÃO DE EQUIVALENCIA () 
“ p é equivalente a q “, ou p  q quando na tabela verdade de p e q têm tabelas verdades iguais, ou seja, quando p e q têm 
sempre o mesmo valor lógico. Conclui-se, então, que: 
 
p  q quando p ↔ q é V 
RESULTADOS IMPORTANTES 
DA CONJUNÇÃO 
 
pqqp 
 
 
)()( rqprqp 
 
 
pvp 
 
 
ffp 
 
 
Obs: v é uma tautologia e f é uma contradição 
DA DISJUNÇÃO 
 
pqqp 
 
 
)()( rqprqp 
 
 
vvp 
 
 
pfp 
 
 
Obs: v é uma tautologia e f é uma contradição 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
5 
 
DA CONJUNÇÃO RELATIVAMENTE À DISJUNÇÃO 
 
)()()( rpqprqp 
 
 
)()()( rpqprqp 
 
 
pqpp  )(
 
 
pqpp  )(
 
DA NEGAÇÃO 
 
pp )(~~
 
 
qpqp ~~)(~ 
 
 
qpqp ~~)(~ 
 
SENTENÇAS ABERTAS 
São aquelas que contêm variáveis e cujo valor lógico depende dessas variáveis. 
 
Exemplo: x+1=7, dependendo do valor de x ela poderá ser V ou F. 
QUANTIFICADORES 
Os quantificadores, aplicados à uma sentença aberta permitem classificá-la como V ou F 
QUANTIFICADOR UNIVERSAL () 
Significado: 
 
 Qualquer que seja 
 Para todo 
 Para cada 
 
)71)((  xx
 esta sentença é F 
QUANTIFICADOR EXISTENCIAL () 
Significado: 
 
 Existe pelo menos um 
 Existe um 
 
)71)((  xx
 esta sentença é V 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
6 
 
Também é utilizado o quantificador existencial  
 
Significado: 
 
 Existe um único 
 Existe só um 
 Existe um e um só 
 Existe apenas um 
 
)71)((  x|x
 esta sentença é V 
)4)(( 2  x|x
 esta sentença é F 
NEGAÇÕES IMPORTANTES 
 A negação de pq (conjunção) é ~p~q , pois ~(pq)~p~q 
 A negação de pq (disjunção) é ~p~q , pois ~(pq)~p~q 
 A negação de p→q é p~q , pois ~(p→q)p~q 
 A negação de (x)(p(x)) é (x)(~p(x)) 
 A negação de (x)(p(x)) é (x)(~p(x)) 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
7 
 
CONJUNTOS 
Na teoria dos conjuntos são consideradas noções primitivas (aceitas sem definição): 
 
 Conjunto 
 Elemento 
 Pertinência entre elemento e conjunto 
 
A noção matemática de conjunto é a mesma da linguagem comum: agrupamento, classe, coleção, etc. 
RELAÇÃO DE PERTINÊNCIA 
Se A é um conjunto e x um elemento que pertence a A então escreve-se 
Ax
, caso contrário escreve-se 
Ax
. 
DESCRIÇÃO DE UM CONJUNTO 
Existem duas maneiras para descrever um conjunto e seus elementos: 
 
 Enumeração – enumeram-se, citam-se ou escrevem-se seus elementos: 
 
}7,5,3,2{A
 
 Propriedade dos elementos – define-se uma propriedade característica P, de seus elementos: 
 
}11{ que do menor positivo primo é xxA 
 
CONJUNTO UNITÁRIO 
É aquele que possui apenas um elemento: 
 
}2{A
 
CONJUNTO VAZIO 
É aquele que não possui elementos, denotado por . Em geral descrito por uma propriedade logicamente falsa: 
 
 }{ xxxA
. 
CONJUNTO UNIVERSO 
Usualmente denotado por U ou  é o conjunto no qual se procura a solução, ou soluções, de um problema específico. Ao se 
descrever um conjunto através de determinada propriedade P, é fundamental definir o conjunto U, que restringirá o espaço de 
busca pelas soluções: 
}{ PxUxA epropriedad a tem
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
8 
 
CONJUNTOS IGUAIS 
Os conjuntos A e B são iguais se todos os elementos de A pertencem a B e, reciprocamente, todo elemento de B pertence a A. 
 
))(( BxAxxBA 
 
SUBCONJUNTO 
Um conjunto A é subconjunto do conjunto B se e somente se todo elemento de A também pertence a B. 
 
))(( BxAxxBA 
 
 
 O símbolo 

 é denominado “sinal de inclusão” 
 A notação 
BA
 indica que “A é subconjunto de B”, “A está contido em B” ou “A é parte de B” 
 A notação 
BA
 indica que “A não está contido em B” 
 Também usa-se 
AB 
 e lê-se “B contém A” 
 
Se A, B e C são conjuntos quaisquer, valem as seguintes propriedades da inclusão: 
 
 
A
 
 
AA 
 (reflexiva) 
 
BAABBA 
 (anti-simétrica) 
 
CACBBA 
 (transitiva) 
CONJUNTO DAS PARTES 
O conjunto das partes de A é aquele formado por todos os subconjuntos de A, e denota-se por 
)(A
 
 
 
)(A
 é um conjuntocujos elementos também são conjuntos, neste caso, se B é subconjunto de A , é correta a notação 
)(AB 
 
 Se A tem n elementos, 
)(A
 tem 2
n
 elementos, isto é, a quantidade de subconjuntos de A é 2
n
, incluindo o conjunto 
vazio 
UNIÃO (REUNIÃO) 
A união de dois conjuntos A e B, denotada por 
BA
 é o conjunto formado pelos elementos que pertencem a A ou a B, isto é, 
pertencem a pelo menos um deles. 
}{ BxAxxBA 
 
 
Se A, B e C são conjuntos quaisquer, valem as seguintes propriedades da união: 
 
AAA 
 (idempotente) 
 
AA 
 (elemento neutro) 
 
ABBA  
 (comutativa) 
 
)()( CBACBA  
 (associativa) 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
9 
 
INTERSEÇÃO 
A interseção de dois conjuntos A e B, denotada por 
BA
 é o conjunto formado pelos elementos que pertencem a A e a B. 
 
}{ BxAxxBA 
 
 
 Se 
BA
 eles são ditos disjuntos, ou exclusivos 
 Se para n conjuntos, 
nAAA ,...,, 21
, tem-se que eles são dois a dois disjuntos, ou seja,
))((  ji AAji 
,eles são 
ditos mutuamente exclusivos 
 
Se A, B e C são conjuntos quaisquer, valem as seguintes propriedades da interseção: 
 
 
AAA 
 (idempotente) 
 
AUA 
 (elemento neutro) 
 
ABBA  
 (comutativa) 
 
)()( CBACBA  
 (associativa) 
PROPRIEDADES ENVOLVENDO UNIÃO E INTERSEÇÃO 
Se A, B e C são conjuntos quaisquer, valem as seguintes propriedades gerais: 
 
 
ABAA )( 
 
 
ABAA )( 
 
 
)()()( CABACBA  
 (distributiva da união em relação à interseção) 
 
)()()( CABACBA  
 (distributiva da interseção em relação à união) 
DIFERENÇA 
A diferença entre dois conjuntos A e B, denotada por A-B é dada pelo conjunto formado pelos elementos de A que não pertencem 
a B. 
 
}{ BxAxxBA 
 
DIFERENÇA SIMÉTRICA 
A diferença simétrica entre dois conjuntos A e B, denotada por 
BA
 é dada por: 
 
)()( ABBABA  
 
 
Se A e B são conjuntos quaisquer, valem as seguintes propriedades para a diferença simétrica: 
 
AA 
 
 
AA
 
 
ABBA 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
10 
 
COMPLEMENTAR 
Se A e B são conjuntos com 
BA
, o complementar de A em relação a B, denotado por 
A
BC
, é o conjunto formado pelos 
elementos de B que não pertencem a A, ou seja: 
 
ABC AB 
. 
 
 O complementar de um conjunto A em relação ao conjunto universo U pode ser denotado simplesmente por cA ou A 
 
 
Se A e B são subconjuntos de um conjunto universo U, valem as seguintes propriedades: 
 
 
AA 
 e 
UAA 
 
 
U
 e 
U
 
 
AA 
 
 
BABA  
 
 
BABA  
 
 
Veja que essas propriedades valem para A e B em relação a qualquer outro conjunto que não seja o universo. 
PARTIÇÃO 
Dados os conjuntos 
nAAAA ,...,,, 21
, então 
nAAA ,...,, 21
 formam uma partição de A se: 
 
 
niAi ,...,2,1,  
 
 
AA
n
i
i 


1
 
 
jiAA ji  ,
 
 
Observe que 
nAAA ,...,, 21
 são subconjuntos de A 
PARTIÇÃO ORDENADA 
Chama-se de partição ORDENADA de A a SEQUENCIA de conjuntos 
 nAAA ,...,, 21
 
 
Aqui, 
 nAAAA ...,,, 321
 e 
 nAAAA ...,,, 312
, por exemplo, são partições diferentes. 
PARTIÇÃO NÃO ORDENADA 
Chama-se de partição NÃO ORDENADA de A a FAMÍLIA de conjuntos 
 nAAA ,...,, 21
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
11 
 
Aqui, 
 nAAAA ...,,, 321
 e 
 nAAAA ...,,, 312
, por exemplo, são partições iguais. 
PRINCÍPIO DA INCLUSÃO-EXCLUSÃO 
A quantidade de elementos de um conjunto A será denotada por #A ou n(A). 
 
Dados dois conjuntos, A e B, a quantidade de elementos da união dos mesmos é dada por: 
 
)()()()( BAnBnAnBAn  
 
Verificação 
 
y = quantidade de elementos que pertencem a A e B 
x = quantidade de elementos que pertencem só a A 
z = quantidade de elementos que pertencem só a B 
 
então 
 
)()()()()()()()(
)()(
)()(
)(
BAnBnAnyBnAnyBnyyAnzyxBAn
yBnzyzBn
yAnxyxAn
yBAn






 
 
 
Para três conjuntos, tem-se: 
 
)()()()()()()()( CBAnCBnCAnBAnCnBnAnCBAn  
 
 
Verificação 
 
)()()()()()()(
)]}()[()()({)()()()(
)]()[()()()()(
])[()()(])[()()(




BAnCBnCAnBAnCnBnAn
CBCAnCBnCAnBAnCnBnAn
CBCAnCnBAnBnAn
CBAnCnBAnCBAnCBAnCBACBA




 
 
 
Denotando os conjuntos por 
321 ,, AAA
podemos escrever: 
 
)()()()( 321
21
321 AAAnAAAnAAAn
n
ji
ji
n
i
i   

 
 
Por indução finita prova-se que, para n conjuntos 
nAAA ,...,, 21
, tem-se : 
 
       n
n
n
rji
rji
n
ji
ji
n
i
i
n
i
i AAAnAAAnAAnAnAn  ...1...)( 211
3211









 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
12 
 
ANÁLISE COMBINATÓRIA 
PRINCÍPIO FUNDAMENTAL DA CONTAGEM 
LEMA 1: 
 
Dados os conjuntos 
},...,,{ 21 maaaA 
 e 
},...,,{ 21 nbbbB 
, a quantidade de pares ordenados 
BxAxxx  2121 ,),,(
 é dada 
por: 
 
 
 
 
 
 
nm
 
 
 
 
 
 
 
LEMA 2: 
 
Dado o conjunto 
},...,,{ 21 maaaA 
, a quantidade de pares ordenados 
212121 ,,),,( xxAxAxxx 
 é dada por: 
 
 
 
 
 
 
 
)1(  mm
 
 
 
 
 
 
 
PRINCÍPIO FUNDAMENTAL-PARTE 1: 
 
Dados os conjuntos 
 
},...,,{
...
},...,,{
},...,,{
)()(
2
)(
1
)2()2(
2
)2(
12
)1()1(
2
)1(
11
2
1
r
n
rr
r
n
n
r
aaaA
aaaA
aaaA



 
 
A quantidade de r-uplas ORDENADAS 
rrr AxAxAxxxx  ,...,,),,...,,( 221121
 é dada por: 
 
rnnn  ...21
 
 
 
 
 
a
1
a
2
 a
1
a
3
 ... a
1
a
m
 
a
2
a
1
 a
2
a
3
 ... a
2
a
m
 
... 
a
m
a
1
 a
m
a
2
 ... a
m
a
m-1
 
 
m linhas e (m-1) colunas 
 
total = mx(m-1) elementos 
 
a
1
b
1
 a
1
b
2
 ... a
1
b
n
 
a
2
b
1
 a
2
b
2
 ... a
2
b
n
 
... 
a
m
b
1
 a
m
b
2
 ... a
m
b
n
 
 
m linhas e n colunas 
 
total = mxn elementos 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
13 
 
PRINCÍPIO FUNDAMENTAL-PARTE 2: 
 
Dado o conjunto 
},...,,{ 21 maaaA 
 
A quantidade de r-uplas ORDENADAS 
rjijixxAxxxx jiir ,...,2,1,;;;);,...,,( 21 
 é dada por: 
 
)]1([...)2()1(  rmmmm
 
PERMUTAÇÕES 
Quantidade de maneiras que se pode ordenar um conjunto de elementos. 
PERMUTAÇÕES SIMPLES 
Quantidade de maneiras que se pode ordenar n elementos distintos: 
naaa ,...,, 21
 
 
Corresponde à quantidade de n-upulas ordenadas que se podem formar a partir do conjunto 
},...,,{ 21 naaa
. Pelo Princípio 
Fundamental da Contagem-Parte 2 temos: 
 
1)...2)(1()1)...(2)(1(  nnnnnnnnPn
 
 
Então: 
 
!nPn 
 
 
nn  ...21!
 
 
1!1 
 
 
1!0 
 
 
 
EXEMPLO 
 
Determinar a quantidade de todas as ordenações possíveis dos números 1,2 e 3. 
 
1,2,3 ; 1,3,2 ; 2,1,3 ; 2,3,1; 3,1,2 ; 3,2,1 
 
6321!33 P
 
PERMUTAÇÕES CAÓTICAS 
Quantidade de permutações dos elementos
),...,,( 21 naaa
nas quais nenhum deles ocupa sua posição original. 
 




n
i
i
n
i
nD
0 !
)1(
!
 ou D
n
 = inteiro mais próximo de 
e
n!
 
 
OBS: a verificação deste resultado será vista na seção sobre o Princípio da Inclusão Exclusão. 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
14 
 
EXEMPLO 
 
Determinar a quantidade de permutações caóticas dos números 1,2 e 3. 
 
2,3,1 ; 3,1,2 
 
2
6
2
6
6
1
2
1
1
1
1
1
6
!3
)1(
!2
)1(
!1
)1(
!0
)1(
6
!
)1(
!3
3
0
3210
3 










 








 
i
i
i
D
 
Ou 
 
2...2,2
!3
3  D
e
 
PERMUTAÇÕES DE ELEMENTOS REPETIDOS 
Quantidade de maneiras como se pode ordenar n elementos, nem todos distintos. 
 
As permutações possíveis dos n elementos é dada por n! mas, com isto, os elementos de um mesmo tipo também estão sendo 
permutados, n
j
! vezes cada tipo, sem necessidade. Desta forma, é necessário eliminar estas permutações, dividindo-se o total 
geral de permutações pela quantidade de permutações realizadas para cada tipo de elemento: 
 
nnnn
aaaaaaaaa
k
n
kkk
nn k
 ...
,...,,...,,...,,,...
21
222111
21
 
 
!!...!
!
21
,...,, 21
k
nnn
n
nnn
n
P k 
 
 
 
EXEMPLO 
 
Determinar a quantidade de anagramas que podem ser formados com a palavra ANA 
 
ANA , AAN , NAA 
 
3
121
321
!1!2
!31,2
3 


P
 
PERMUTAÇÕES CIRCULARES 
Quantidade de maneiras como se pode colocar n elementos distintos, 
naaa ,...,, 21
, em n lugares (equiespaçados) em torno de um 
círculo, considerando-se equivalentes as disposições que possam coincidir por rotação. 
 
Se disposições obtidas por rotação não fossem consideradas equivalentes, teríamos n! disposições possíveis mas, considerando a 
equivalência, cada permutação circular é contada n vezes, de tal forma que:
)!1(
!
 n
n
n
PCn
 
 
Então: 
 
1)!1(  nn PnPC
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
15 
 
EXEMPLO 
 
Determinar a quantidade de maneiras que se pode dispor 4 pessoas em uma mesa redonda. 
 
 
 
6!34 PC
 
ARRANJOS 
Quantidade de subgrupos ORDENADOS, com k elementos, que podem ser formados a partir de um grupo com n elementos 
distintos. 
ARRANJOS SIMPLES 
Quantidade de subgrupos ORDENADOS, com k elementos, NÃO REPETIDOS, que podem ser formados a partir de um grupo com 
n elementos distintos. 
 
Pelo Principio Fundamental da Contagem-Parte 2 temos: 
 
)!(
!
1.2.3)...1)((
1.2.3)...1)()(1)...(2)(1()1)...(2)(1(
1.2.3)...1)((
1.2.3)...1)((
)1)...(2)(1()1)...(2)(1(
)1)...(2)(1()1)...(2)(1(,
kn
n
knkn
knknknnnnknnnn
knkn
knkn
knnnnknnnn
knnnnknnnnA kn










 
 
Então: 
 
)!(
!
,
kn
n
A kn


 
 
EXEMPLO 
 
Dado o conjunto {a1,a2,a3}, os subgrupos ordenados com 2 elementos não repetidos que podem ser formados são: 
 
6
)!23(
!3
),(),,(),,(),,(),,(),,(
2,3
233213311221


A
aaaaaaaaaaaa
 
ARRANJOS COM REPETIÇÃO (COMPLETOS) 
Quantidade de subgrupos ORDENADOS, com k elementos, REPETIDOS OU NÃO, que podem ser formados a partir de um grupo 
com n elementos distintos. 
 
Considerando-se k conjuntos iguais, pelo Princípio Fundamental da Contagem-Parte 1, temos: 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
16 
 
k
k
kn
nk
n
n
nnnnnA
aaaA
aaaA
aaaA





.
21
212
211
},...,,{
...
},...,,{
},...,,{
 
 
Então: 
 
 
k
kn nA 

,
 
 
 
EXEMPLO 
 
Dado o conjunto {a1,a2,a3}, os subgrupos ordenados com 2 elementos, com repetição, que podem ser formados são: 
 
93
),(),,(),,(),,(),,(),,(),,(),,(),,(
2*
2,3
332313322212312111
A
aaaaaaaaaaaaaaaaaa 
COMBINAÇÕES 
Quantidade de subgrupos NÃO ORDENADOS, com k elementos, que podem ser formados a partir de um grupo com n elementos 
distintos. 
COMBINAÇÕES SIMPLES 
Quantidade de subgrupos NÃO ORDENADOS, com k elementos, NÃO REPETIDOS, que podem ser formados a partir de um grupo 
com n elementos distintos. 
 
Se os subgrupos fossem ORDENADOS, a quantidade deles seria dada por 
knA ,
, com cada subgrupo formado pelos mesmos 
sendo contado k! vezes (ordens possíveis). Portando para eliminarmos esses casos, devemos dividir 
knA ,
por k!: 
 
)!(!
!
!
)!(
!
!
,
,
knk
n
k
kn
n
k
A
C
kn
kn




 
 
 
Então: 
 
)!(!
!
,
knk
n
C kn


 
 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
17 
 
EXEMPLO 
 
 
Dado o conjunto {a1,a2,a3}, os subgrupos não ordenados com 2 elementos não repetidos que podem ser formados são: 
 
3
)!23(!2
!3
},{},,{},,{
2,3
323121


C
aaaaaa
 
COMBINAÇÕES COM REPETIÇÃO (COMPLETAS) 
Quantidade de subgrupos NÃO ORDENADOS, com k elementos, REPETIDOS OU NÃO, que podem ser formados a partir de um 
grupo com n elementos distintos. 
 
Considere os elementos 
nxxx ,...,, 21
. Determinar a quantidade de subgrupos com k elementos não ordenados que podem ser 
formados com os mesmos, equivale a encontrar todas as soluções possíveis, inteiras não negativas, da equaçao 
kxxx n  ...21
, onde o valor x
i
 na solução é equivalente à quantidade de vezes que o elemento x
i
 aparece no subgrupo 
com k elementos, o que pode ser visto no esquema abaixo. 
 
 
 
 
 
 
A quantidade de símbolos abaixo de x
i
 representa o seu valor na solução da equação, que é equivalente à quantidade de vezes 
que x
i
 aparece no subgrupo com k elementos, veja que essa quantidade varia de 0 a k. Então, ao todo, são k símbolos desse tipo. 
 
O símbolo faz a divisão dos símbolos entre os elementos x
i
. Ao todo são n-1 símbolos do tipo . 
 
Portanto, cada permutação desses dois tipos de símbolo é uma solução possível da equação e corresponde a um subgrupo 
possível com k elementos. Assim, a quantidade procurada de subgrupos com k elementos que podem ser formados a partir de n 
elementos é dada pela seguinte permutação dos k+(n-1) símbolos, sendo k de um tipo e n-1 de outro (permutação de elementos 
nem todos distintos): 
n
kn
nk
nkkn CPC 1
1,
)1(, 


 
 
 
 
Então 
 
kknkn CC ,1
*
, 
 
 
 
EXEMPLO 
 
Dado o conjunto {a1,a2,a3}, os subgrupos não ordenados com 2 elementos, com repetição, que podem ser formados são: 
 
 
6
)!24(!2
!4
},{},,{},,{},,{},,{},,{
2,42,123
*
2,3
333222312111


  CCC
aaaaaaaaaaaa
 
 
 
 
 
x
1 
x
2 
x
3 
x
n-1 
x
n 
. . . ... ... ... ... ... 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
18 
 
PRINCÍPIO DA INCLUSÃO-EXCLUSÃO (EXTENSÃO) 
Na seção sobre conjuntos o princípio da inclusão-exclusão foi utilizadopara determinar a quantidade de elementos da união de n 
conjuntos. Aqui, serão apresentados mais dois resultados importantes. 
 
Sejam um conjunto U e 
nAAAA ,...,,, 321
 subconjuntos de U e as seguintes somas: 
 
...
)(
)(
)(
)(
3
3
2
2
1
1
0










n
kji
kji
n
ji
ji
n
i
i
AAAnS
AAnS
AnS
UnS


 
 
OBS: Existem 
1,nC
 parcelas em S1, 
2,nC
 em S2, 
3,nC
 em S3 e assim por diante. 
 
Assim, temos: 
 
a) O número de elementos de U que pertencem a exatamente p (p≤n) dos conjuntos 
nAAAA ,...,,, 321
 é 




pn
k
kpkkp
k
p SCa
0
,)1(
 
b) O número de elementos de U que pertencem a pelo menos p (p≤n) dos conjuntos 
nAAAA ,...,,, 321
 é 




pn
k
kpkkp
k
p SCb
0
,1)1(
 
c) O número de elementos do conjunto 
nAAAA  ...321
 é 
n
n SSS 121 )1(...

 
DETERMINAÇÃO DA QUANTIDADE DE PERMUTAÇÕES CAÓTICAS 
Sejam os elementos 
nxxx ,...,, 21
. 
 
Seja U o conjunto de todas as permutações dos elementos 
nxxx ,...,, 21
. 
 
Seja A
i
 o conjunto das permutações de 
nxxx ,...,, 21
em que o elemento x
i
 ocupa a posição i (sua posição original), i{1,2,...,n}. 
 
Então, temos que determinar a quantidade de elementos de U que pertencem a exatamente ZERO (nenhum) dos conjuntos 
nAAA ,...,, 21
. 
 
 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
19 
 
Temos, pelo princípio da inclusão/exclusão: 
 
!)(0 nUnS 
 , todas as permutações possíveis de 
nxxx ,...,, 21
 
!)!1()!1()(
11
1 nnnnAnS
n
i
n
i
i  

 
 
!2
!
)!2()!2()( 2,
11
2
n
nCnAAnS n
njinji
ji  

 
!3
!
)!3()!3()( 3,
11
3
n
nCnAAAnS n
nkjinkji
kji  

 
... 
!
!
1
n
n
Sn 
 
 













 


n
k
kn
n
n
n
n
k
k
k
n
k
kkk
k
n
k
kkk
k
kn
n
n
nnn
nn
SSSSSSSCSCa
0
3210
00
,
0
0
00,0
!
)1(
!
)1(
...
!3
1
!2
1
!1
1
!0
1
!
!
!
)1(...
!3
!
!2
!
!!
)1()1()1()1(
 
 
Então 
 




n
k
k
n
k
D
0 !
)1(
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
20 
 
 
NÚMEROS BINOMIAIS 
Para qualquer n real e p inteiro não-negativo, o BINOMIAL de n sobre p é definido por: 
 
1
0
0
!
)1(...)2()1(











 np
p
pnnnnn
p
 ecom
 
 
 
 Se n é inteiro não-negativo, 
pn
Cn
p ,






 
 
 
BINÔMIO DE NEWTON 
TEOREMA BINOMIAL 
O desenvolvimento de 
nax )( 
 é dado por: 
 
         
RaxNn
axaaxaxxax
n
p
ppnn
p
nn
n
nnnnnnn

 


,;
...)(
0
22
2
11
10 
 
 O números 





 n
p
 são chamados de COEFICIENTES BINOMIAIS, onde n é o numerador e p o denominador 
 O Teorema Binomial também é válido para 
nax )( 
, basta escrever como 
nax )]([ 
 
 O termo 
  ppnnp ax 
 é chamado de TERMO GERAL. Como 
np ,...,2,1,0
, o desenvolvimento tem n+1 termos, 
então, para encontrar o (k+1)-ésimo termo faz-se p=k: 
  kknnkk axT  1
 
POLINÔMIO DE LEIBNIZ (GENERALIZAÇÃO DO BINÔMIO DE NEWTON) 
Nnnn
xxx
nnn
n
xxx
p
nnnn
n
p
nn
p
n
p
p
p

 

,...,,
...
!!...!
!
)...(
21
...
21
21
21
21
21
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
21 
 
TRIÂNGULO DE PASCAL 
O Triangulo de Pascal é dado pelo quadro abaixo. 
 
 
   
     
       
         
...
0
0
4
4
4
3
4
2
4
1
4
0
3
3
3
2
3
1
3
0
2
2
2
1
2
0
1
1
1
0
 
 
 
 
 = 
...
14641
1331
121
11
1
 
 
 
 
 
 
 Iniciando a contagem das linhas e colunas a partir de ZERO, a n-ésima linha do Triângulo de Pascal é composta pelos 
coeficientes binomiais de 
nax )( 
, 
 np
 
RELAÇÃO DE STIFEL 
Somando dois elementos consecutivos de uma mesma linha obtem-se o elemento situado abaixo da última parcela da soma: 
 
 
 
 
 
 





















1
1
1 p
n
p
n
p
n 
 
 
 
 
 
PROVA: 
 
Aplicando a definição do Binomial de n sobre p, temos 
 
 




 













































1
1
)!1(
)1)...(1()1(
)1(!
)1)...(1()1(
1
1
!
)1)...(1(
1
1
!
)1)...(1(
)1(!
))(1)...(1(
!
)1)...(1(
)!1(
))(1)...(1(
!
)1)...(1(
)!1(
]1)1()[1)...(1(
!
)1)...(1(
1
n
p
p
pnnnn
pp
pnnnn
p
n
p
pnnn
p
pn
p
pnnn
pp
pnpnnn
p
pnnn
p
pnpnnn
p
pnnn
p
pnpnnn
p
pnnnn
p
n
p
 
 
 
 
 
 
1 
 1 1 
 1 2 1 
 
 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
22 
 
COMBINAÇÕES COMPLEMENTARES 
Em uma mesma linha, elementos equidistantes dos extremos são iguais: 
 
 
 
 
 













pn
n
p
n 
 
 
 
 
 
 
 
PROVA: 
 
 
















 p
n
ppn
n
pnnpn
n
pn
n
!)!(
!
)!([)!(
! 
 
TEOREMA DAS LINHAS 
A soma dos elementos da linha n é igual a 2
n
 : 
 
 
 
 
 
n
n
nnn
2...
10


















 
 
 
 
 
 
 
 
PROVA: 
 
 
Aplicando o desenvolvimento do Binômio de Newton, temos 
 
 
 
































n
k
n
k
kknnn
n
nnn
k
n
k
n
0 0
...
10
11)11(2
 
 
 
 
 
 
 
1 
 1 1 
 1 2 1 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 
1 
 1 1 
 1 2 1 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 
1+4+6+4+1=16=2
4 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
23 
 
TEOREMA DAS COLUNAS 
A soma de elementos consecutivos de uma coluna, iniciando no primeiro elemento da coluna, é igual ao elemento que está 
avançado uma linha e uma coluna em relação ao último elemento da soma: 
 
 
 
 
 
 
 













 





 





 






1
1
...
21
p
kp
p
kp
p
p
p
p
p
pOBS: k+1 é quantidade de parcelas da soma 
 
PROVA: 
 
Aplicando a reação de Stifel para os elementos da coluna p+1, temos 
 





 





 











 





 














































 





















 





















 





















 






































p
kp
p
p
p
p
p
kp
p
p
p
p
p
p
p
kp
p
kp
p
kp
p
kp
p
kp
p
kp
p
kp
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
 
 
 
 
 
 
 
 
...
1
...
1
11
1
11
1
1
1
1
1
...
2
1
2
1
3
1
1
1
1
2
11
1
0

 
TEOREMA DAS DIAGONAIS 
A soma dos elementos de uma diagonal (paralela à hipotenusa), começando no primeiro elemento da diagonal, é igual ao elemento 
que está imediatamente abaixo da última parcela da soma: 
 
 
 
 
 
 





 





 





 





 






p
pn
p
pnnnn
 
1
...
2
2
1
1
0
 
 
 
 
 
 
 
 
1 
 1 1 
 1 2 1 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 
1 
 1 1 
 1 2 1 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
24 
 
PROVA: 
 
 
  
arescomplement scombinaçõecolunas das teoremaarescomplement scombinaçõe
 





 













 





 





 











 





 





 






p
pn
n
pn
n
pn
n
n
n
n
n
n
p
pnnnn 1
1
1
...
21
...
2
2
1
1
0
 
TEOREMA 
Na primeira metade da linha seus elementos estão em ordem crescente e em ordem decrescente na segunda metade: 
 
 
2
1
1
2
1
1




























n
p
p
n
p
n
n
p
p
n
p
n
 
 
 
 
se
se
 
 
PROVA: 
 
 




























































































2
1
1
2
1
1
02120
1
02120
1
)0)!(,0)!1(,0!(
)!()!1(
)21(!
)!()!1(
)1(!)(!
)!(!
!
)!1()!1(
!
1
n
p
p
n
p
n
n
p
p
n
p
n
p
p
n
p
n
p
p
n
p
n
pnpn
pnp
pnn
pnp
pnpnn
pnp
n
pnp
n
p
n
p
n
 
 
 
 
 
 
 
 
 
se
se
se
se
 
FÓRMULA DE EULER 





 


















































p
nnn
p
n
p
nn
p
nn
p
nn
 
 2121212121
0
...
22110
 
 
PROVA: 
 
Seja um grupo com n
1
 elementos do tipo 1 e n
2
 do tipo 2. 
A quantidade de grupos com p elementos que podem ser formados é 





 
p
nn
 
21
 
 
A quantidade de grupos com exatamente k elementos do tipo 1 e p-k do tipo 2 é 
pk
kp
n
k
n
,...,2,1,0,
21












 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
25 
 
Então 




















  p
k kp
n
k
n
p
nn
0
2121 
 
 
FÓRMULA DE LAGRANGE 






























n
n
n
nnnn
 
2
...
210
2222 
 
 
PROVA: 
 
Fazendo n=p=n
1
=n
2
 e aplicando a Fórmula de Euler, temos 
 
 














































































































































n
n
n
nnnn
p
n
n
n
n
nnnnnnn
n
nn
n
n
n
nn
n
nn
n
nn
 
 
 
 
 
ares)complement es(combinaçõ
2
...
210
2
...
221100
2
0
...
22110
2222
 
 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
26 
 
EXERCÍCIOS – LÓGICA 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
27 
 
EXERCÍCIOS – CONJUNTOS 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
28 
 
EXERCÍCIOS – ANÁLISE COMBINATÓRIA 
 
1) Quantos números de quatro dígitos são maiores que 2.400 e: 
 
a) Têm todos os dígitos diferentes 
b) Não têm dígitos iguais a 3,5 ou 6 
c) Têm as propriedades (a) e (b) simultaneamente 
 
2) O conjunto A possui 4 elementos e o conjunto B possui 7 elementos. Quantas são as funções f:A→B? Quantas são as funções 
INJETORAS f:A→B? 
 
3) Quantos divisores naturais possui o número 360? Quantos são pares? 
 
4) Escrevem-se os inteiros de 1 até 222.222. Quantas vezes o algarismo 0 é escrito ? 
 
5) Dispõe-se de n cores diferentes para colorir um mapa com 4 países, cada país com uma cor, distinta ou não de outro país, 
sendo que países com uma linha fronteira comum devem ter cores distintas. Determinar de quantas maneiras cada um dos 
mapas abaixo pode ser colorido e qual o menor valor de n que permite colorir o mapa. 
 
 
MAPA 1 MAPA 2 
 
6) Permutam-se de todos os modos possíveis os algarismos 1,2,4,6 e 7 e escrevem-se os números assim formados em ordem 
crescente. 
 
a) Que lugar ocupa o número 62.417? 
b) Qualo número que ocupa o 66o lugar? 
c) Qual o 200o algarismo escrito? 
d) Qual a soma dos números assim formados? 
 
7) Quantos dados podemos formar numerando as faces de um cubo com os números 1,2,3,4,5 e 6, nas seguintes situações: 
 
a) As faces do cubo são distinguíveis como, por exemplo,cada uma com uma cor diferente 
b) As faces não são distinguíveis 
c) Responda o item (b) para um dodecaedro regular 
 
8) Quantas são as permutações simples dos números 1,2,...,n nas quais o elemento que ocupa a k-ésima posição é inferior a k+4, 
para todo k ? 
 
9) Quantas diagonais tem um polígono com n lados? E um poliedro convexo com n faces ? 
 
10) Tem-se 5 pontos sobre uma reta R e 8 pontos sobre uma reta S paralela a R. Quantos quadriláteros convexos com vértices em 
4 desses 13 pontos existem ? 
 
11) De quantas maneiras podemos colocar 10 pessoas em salas (A,B e C) de modo que em A fiquem 4 pessoas, em B fiquem 3 
pessoas e em C também fiquem 3 pessoas ? 
 
12) De quantos modos é possível dividir 20 pessoas em: 
 
a) Em dois grupos de 10 ? 
b) Em quatro grupos de 5 ? 
c) Em um grupo de 12 e um de 8 ? 
d) Em 3 grupos de 2 e dois de 7 ? 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
29 
 
 
13) O conjunto A possui p elementos e o conjunto B possui n elementos. Determine o número de funções sobrejetoras para: 
 
a) p=n 
b) p=n+1 
 
14) Uma partícula, estando no ponto (x,y), pode mover-se para o ponto (x+1,y) ou para o ponto (x,y+1). Quantos são os caminhos 
que a partícula pode tomar para, partindo do ponto (0,0) chegar ao ponto (a,b), onde a>0 e b>0 ? Se a partícula estiver em 
(x,y,z) ela pode mover-se para (x+1,y,z), (x,y+1,z) ou (x,y,z+1). Quantos são os caminhos, partindo do ponto (0,0,0) que ela pode 
tomar para chegar ao ponto (a,b,c), a>0, b>0, c>0 ? 
 
15) Quantas são as soluções inteiras não negativas de: 
 
a) 
20654321  xxxxxx
 
b) 
20654321  xxxxxx
 
c) 
20654321  xxxxxx
 
d) 
20654321  xxxxxx
, onde 
6,5,4,3,2,1,2  ixi
 
e) 
20654321  xxxxxx
, onde exatamente 3 incógnitas são nulas 
f) 
20654321  xxxxxx
, onde pelo menos 3 incógnitas são nulas 
 
 
16) Quantos são os inteiros compreendidos entre 1 e 1000, inclusive, que são divisíveis por exatamente 2 dos números 2,3,7 e 10? 
E por pelo menos 2 ? 
 
17) Se n(A)=n e n(B)=p (np), quantas são as funções f:A→B sobrejetoras ? 
 
18) Seja um conjunto A, com n(A)=n. Quantas são as funções f:A→A para as quais f(x)=x não tem solução? Dessas, quantas são 
bijetoras ? 
 
19) Dois médicos devem examinar, durante uma mesma hora, 6 pacientes, gastando 10 min com cada um. Cada um dos 6 
pacientes deve ser examinado pelos dois médicos. De quantos modos pode ser feito um horário compatível ? 
 
20) Considere uma população com N elementos distintos, dos quais N
1
 são do tipo 1, N
2
 do tipo 2,...,N
k
 do tipo k, com 
N
1
+N
2
+...+N
k
=N. Será retirada uma amostra de n elementos dessa população. Se S é conjunto de todas as amostras possíveis 
de serem retiradas e A o conjunto das amostras que têm exatamente n
1
 elementos do tipo 1, n
2
 do tipo 2,...,n
k 
do tipo k, com 
n
1
+n
2
+...+n
k
=n, determine n(S) e n(A) nas seguintes condições: 
 
a) Amostra ordenada sem reposição 
b) Amostra ordenada com reposição 
c) Amostra não ordenada sem reposição 
d) Amostra não ordenada com reposição 
 
21) Considere um conjunto com n objetos para serem distribuídos em N urnas numeradas. De quantas maneiras eles podem ser 
distribuídos, nas seguintes condições: 
 
a) Objetos distinguíveis, com exclusão 
b) Objetos distinguíveis, sem exclusão 
c) Objetos não distinguíveis, com exclusão 
d) Objetos não distinguíveis, sem exclusão 
 
OBS: COM EXCLUSÃO significa que uma urna pode NÃO RECEBER objetos ou receber APENAS UM objeto, SEM 
EXCLUSÃO significa que uma urna pode NÃO RECEBER objetos ou receber PELO MENOS UM objeto 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
30 
 
EXERCÍCIOS – BINÔMIO DE NEWTON 
 
 
1) Determine o coeficiente de x
2
 no desenvolvimento de 9
2
3 1







x
x
 
 
2) Determine o termo máximo do desenvolvimento de 65
3
1
1 






 
 
3) Calcule 


n
k
k
knkC
0
, 3
 
 
4) Calcule a soma dos coeficientes dos termos de ordem par do desenvolvimento de 
nyx )32( 2 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
31 
 
EXERCÍCIOS – TRIÂNGULO DE PASCAL 
 
 
1) Todo polinômio P(x) de grau p pode ser escrito da forma 
)1)...(1(...)1(210  pxxxaxxaxaa p
. Calcule 
as seguintes somas: 
 
a) 
)1(...)1(...)2(...43)1(...32...21  npnnpppS
 
b) 
222 ...321
2
nS 
 
c) 
333 ...321
3
nS 
 
 
2) Determine p para que: 
 
a) 
pC ,10
 seja máximo 
b) 
pC ,21
 seja máximo 
 
 
3) O número de Fibonacci, F
n
 é definido com a soma dos elementos da n-ésima “diagonal inversa” do Triângulo de Pascal. Prove 
que F
n+2
=F
n+1
+F
n
. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4) Seja A o conjunto {1,2,...,n} e p um natural tal que 1<p<n 
 
a) Quantos são os p-subconjuntos de A nos quais o elemento mínimo é igual a k ? 
 
b) Formados todos os p-subconjuntos de A, em cada um deles considera-se o elemento mínimo do subconjunto. Quanto vale 
a média aritmética desses mínimos ? 
 
 
5) Resolva as seguintes equações: 
 
a) 
12,41,41  pp CC
 
 
b) 
pppp CC   9,152,15
 
 
6) Prove que em cada coluna (exceto a coluna 0) os elementos do Triângulo de Pascal estão em ordem crescente. 
 
 
 
1 
 F0=1 1 1 
 F1=1 1 2 1 
 F2=2 1 3 3 1 
 F3=3 1 4 6 4 1 
 F4=5 1 5 10 10 5 1 
 F5=8 1 6 15 20 15 6 1 
F6=13 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
32 
 
RESPOSTAS DOS EXERCÍCIOS – LÓGICA 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
33 
 
RESPOSTAS DOS EXERCÍCIOS – CONJUNTOS 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
34 
 
RESPOSTAS DOS EXERCÍCIOS – ANÁLISE COMBINATÓRIA 
 
 
EXERCÍCIO 1 
 
a) Não começando por 2: 7 possibilidades para o 1o algarismo; 9 para o 2o; 8 para o 3o e 7 para o 4o = 7987=3.528 
Começando por 2: 1 possibilidade para o 1o algarismo; 6 para o 2o; 8 para o 3o e 7 para o 4o = 1678=336 
Total=3.528+336=3.864 
 
b) Não começando por 2: 4 possibilidades para o 1o algarismo; 7 para o 2o; 7 para o 3o e 7 para o 4o = 4777=1.372 
Começando por 2: 1 possibilidade para o 1o algarismo; 4 para o 2o; 7 para o 3o e 7 para o 4o = (1477)-1=195 obs: deve-se 
retirar o n
o
 2.400 
Total=1.372+195=1.567 
 
c) Não começando por 2: 4 possibilidades para o 1o algarismo; 6 para o 2o; 5 para o 3o e 4 para o 4o = 4654=480 
Começando por 2: 1 possibilidade para o 1o algarismo; 4 para o 2o; 5 para o 3o e 4 para o 4o = 1454=80 
Total=480+80=560 
 
 
EXERCÍCIO 2 
 
FUNÇÕES: 7777=2401 
FUNÇÕES INJETORAS: 7654=840 
 
 
EXERCÍCIO 3 
 
532360 23  
 
DIVISORES: 
24234
}1,0{}2,1,0{}3,2,1,0{532


quantidade
 zyxzyx
 
 
DIVISORES PARES: 
18233
}1,0{}2,1,0{}3,2,1{532


 quantidade
 zyxzyx
 
 
 
EXERCÍCIO 4 
 
0 na casa das unidades: antes do 0=22.222 números (de 1 a 22.222) = 22.222 números 
Casa das dezenas:antes do 0=2.222 números (de 1 a 2.222); depois do 0=10 números (de 0 a 9) 2.22210= 22.220 números 
Casa das centenas: antes do 0=222 números (de 1 a 222); depois do 0=100 números (de 0 a 99) 222100= 22.200 números 
Casa dos milhares: antes do 0=22 números (de 1 a 22); depois do 0=1.000 números (de 0 a 999)221.000 = 22.000 números 
Casa das dezenas de milhares: antes do 0=2 números (de 1 a 2); depois do 0=10.000 números (de 0 a 9.999)210.000=20.000 
números 
Total=22.222+22.220+22.200+22.000+20.000=108.642 
 
 
EXERCÍCIO 5 
 
MAPA 1: 
 
Considerando, inicialmente, que os quadrantes 1 e 4 possam ter a mesma cor, a quantidade de total maneiras de colorir o mapa 
seria: 
3)1()1)(1)(1(  nnnnnn
 
A quantidade de maneiras onde os quadrantes 1 e 4 têm a mesma cor é dada por: 
)2)(1(  nnn
 
Então, a quantidade correta de colorir o mapa é: 
)33)(1()()33)(1()2)(1()1( 223  nnnnnfnnnnnnnnn
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
35 
 
É fácil verificar que são necessárias apenas 2 cores para colorir o mapa, uma cor para os quandrantes ímpares e a outra para os 
quadrantes pares. Analisando f(n), tem-se f(1)=0, f(n)>0 para n2. 
 
 
MAPA 2: 
 
Como todos os países têm fronteira em comum, todos devem ter cores diferentes. Assim a quantidade de maneiras de colorir o 
mapa com as n cores é: 
)3)(2)(1()(  nnnnnf
 
 
É fácil verificar que são necessárias apenas 4 cores para colorir o mapa, uma cor para cada país. Analisando f(n), tem-se 
f(1)=f(2)=f(3)=0, f(n)>0 para n4. 
 
 
EXERCÍCIO 6 
 
a) Quantidade de números antes do 62.471: 
Começados por 1 = 4! = 24 
Começados por 2 = 4! = 24 
Começados por 4 = 4! = 24 
Começados por 61 = 3! = 6 
Começados por 621 =2! = 2 
Total=24+24+24+24+6+2=80  o n
o
 62.471 ocupa o 81
o
 lugar 
 
b) Existem 4! = 24 números começados por 1 
Existem 4! = 24 números começados por 2 
Existem 3! = 6 números começados por 41 
Existem 3! = 6 números começados por 42 
Existem 3! = 6 números começados por 46 
Total=24+24+6+6+6=66 números  o 66o número é o último começado por 46 que é o 46.721 
 
c) Cada número tem 5 algarismos  o 200o algarismo é o último do 40o número 
Existem 4! = 24 números começados por 1 
Existem 3! = 6 números começados por 21 
Existem 3 números começados por 24 
Total=24+6+6=36 números  o 37o número é o primeiro começado por 26 que é o 26.147  o 38o é o 26.174, o 39
o
 é o 26.417 e 
o 40o é o 26.471  o 200o algarismo escrito é o 1. 
 
d) Soma das unidades = (1+2+4+6+7)4!1 = 4801=480 
Soma das dezenas = (1+2+4+6+7)4!10 = 48010=4.800 
Soma das centenas = (1+2+4+6+7)4!100 = 480100=48.000 
Soma dos milhares = (1+2+4+6+7)4!1000 = 4801000=480.000 
Soma das dezenas de milhares = (1+2+4+6+7)4!10.000 = 48010.000=4.800.000 
Soma total = 480+4.800+48.000+480.000+4.800.000=5.333.280 
 
 
EXERCÍCIO 7 
 
 
a) 6! = 720 
 
b) Considerando inicialmente faces distintas tem-se 6!=720 
Eliminando os dados iguais, que se repetem por rotação: 
Modos de escolher a base = 6 
Modos de escolher a face de frente = 4 
Total de rotações para cada base = 6x4=24 
Então, total de dados = 720/24=30 
 
c) São 12 maneiras de se escolher a base e 5 de escolher a face da frente; 
Então, total de dodecaedros = 12!/(12x5)=7.983.360 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
36 
 
EXERCÍCIO 8 
 
O primeiro elemento deve ser inferior a 5  existem 4 maneiras de escolha 
O segundo elemento deve ser inferior a 6  existem 5-1=4 possibilidades (1 já utilizado na posição anterior) 
O terceiro elemento deve ser inferior a 7  existem 6-2=4 possibilidades (2 já utilizados nas posições anteriores) 
... 
O elemento de posição (n-3) deve ser inferior a (n-3)+4=n+1  existem n-(n-4)=4 possibilidades (n-4 já utilizados anteriormente) 
O elemento de posição (n-2) deve ser inferior a (n-2)+4=n+2  existem n-(n-3)=3 possibilidades (n-3 já utilizados anteriormente) 
O elemento de posição (n-1) deve ser inferior a (n-1)+4=n+3  existem n-(n-2)=2 possibilidades (n-2 já utilizados anteriormente) 
O elemento de posição n deve ser inferior a n+4  existem n-(n-1)=1 possibilidade (n-1 já utilizados anteriormente) 
 
Então a quantidade buscada é 4n-3321=64n-3
 
 
 
EXERCÍCIO 9 
 
POLÍGONO 
 
Os segmentos que unem dois vértices do polígono ou são lados ou são diagonais, como existem C
v,2
 (v=quantidade de vértices) 
segmentos dos quais n são lados, então D=C
n,2
-n=n(n-3)/2 (obs: quantidade de vértices=quantidade de lados) 
 
POLIEDRO 
 
 dACD v 2,
, onde v=quantidade de vértices, A= quantidade de arestas e d é a soma das diagonais das faces 
 
EXERCÍCIO 10 
 
Basta selecionar 2 pontos em R e dois pontos em S: 
28028102,82,5 CC
 
 
 
EXERCÍCIO 11 
 
Existem 
4,10C
 maneiras de se colocar 4 pessoas na sala A 
Existem 
3,6C
 maneiras de se colocar 3 pessoas na sala B e 
Existem 
3,3C
 maneiras de se colocar 3 pessoas na sala C 
 
Então, a quantidade desejada é: 
200.4
!0!3
!3
!3!3
!6
!6!4
!10
3,33,64,10  CCC
 
 
EXERCÍCIO 12 
 
2 grupos de 10: 
 
A princípio existem 
10,20C
 maneiras de formarmos o 1o grupo e 
10,10C
 de formarmos o 2o grupo, totalizando 
10,1010,20 CC 
 grupos. 
Mas, cada formação de dois grupos é contada 2!=2 vezes  a quantidade desejada (correta) é 
378.92
!2
10,1010,20

CC
 
 
4 grupos de 5: 
 
Usando o mesmo raciocínio anterior: 
376.864.488
!4
5,55,105,155,20

 CCCC
 
 
1 grupo de 12 e 1 de 8: 
 
como os 2 grupos são de tamanhos diferentes, não há repetições na formação de dois grupos, então a quantidade desejada é: 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
37 
 
970.1258,812,20 CC
 
3 grupos de 2 e 2 de 7: 
 
Na quantidade 
7,77,142,162,182,20 CCCCC 
 os 3 grupos de 2 são contados 3! vezes e os 2 grupos de 7 são contados 2! vezes, 
então a quantidade desejada é: 
 
400.682.997
!2!3
7,77,142,162,182,20 

 CCCCC
 
 
 
 
EXERCÍCIO 13 
 
a) p = n 
 
neste caso f é bijetiva: 
 
a imagem de a
1
 pode ser escolhida de n maneiras 
a imagem de a
2
 pode ser escolhida de n-1 maneiras 
... 
a imagem de a
n
 pode ser escolhida de 1 maneira 
 
então a quantidade desejada é 
!1)...1( nnn 
 
 
b) p=n+1 
 
neste caso dois elementos de A terão a mesma imagem em B e a correspondência entre os demais n-1 elementos de A e os 
demais n-1 elementos de B será bijetiva: 
 
existem 
2,1nC
 maneiras de escolher os dois elementos de A com a mesma imagem em B, n maneiras de escolher esta 
imagem e (n-1)! maneiras se construir uma relação bijetiva entre os n-1 elementos restantes 
 
Então, a quantidade procurada é: 
2
)!1(
)!1(2,1


nn
nnCn
 
 
EXERCÍCIO 14 
 
De (0,0) para (a,b): 
 
A partícula deve mover-se para a direita (D) a vezes e para cima (C) b vezes. Portanto, a quantidade de trajetos é igual à 
permutação das letras D e C, repetidas a e b vezes, respectivamente: 
!!
)!(,
ba
ba
P ba ba


 
 
De (0,0,0) para (a,b,c): 
 
A partícula deve mover-se para a direita (D) a vezes, para a frente (F) b vezes e para cima (C) c vezes. Portanto, a quantidade de 
trajetos é igual à permutação das letras D, F e C repetidas a,b e c vezes, respectivamente: 
!!!
)!(,,
cba
cba
P cba cba


 
 
 
 
 
 
 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
38 
 
 
EXERCÍCIO 15130.53
!5!20
!25
20,2520,6 
 CC a)
 
230.230
!6!20
!26
20
)(20
20
20,2620,7
654321
654321
654321




 CC
fxxxxxx
fxxxxxxf
xxxxxx
 
 
 
 b)
folga de variável
 
 
100.177
!6!19
!25
19
)(19
19
20
19,2519,7
654321
654321
654321
654321





 CC
fxxxxxx
xxxxxxf
xxxxxx
xxxxxx
 
 
 
 
 c)
 
287.1
!5!8
!13
8
2012
20)2(...)2()2(
0,2
2,20
8,138,6
654321
654321
621
654321






 CC
yyyyyy
yyyyyy
yyy
yyx
xxxxxxx
iii
i
 
 
 
 
 
 d)
inteiros e
 
 
 
420.317120
!2!17
!19
!3!3
!6
1720320)1()1()1(
0,,;1,1,1
1,1,1,20
,20
17,193,6
17,1917,3
321321321
321332211
321321
3,6
654321







CC
CC
zzzzzzzzz
zzzzyzyzy
yyyyyy
C
xxxxxx
 
 
 
 
 
 
 
 e)
é solução a
é equação desta soluções de quantidade a
de soluções de quantidade a encontrar ser a passa problema o,incógnitas essas fixadas
nulas incógnitas 3 as escolher se de maneirasexistem
nulas incógnitas 3 exatamente com
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 f)
soluções de Total 
soluçõesnulas incógnitas com
:então valer deve restante a,incógnitas essas fixadas
nulas incógnitas 5 escolher se de maneirasexistem 
soluçõesnulas incógnitas com
é equação desta soluções de quantidade a
temos,incógnitas essas fixadas
nulas incógnitas escolher se de maneirasexistem
soluções nulas incógnitas 3 com 
nulas incógnitas menos pelo com
711.36285420.3
5
20
4
4
420.3
3
61
2851915
1820220)1()1(
0,;1,1
1,1,20
,20
5,6
5,6
18,194,6
18,1918,2
212121
212211
2121
4,6
654321










C
C
CC
CC
zzzzzz
zzzyzy
yyyy
C
xxxxxx
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
39 
 
 
EXERCÍCIO 16 
 
}10|{
}7|{
}3|{
}2|{
}000.11|{
4
3
2
1
xxA
xxA
xxA
xxA
xx
 
 
 
 
divide
divide
divide
divide





 
 
100
10
000.1
)(
142
7
000.1
)(
333
3
000.1
)(
500
2
000.1
)(
000.1)(
4
3
2
1






























An
An
An
An
n
inteira parte 
 
14
70
000.1
)(
33
30
000.1
)(
47
21
000.1
)(
100
10
000.1
)(
71
14
000.1
)(
166
6
000.1
)(
43
42
32
41
31
21










































AAn
AAn
AAn
AAn
AAn
AAn
 
4
744143323
43114334710071166
075.1100142333500
000.1
4
3
2
1
0





S
S
S
S
S
 
2334674343163
)1()1()1(
)1()1()
432
42,4
2
31,3
1
20,2
0
2
0
2,2
24
0
2,22


 





SSS
SCSCSC
SCSCaa
k
kkk
k
k
kkk
k
 
 
 
 
2954374243132
)1()1()1(
)1()1()
432
42,3
2
31,2
1
20,1
0
2
0
2,1
24
0
2,122


 





SSS
SCSCSC
SCSCbb
k
kkk
k
k
kkk
k
 
 
 
 
 
 
EXERCÍCIO 17 
 
O total de funções f:A→B é pn 
 
Chamando os elementos de B de y
1
,y
2
,...,y
p
, as funções não sobrejetoras são as em que y
1
,y
2
,...,y
p
 não pertencem ao Conjunto-
Imagem da função 
 
Chamando de 
),...,2,1( pjAj  
 o conjunto das funções f:A→B em que y
i
 não pertence ao Conjunto-Imagem, as funções não 
sobrejetoras são aquelas que pertencem a 
pAAA  ...21
. 
 
Então, o número de funções sobrejetoras é 
p
pn
p
pn SSSpSSSp )1(...)1(...( 21
1
21 

 
 
A
i
=conjunto das funções onde y
i
Im 
n(A
i
)=quantidade de funções onde y
i
Im 
n
p
n
i pCSpAn )1()1()( 1,1 
 
 
ji AA 
=conjunto das funções onde y
i
,y
j
Im 
)( ji AAn 
=quantidade de funções onde y
i
,y
j
Im 
n
p
n
ji pCSpAAn )2()2()( 2,2 
 
... 
n
ppp ppCS )]1([1,1  
 
n
ppp ppCS )(, 
 
 
Então a quantidade de funções sobrejetoras é 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
40 
 






p
k
n
kp
k
n
pp
Pn
pp
pn
p
n
p
n
kpC
ppCppCpCpCp
0
,
,1,
1
2,1,
)()1(
)()1()]1([)1(...)2()1( 
 
EXERCÍCIO 18 
 
Funções onde f(x)=x não tem solução: 
 
Cada elemento de A pode ter sua imagem escolhida de n-1 modos, então a quantidade desejada é (n-1)
n
. 
 
 
Funções bijetoras onde f(x)=x não tem solução: 
f(x
1
), f(x
2
),...,f(x
n
) deve ser uma permutação caótica de n elementos, então a quantidade desejada é
 





 

!
)1(
...
!1
1
01
1
!
n
nD
n
n
 
 
 
EXERCÍCIO 19 
 
A agenda do primeiro médico pode ser montada de P
6
 = 6! = 720 modos 
A agenda do segundo médico pode ser montada de D
6
 = 265 modos 
Então a quantidade de agendas compatíveis é 720265=190.800 
 
 
 
EXERCÍCIO 20 
 
 
 
 
EXERCÍCIO 21 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
41 
 
RESPOSTAS DOS EXERCÍCIOS – BINÔMIO DE NEWTON 
 
 
EXERCÍCIO 1 
 
 
 
126126
5
9
)1(
52527
9
)1(
)1(919
2255275
6
527327
2
93
21





































 éde ecoeficient o xxxT
kkx
k
x
xk
x
xk
T kkk
k
k
k
k
k
 
 
 
EXERCÍCIO 2 
 
 
1617
65641817161521
1
1
1
1
11
65
1
3
1
16
65
......
65,...,18,17
16,...,2,1
5,161366
!65
!65
3
3
)!1(
!
)!65(
)!66(
3
1
3)!66()!1(
!65
3)!65(!
!65
3
1
1
65
3
165
3
165
1
3
165































































T
TTTTTTTT
kTT
kTT
kkk
k
k
k
k
kkkk
kk
TT
kk
T
kk
kk
k
k
kkk
kkkk
k
k
k
k
 
 
 para 
 para 
 
 
 
 
 
 se 
é máximo termo o
logo
então
 
 
 
EXERCÍCIO 3 
 
11
1
0
,1
1
1
1,1
1
1,1
110
,
43)31(333
333
3
)!()!1(
)!1(
3
)!(!
!
3




















nn
n
p
p
pn
n
k
k
kn
n
k
k
kn
n
k
k
n
k
k
n
k
k
kn
nnCn
CnCn
knk
n
n
knk
n
kkC
 
 
 
 
 
 
 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
42 
 
EXERCÍCIO 4 
 
 
2
5)1(
2
)32()32(
1
2
)32()32(
...
...)(2)32()32(
...)32(
...)32(
22
642
642
22
654321
2
654321
2
nnnn
nn
nn
n
n
yx
yxyx
TTT
TTTyxyx
TTTTTTyx
TTTTTTyx









:é escoeficient dos soma aazendo f 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
43 
 
RESPOSTAS DOS EXERCÍCIOS – TRIÂNGULO DE PASCAL 
 
 
EXERCÍCIO 1 
 













































































 

2
1
)!1(
1
...
1
3
1
2
1
1
)!1(
1
)!1(
1
)!1(
1
)!1()1(...)2()1(
11
p
np
p
p
np
p
p
p
p
p
p
p
p
pk
p
p
pk
pS
p
pk
pkpkkk
n
k
n
k
p
 
 
parcelas 
a)   
 
 
 
 
6
)12)(1(
2
)1(
6
)1)(2(
2
2
1
3
2
2
1
!1
2
1
!2
)1()1(
)1(
0,1,1
0,0,1
)(
)1(
11
111
2
012
0122
012
2
2
2
012
2










 





 












 











nnnnnnnnnn
kk
kkkkkkS
kkkk
aaa
aaaa
akaakak
akakkak
n
k
n
k
n
k
n
k
n
k
 
 
 
 
 
 
 
 
 
 b)
 
 
 
 
 
4
)1(
2
1
3
2
6
4
3
6
1
!1
2
1
!23
3
2
!3
)1(3)2)(1()1(3)2)(1(
)1(3)2)(1(
0,1,3,1
0,02,03,1
)2()3(
)1()2)(1(
22
111
1111
3
0123
0123233
0123
2
23
3
3
3
0123
3






 





 





 












 





 











nnnnn
kkk
kkkkkkkkkkkkS
kkkkkkk
aaaa
aaaaaaa
akaaakaakak
akakkakkkak
n
k
n
k
n
k
n
k
n
k
n
k
n
k
 
 
 
 
 
 
 
 
 
 c)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
LÓGICA - CONJUNTOS - ANÁLISE COMBINATÓRIA Prof. MSc. Francisco de Assis Amaral Bastos 
44 
 
EXERCÍCIO 2 
 
a) Quando n é par, existe apenas um elemento máximo, aquele que ocupa a coluna 
2
n
p 
. Como 
pC ,10
 é elemento da 
linha 10  p=5. 
 
b) Quando n é ímpar, existem dois elementos máximos, aqueles que ocupam as colunas 
2
1

n
p
 e 
1
2
1



n
p
. 
Como 
pC ,21
 é elemento da linha 21  p=10 ou p=11. 
 
 
EXERCÍCIO 3 
 
 
2
1
...
21
1
0
2
...
2
1
1
1
100
1
...
2
2
1
1
0
...
2
1
10
1














 





 












 





 























 












 





 

















 











 

n
nn
F
nnn
nnnnn
nnnnnn
FF
 
 
 
 
 
 
 
 
 
EXERCÍCIO 4 
 
a) Escolhido o elemento de valor k, os outros p-1 elementos do subconjunto devem ser escolhidos entre os n-k elementos de 
A que são maiores do que k, então a quantidade desejada é 
1,  pknC
 
 
1
1)1(
)1(
)1()1()1()1(
,
1,1,
,
1
1
,1,
,
1
1
1,,
,
1
1
1
1
1,1,
1
1
1,
1
1
1,






























 


p
n
C
pCCn
C
pCCn
C
CknCn
C
CnCnk
C
kC
pn
pnpn
pn
pn
k
pknpn
pn
pn
k
pknpn
pn
pn
k
pn
k
pknpkn
pn
k
pkn
pn
k
pkn
 
 b)
 
 
EXERCÍCIO 5 
 
a) 
141411212  pppppp ouou
 
 
b) 
3159292  pppppp ou
 
 
 
EXERCÍCIO 6 
 
01
1
1
,
,1





p
pn
n
C
C
pn
pn
 se