ANÁLISE COMBINATÓRIA

Prévia do material em texto

Francisco de Assis Amaral Bastos 
 
2ª EDIÇÃO – FEV 2014 
 
 
 
 
 
 
 
 
 
 
 
CONJUNTOS 
 
 
 
 
 
 
 
ANÁLISE 
COMBINATÓRIA 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
1 
 
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 domenor 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
. 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
2 
 
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
 
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 conjunto cujos 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 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
3 
 
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) 
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 subconjuntos quaisquer, de um universo U, 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) 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
4 
 
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 
 
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 para o 
complementar: 
 
 
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. 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
5 
 
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
 
 
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 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
6 
 
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
nn
rji
rji
n
ji
ji
n
i
i
n
i
i AAAnAAAnAAnAnAn  ...1...)( 211
3211









 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
7 
 
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
 m linhas e (m-1) colunas 
... total = mx(m-1) elementos 
a
m
a
1
 a
m
a
2
 ... a
m
a
m-1
 
 
 
 
 
a
1
b
1
 a
1
b
2
 ... a
1
b
n
 
a
2
b
1
 a
2
b
2
 ... a
2
b
n
 m linhas e n colunas 
... total = mxn elementos 
a
m
b
1
 a
m
b
2
 ... a
m
b
n
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
8 
 
 
 
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
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
9 
 
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. 
 
 
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 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
10 
 
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
 
 
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. 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
11 
 
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: 
 
k
k
kn
nk
n
n
nnnnnA
aaaA
aaaA
aaaA





.
21
212
211
},...,,{
...
},...,,{
},...,,{
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
12 
 
 
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 elementosdistintos. 
 
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


 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
13 
 
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
*
, 
 
 
 
 
 
x
1 
x
2 
x
3 
x
n-1 
x
n 
. . . ... ... ... ... ... 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
14 
 
EXEMPLO 
 
Dado o conjunto {a
1
,a
2
,a
3
}, 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
 
PRINCÍPIO DA INCLUSÃO-EXCLUSÃO (EXTENSÃO) 
Na seção sobre conjuntos o princípio da inclusão-exclusão foi utilizado para 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(...

 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
15 
 
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
. 
 
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
k
n
n
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
nD
0 !
)1(
!
 
Outra maneira de calcular D
n
: D
n
 é o inteiro mais próximo de 
e
n!
 
 
Veja que o resultado vale para n=1 e n=2, pois D
1
=0 






 ...3,0
!1
e
e D
2
=1 






 ...7,0
!2
e
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
16 
 
Prova para n>2: 
 
...
!3!2!1!0
1 32

xxx
e x
 , portanto 
...
!3
1
!2
1
!1
1
!0
11 1  e
e
 
 
2
2
1!
2
11
1
1
1
1
1
...
)1(
1
)1(
1
1
1
...
)3)(2)(1(
1
)2)(1(
1
1
1
...
)!2(
1
)!1(
1
!...
)!2(
)1(
)!1(
)1(
!
...
)!2(
)1(
)!1(
)1(
!
)1(
...
!3
1
!2
1
!1
1
!0
1
!
!
)1(
...
!1
1
!0
1
!
!
32
21
21




















































 



n
e
n
D
n
n
n
nnn
nnnnnnnn
n
nn
n
nnn
n
n
n
e
n
D
n
nn
nnnn
n
 se
 
Logo, D
n
 é um inteiro situado a uma distância menor que 
2
1
 do número 
e
n!
, ou seja, é o inteiro mais próximo 
de 
e
n!
. 
 
 
 
 
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
17 
 
NÚMEROS BINOMIAIS 
Para qualquer n real e p inteiro não-negativo, o BINOMIAL de n sobre p é definido por: 
 
1
0
 e 0 com 
!
)1(...)2()1(











 np
p
pnnnnn
p
 
 
 
 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
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
18 
 
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 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
19 
 
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=24 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
20 
 
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
 
1 
1
 
...
 
2
 
1
0 p
np
p
kp
p
np
p
np
p
p
p
p
p
p
n
k
 
 
 
OBS: n+1 é quantidade de parcelas (linhas) da soma 
 
 
PROVA: 
 
Aplicando a reação de Stifel para os elementos da coluna p+1, temos 
 
 





 





 











 





 



























 





















 





















 





















 






































p
np
p
p
p
p
p
np
p
p
p
p
p
p
p
np
p
np
p
np
p
np
p
np
p
np
p
np
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
 
...
 
1
 
...
 
1
1
 
1 
1
 11 
1
 
1
1 
1
1
...
 
2
1
2
1
3
 
1
1
1
1
2
1
 
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 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
21 
 
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
k
kn
p
pn
p
pnnnn
p
k 
1
 
 
1
 
...
2 
2
1 
1
0
0
 
 
 
 
PROVA: 
 
 

  
arescomplement scombinaçõecolunas das teorema
arescomplement scombinaçõe
 
1
1 
1
 
 
...
 
2
 
1
 
...
2 
2
1 
1
0





 














 





 





 











 





 





 






p
pn
n
pn
n
pn
n
n
n
n
n
n
p
pnnnn
 
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
 
 
 
 
 
1 
 1 1 
 1 2 1 
 1 3 3 11 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
22 
 
PROVA: 
 
 




























































































2
1
 
1
 
2
1
 
1
 
 
0212 0
1
 
0212 0
1
 
)0)!(,0)!1(,0!(
)21(
)!()!1(
!
)!()!1(
)1(!)(!
)!(!
!
)!1()!1(
!
1
 
se
se
se
se
n
p
p
n
p
n
n
p
p
n
p
n
p
p
n
p
n
p
p
n
p
n
pnpn
pn
pnp
n
pnp
pnpnn
pnp
n
pnp
n
p
n
p
n
 
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












 
Então 




















  p
k kp
n
k
n
p
nn
0
2121 
 
 
 
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
23 
 
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
 
2
...
210
arescomplement scombinaçõe 
 
2
...
221100
 
2
0
...
2
 
21
 
10
2222
)(
 
 
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
24 
 
EXERCÍCIOS – CONJUNTOS 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
25 
 
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) Qual o 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 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
26 
 
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 ? 
 
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 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
27 
 
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 
detodas 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 n1+n2+...+nk=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 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
28 
 
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 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
29 
 
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 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
. 
 
 0 1 2 3 4 5 6 
 
 
 
 
 
 
 
 
 
 
 
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 ? 
 
 
 
 
 
 
 
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 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
30 
 
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. 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
31 
 
SOLUÇÃO DOS EXERCÍCIOS – CONJUNTOS 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
32 
 
SOLUÇÃO 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 1
o
 algarismo; 6 para o 2
o
; 8 para o 3
o
 e 7 para o 4
o
 = 
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 1
o
 algarismo; 4 para o 2
o
; 7 para o 3
o
 e 7 para o 4
o
 = 
(1477)-1=195 obs: deve-se retirar o no 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 1
o
 algarismo; 4 para o 2
o
; 5 para o 3
o
 e 4 para o 4
o
 = 
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 
 
123 532360 
 
 
DIVISORES: 
24234quantidade
}1,0{ }2,1,0{ }3,2,1,0{ 532

 zyxzyx
 
 
DIVISORES PARES: 
18233quantidade
}1,0{ }2,1,0{ }3,2,1{ 532
 
 zyxzyx
 
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
33 
 
 
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
 
 
É 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. 
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
34 
 
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.417: 
b) 
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 no 62.417 ocupa o 81o lugar 
 
c) 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 
 
d) Cada número tem 5 algarismos  o 200o algarismo é o último do 40o número 
e) 
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 40
o
 é o 26.471  o 200o algarismo escrito é o 1. 
 
f) 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 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
35 
 
 
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 
 
 
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 é 4
n
-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 
2,vC
 
(v=quantidade de vértices) segmentos dos quais n são lados, então 
2
)3(
2,


nn
nCD n
 (obs: quantidade 
de vértices=quantidade de lados) 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
36 
 
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 1
o
 grupo e 
10,10C
 de formarmos o 2
o
 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 é: 
 
970.1258,812,20 CC
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
37 
 
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


 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
38 
 
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


 
 
 
EXERCÍCIO 15 
 
130.53
!5!20
!25
 a) 20,2520,6 
 CC
 
230.230
!6!20
!26
 
20 
folga de variável )(20 
20 b)
20,2620,7
654321
654321
654321




 CC
fxxxxxx
fxxxxxxf
xxxxxx
 
 
100.177
!6!19
!25
 
19 
)(19 
19 
20 c)
19,2519,7
654321
654321
654321
654321





 CC
fxxxxxx
xxxxxxf
xxxxxx
xxxxxx
 
287.1
!5!8
!13
 
8 
2012 
20)2(...)2()2( 
inteiros e 0,2 
2,20 d)
8,138,6
654321
654321
621
654321






 CC
yyyyyy
yyyyyy
yyy
yyx
xxxxxxx
iii
i
 
 
 
420.317120
!2!17
!19
!3!3
!6
 é solução a 
 é equação desta soluções de quantidade a 
1720320)1()1()1( 
0,,;1,1,1 
1,1,1,20 
de soluções de quantidade aencontrar ser a passa problema o ,incógnitas essas fixadas 
nulas incógnitas 3 asescolher se de maneiras existem 
nulas incógnitas 3 exatamente com ,20 e)
17,193,6
17,1917,3
321321321
321332211
321321
3,6
654321







CC
CC
zzzzzzzzz
zzzzyzyzy
yyyyyy
C
xxxxxx
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
39 
 
 
711362854203soluções de Total
soluções 61 nulas incógnitas 5 com 
:então 20 valer deve restante a ,incógnitas essas fixadas 
nulas incógnitas 5escolher se de maneiras existem
soluções 2851915 nulas incógnitas 4 com 
 é equação desta soluções de quantidade a 
1820220)1()1( 
0,;1,1 
1,1,20 
 temos,incógnitas essas fixadas 
nulas incógnitas 4escolher se de maneiras 
4,6
 existem 
soluções 420.3 nulas incógnitas 3 com 
asnu incógnitas 3 menos pelo com ,20 f)
 
 
 
l
5,6
5,6
18,194,6
18,1918,2
212121
212211
2121
654321
..
C
C
CC
CC
zzzzzz
zzzyzy
yyyy
C
xxxxxx










 
 
EXERCÍCIO 16 
 
} divide 10|{
} divide 7|{
} divide 3|{
} divide 2|{
}000.11|{
4
3
2
1
xxA
xxA
xxA
xxA
xx





 
 
100
10
000.1
)(
142
7
000.1
)(
333
3
000.1
)(
500
2
000.1
)(
000.1)(
inteiraparte 
4
3
2
1






























An
An
An
An
n
 
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
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
40 
 
4
210
000.1
)(
4
210
000.1
)(
14
70
000.1
)(
33
60
000.1
)(
23
42
000.1
)(
4321
432
431
421
321



































AAAAn
AAAn
AAAn
AAAn
AAAn
 
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
 ou y
2
 ou...ou y
p
 não 
pertencem ao Conjunto-Imagem da função 
 
Chamando de 
),...,2,1( pjA j  
 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
n
n SSSpSSSpAAAnp )1(...)1(...()...( 21
1
2121 

 
 
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 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
41 
 
... 
n
ppp ppCS )]1([1,1  
 
n
ppp ppCS )(, 
 
 
Então a quantidade de funções sobrejetoras é 
 









p
k
n
kp
k
n
pp
Pn
pp
pn
p
n
p
n
p
n
pp
Pn
pp
pn
p
n
p
n
kpC
ppCppCpCpCpC
ppCppCpCpCp
0
,
,1,
1
2,1,0,
,1,
1
2,1,
)()1(
)()1()]1([)1(...)2()1()0(
)()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 
 
 
a) Amostra ORDENADA SEM REPOSIÇÃO 
 
 
!!...!
!
...)(
)(
21
,,,
,
12211
k
nNnNnN
nN
nnn
n
AAAAn
ASn
kk


 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
42 
 
b) Amostra ORDENADA COM REPOSIÇÃO 
 
 
!!...!
!
...)(
)(
21
,,,
,
12211
k
nNnNnN
nN
nnn
n
AAAAn
ASn
kk




 
 
 
c) Amostra NÃO ORDENADA SEM REPOSIÇÃO 
 
 
12211 ,,,
,
...)(
)(
kk nNnNnN
nN
CCCAn
CSn

 
 
 
b) Amostra NÃO ORDENADA COM REPOSIÇÃO 
 




12211 ,,,
,
...)(
)(
kk nNnNnN
nN
CCCAn
CSn 
 
 
EXERCÍCIO 21 
 
a) OBJETOS DISTINGUÍVEIS, COM EXCLUSÃO 
 
 
nNASn ,)( 
 
 
b) OBJETOS DISTINGUÍVEIS, SEM EXCLUSÃO 
 
 
 nNASn ,)(
 
 
c) OBJETOS NÃO DISTINGUÍVEIS, COM EXCLUSÃO 
 
 
nNCSn ,)( 
 
 
d) OBJETOS NÃO DISTINGUÍVEIS, SEM EXCLUSÃO 
 
 
 nNCSn ,)(
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
43 
 
SOLUÇÃO DOS EXERCÍCIOS – BINÔMIO DE NEWTON 
 
 
EXERCÍCIO 1 
 
 
 
126 é de ecoeficient o 126
5
9
)1( 
52527
9
)1(
)1(919
2255275
6
527327
2
93
21





































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
 é máximo termoo
...... logo
65,...,18,17 para 
16,...,2,1 para 
 então
5,161366 
!65
!65
3
3
)!1(
!
)!65(
)!66(
 
3
1
 )!66()!1(
!65
3 )!65(!
!65
 
3
1
1
65 
3
165
 se 
3
165
1
3
165































































T
TTTTTTTT
kTT
kTT
kkk
k
k
k
k
kkkk
kk
TT
kk
T
kk
kk
k
k
kk
kkkk
k
k
k
k
 
 
 
EXERCÍCIO 3 
 
11
1
0
1
0
)1(
,1,1
1
1
1,1
1
1,1
1110
,
43)31(3 
31333333 
3
)!()!1(
)!1(
3
)!()!1(
)!1(
3
)!(!
!
3
























 

nn
n
p
n
p
ppn
pn
p
pn
n
k
k
kn
n
k
k
kn
n
k
k
n
k
k
n
k
k
n
k
k
kn
nn
CnCnCnCn
knk
n
n
knkk
nn
k
knk
n
kkC
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
44 
 
 
EXERCÍCIO 4 
 
 
2
5)1(
2
)32()32(
:é escoeficient dos soma a 1 fazendo
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









 
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
45 
 
SOLUÇÃO DOS EXERCÍCIOS – TRIÂNGULO DE PASCAL 
 
 
EXERCÍCIO 1 
 


























 

















 











 






 




 1
!
 
1
...
 
1
!
 
1
!
 
1
!
 
1
!
!
)1)...(2)(1(
!)1)...(2)(1( a)
colunas das teorema
fatores 
11 p
np
p
p
np
p
p
p
p
p
p
pk
p
p
pk
pS
p
pk
p
p
kpkkk
pkpkkk
n
k
n
k
p
  
  
 
 
 
  
6
)12)(1(
2
)1(
6
)1)(2(
2 
2 
1
!1
3 
2
!2)1()1( 
)1( 
0,1,1 
0,0,1 
)( 
)1( b)
1 11
2
1
2
012
0122
012
2
2
2
012
2











 





 







 


nnnnnnnn
nn
kkkkkkS
kkkk
aaa
aaaa
akaakak
akakkak
n
k p
n
k
p
n
k

 
 
 
 
  
4
)1(
2 
1
3 
2
6
4 
3
6
2 
1
!1
3 
2
!23
4 
3
!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( c)
22
1 11
2
1
3
1
3
0123
0123233
0123
2
23
3
3
3
0123
3






 





 





 





 





 





 








 




nnnnnnnn
kkkkkkkkkkkkS
kkkkkkk
aaaa
aaaaaaa
akaaakaakak
akakkakkkak
n
k p
n
k
p
n
k
p
n
k
 
 
 
 
 
 
 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
46 
 
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
Stifel de relaçãoStifel de relação













 





 



















 





 






























 












 





 

















 











 

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
 
 
pn
pn
k
C
pn
k
pknpkn
pn
pn
k
pkn
pn
k
pkn
pn
k
pkn
C
CnCnk
C
Cnnk
C
kC
pn
,
1
1
1
1
1,1,
,
1
1
1,
1
1
1,
1
1
1,
,
)1()1(
 
)]1()1[(
 b)
colunas das teorema
 






















 
 
pn
pn
k
pn
pn
pn
k
pknpn
C
p
pknkn
knCn
C
CknCn
,
1
1
,
,
1
1
1,,
)!1(
)2)...((
)1()1()1()1( 










 
CONJUNTOS - ANÁLISE COMBINATÓRIA Francisco de Assis Amaral Bastos 
47 
 
pn
pn
k
pn
pn
pn
k
pn
C
p
pknknkn
pCn
C
pp
pknknkn
pCn
,
1
1
,
,
1
1
,
!
)2)...()(1(
)1(
)!1(
)2)...()(1(
)1( 











 
 
pn
pppppnpnpn
pn
pn
k
pknpn
pn
pn
k
pknpn
C
CCCCpCn
C
CpCn
C
pCCn
,
,,1,1,,
,
1
1
,1,
,
1
1
,1,
colunas das teorema
...)1(
)1()1(   












 
 
pn
pn
pn
pn
pn
pnpn
C
pp
pnnnnp
Cn
C
p
pnnnnp
Cn
C
pCCn
,
,
,
,
,
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
p
np
nC
C
C
p
np
Cn
C
p
pnnn
p
np
Cn
pn
pn
pn
pnpn
pn
pn
 
 
 
EXERCÍCIO 5 
 
a) 
141411212  pppppp ouou
 
 
b) 
3159292  pppppp ou
 
 
 
 
EXERCÍCIO 6 
 
0 1
1
1
!
)!(
)!)(1(
!)1(
!
)!(
)!1(
)!1(
)!(!
!
)!1(!
)!1(
se
,
,1



















p
pn
n
n
pn
pnpn
nn
n
pn
pn
n
pnp
n
pnp
n
C
C
pn
pn