ANÁLISE COMBINATÓRIA 1

Prévia do material em texto

Universidade Estadual de Campinas
Análise Combinatória, Probabilidade
Noções de Estat́ıstica
Tema 1 - Elementos da teoria de conjuntos e
estruturas de contagem
Prof. Laura Rifo
laurarifo at ime.unicamp.br
- 1o semestre 2017 -
Conteúdo
1 Elementos da teoria de conjuntos 1
1.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Relações entre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Coleções de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Produto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Mãos à obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Medida de contagem 9
2.1 Prinćıpio da adição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Algumas desigualdades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Desigualdade de Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Desigualdade de Bonferroni . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Prinćıpio de inclusão-exclusão . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Prinćıpio da multiplicação . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Mãos à obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Estruturas de contagem 19
3.1 Permutações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Combinações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Mãos à obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Amostragem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Amostra ordenada sem reposição . . . . . . . . . . . . . . . . . . . . . . 28
http://www-history.mcs.st-andrews.ac.uk/Biographies/Boole.html
http://www-history.mcs.st-andrews.ac.uk/Biographies/Bonferroni.html
ii Conteúdo
Amostra ordenada com reposição . . . . . . . . . . . . . . . . . . . . . . 29
Amostra não ordenada sem reposição . . . . . . . . . . . . . . . . . . . . 29
Amostra não ordenada com reposição . . . . . . . . . . . . . . . . . . . 29
Mãos à obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Coeficientes multinomiais . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Mãos à obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Caṕıtulo 1
Elementos da teoria de conjuntos
1.1 Conjuntos
A teoria de conjuntos é a base para todo o cálculo de probabilidades, assim como para
outras áreas da matemática. Nesta seção, faremos uma pequena revisão do material
necessário para este módulo.
Lembremos que um conjunto é uma coleção de objetos, chamados os elementos do con-
junto. Tipicamente, denotaremos os conjuntos por letras maiúsculas do começo do alfa-
beto, A,B, . . . , e seus elementos por letras minúsculas do alfabeto, a, b, c, s, t, x, y, . . . .
Alguns conjuntos serão denotados por śımbolos especiais, como veremos mais adiante.
A afirmação de que s é um elemento do conjunto A é escrita como s ∈ A. Como
conceito primitivo, um conjunto fica completamente determinado por seus elementos,
A = {a1, a2, . . . }. Decorrente disto, dizemos que dois conjuntos A e B são iguais,
A = B, se eles tiverem os mesmos elementos,
A = B se e somente se (s ∈ A ⇐⇒ s ∈ B) .
Esta relação entre pertinência e igualdade é conhecida como o Axioma da Extensão.
Dados os conjuntos A e B, dizemos que A é um subconjunto de B, A ⊂ B, se todo
elemento de A for também elemento de B,
A ⊂ B se e somente se (s ∈ A⇒ s ∈ B) ,
e diremos que A ⊂ B é um subconjunto próprio de B se existe algum elemento b ∈ B
que não pertence a A. Neste segundo caso, escreveremos explicitamente A ( B.
2 Elementos da teoria de conjuntos
Figura 1.1: Diagrama de Euler-Venn para dois conjuntos, A ⊂ B.
O conceito de inclusão de conjuntos nos permite reescrever o Axioma da Extensão da
seguinte maneira
A = B se e somente se (A ⊂ B e B ⊂ A) .
Esta condição equivalente é a comumente usada nas demonstrações de igualdade entre
dois conjuntos: primeiro mostramos que A ⊂ B e depois que B ⊂ A.
Podemos representar conjuntos e relações entre eles com desenhos esquemáticos chama-
dos diagramas de Euler - Venn. O diagrama da Figura 1.1, por exemplo, representa
a relação de subconjunto, com A ⊂ B.
Consideremos um conjunto Ω. Para cada elemento s ∈ Ω, um predicado q(s) é uma
afirmação que ou é verdadeira ou é falsa. Assim, {s ∈ Ω : q(s) é verdadeira} define
completamente um subconjunto de Ω: o conjunto de todos os elementos de Ω que satis-
fazem q(s). Por exemplo,
A = {s inteiro : s = 2k, para algum k natural }
representa o conjunto dos números pares não-negativos.
A existência de um conjunto a partir de um predicado é garantido pelo chamado Axioma
da Especificação.
Assumiremos agora a seguinte hipótese de existência: existe um conjunto. Com esta
hipótese e com o Axioma da Especificação, podemos provar que existe um conjunto sem
elementos.
De fato, dado um conjunto Ω, basta tomar {s ∈ Ω : s 6= s}, ou qualquer outro predicado
universalmente falso.
Daqui também, pelo Axioma da Extensão, temos que este conjunto é único: o chamado
conjunto vazio, denotado por ∅.
Observe que o conjunto vazio é subconjunto de qualquer conjunto A. De fato, se isto
não fosse verdade, deveria existir um elemento s ∈ ∅ que não pertence a A, o que não
é posśıvel.
http://www-history.mcs.st-andrews.ac.uk/Biographies/Euler.html
http://www-history.mcs.st-andrews.ac.uk/Biographies/Venn.html
Relações entre conjuntos 3
Trabalharemos, em qualquer contexto, com conjuntos que serão todos subconjuntos de
um conjunto espećıfico, Ω, que chamaremos conjunto universo, no sentido de um
conjunto que contém todos os elementos pertinentes ao contexto dado.
1.2 Relações entre conjuntos
Lembremos que as operação básicas em teoria de conjuntos permitem definir novos
conjuntos a partir de conjuntos dados. Mais precisamente, sejam A e B subconjuntos
de um mesmo conjunto Ω. Definimos a união entre A e B, como o conjunto que contém
todos os elementos de A ou de B, e apenas estes,
A ∪B = {s ∈ Ω : s ∈ A ou s ∈ B}.
A interseção de A e B é o conjunto dos elementos em comum entre A e B,
A ∩B = {s ∈ Ω : s ∈ A e s ∈ B}.
A diferença de conjuntos de B e A é o conjunto dos elementos que estão em B mas
não em A,
B \A = {s ∈ Ω : s ∈ B e s /∈ A}.
O complementar de A é o conjunto de elementos de Ω que não estão em A,
AC = {s ∈ Ω : s /∈ A} = Ω \A.
Observe que B \A é igual a A ∩BC . (Prove.)
Dizemos que os conjuntos A e B são disjuntos se sua interseção for o conjunto vazio,
A ∩B = ∅.
Uma discussão mais aprofundada de teoria de conjuntos pode ser encontrada no livro
clássico de Halmos [4]. O projeto Laboratório de Probabilidade e Estat́ıstica da Univer-
sidade do Alabama [12] disponibiliza um applet sobre o diagrama de Euler-Venn para
visualizar as posśıveis relações entre dois conjuntos.
1.3 Coleções de conjuntos
Podemos estender as operações anteriores para coleções finitas ou infinitas de conjuntos.
http://www.math.uah.edu/stat/applets/VennGame.html
4 Elementos da teoria de conjuntos
Assim, se tivermos três conjuntos A,B,C, a união deles é
A ∪B ∪ C = (A ∪B) ∪ C = A ∪ (B ∪ C) = {s ∈ Ω : s ∈ A ou s ∈ B ou s ∈ C} ,
e a interseção é
A ∩B ∩ C = (A ∩B) ∩ C = A ∩ (B ∩ C) = {s ∈ Ω : s ∈ A e s ∈ B e s ∈ C}.
Mais geralmente, seja A uma coleção de subconjuntos de Ω, A = {Ai ⊂ Ω : i ∈ I}.
A união da coleção A é o conjunto que combina os elementos dos conjuntos em A,⋃
A = {s ∈ Ω : s ∈ A para algum A ∈ A},
ou, escrito de outra maneira,⋃
i∈I
Ai = {s ∈ Ω : s ∈ Ai para algum i ∈ I}.
A interseção da coleção A é o conjunto dos elementos em comum a todos os conjuntos
em A, ⋂
A =
⋂
i∈I
Ai = {s ∈ Ω : s ∈ Ai para todo i ∈ I}.
A Figura 1.2 mostra estes novos conjuntosa partir de uma coleção.
Figura 1.2: Diagrama de Euler-Venn para a união e a interseção de uma coleção de
conjuntos.
Dizemos que os conjuntos da coleção A são disjuntos dois a dois se a interseção de
quaisquer dois conjuntos diferentes da coleção for vazia,
A ∩B = ∅ para quaisquer A ∈ A e B ∈ A , com A 6= B.
Dizemos que a coleção A forma uma partição de um conjunto B se A for disjunta dois
a dois e
⋃
A = B. Por exemplo, se B = {a, b, c}, então A = {{a}, {b, c}} é uma partição
de B.
Produto cartesiano 5
Dado um conjunto Ω, uma coleção importante é a coleção de todos os subconjuntos de
Ω, chamado o conjunto das partes ou conjunto potência de Ω, que denotaremos
por P(Ω) ou 2Ω. A existência desta coleção é garantida pelo Axioma das potências.
Por exemplo, se Ω = ∅, então P(Ω) é o conjunto {∅}. Se Ω = {a, b}, então P(Ω) =
{∅, {a}, {b},Ω}. O conjunto potência é tipicamente grande com relação ao conjunto
original: se Ω tem n elementos, então P(Ω) tem 2n elementos. (Prove.)
1.4 Produto cartesiano
Dados dois conjuntos A,B, definimos o produto cartesiano entre A e B, e o denota-
remos por A × B, como o conjunto de pares ordenados (a, b) tais que a é elemento de
A, e b é elemento de B,
A×B = {(a, b) : a ∈ A, b ∈ B} .
Observe que, em geral, A×B 6= B ×A. Mostre um exemplo onde a igualdade é válida
e outro onde ela não é.
Em geral, consideremos os conjuntos Ω1,Ω2, . . . ,Ωn. Definimos o produto cartesiano
entre eles como o conjunto
Ω1 × Ω2 × · · · × Ωn = {(s1, s2, . . . , sn) : si ∈ Ωi para todo i ∈ {1, 2, . . . , n}}.
Se todos os conjuntos forem iguais, Ωi = Ω, denotamos o produto cartesiano como Ω
n.
Podemos estender esta definição para uma seqüência enumerável de conjuntos (Ω1,Ω2, . . . )
como ∏
i
Ωi = Ω1 × Ω2 × · · · = {(s1, s2, . . . ) : si ∈ Ωi para todo i ∈ {1, 2, . . . }},
ou para uma famı́lia não-enumerável, como, por exemplo, {Ωt, t ∈ [0, 1]}. Neste último
exemplo, podemos pensar o conjunto de ı́ndices como o tempo, e Ωt como o conjunto
considerado no instante t. No caso enumerável, esta interpretação também se aplica,
considerando o conjunto de ı́ndices como as etapas de um processo e Ωn como o conjunto
considerado da n-ésima etapa.
Denotaremos os elementos de um produto cartesiano com a notação vetorial usual
(s1, s2, . . . , sn) ou simplesmente como letras de uma palavra s1s2 . . . sn.
Alguns produtos do portal Matemática Multimı́dia [10] lidam com teoria de conjuntos,
podendo ser utilizado como material auxiliar com os alunos. Os v́ıdeos Alice, os parado-
xos e a formalização e A revanche de Alice mostram alguns dos paradoxos em teoria de
http://m3.ime.unicamp.br/portal/Midias/Videos/index.php?url=http://m3.ime.unicamp.br/portal/Midias/Videos/VideosM3Matematica/MatematicanaEscola/ParadoxosdeAlice/
http://m3.ime.unicamp.br/portal/Midias/Videos/index.php?url=http://m3.ime.unicamp.br/portal/Midias/Videos/VideosM3Matematica/MatematicanaEscola/ParadoxosdeAlice/
http://m3.ime.unicamp.br/portal/Midias/Videos/index.php?url=http://m3.ime.unicamp.br/portal/Midias/Videos/VideosM3Matematica/MatematicanaEscola/RevanchedeAlice/
6 Elementos da teoria de conjuntos
conjuntos e suas soluções formais. Os v́ıdeos Grande hotel e Hotel de Hilbert abordam
conjuntos numéricos infinitos e alguns resultados pouco intuitivos relacionados.
1.5 Mãos à obra
1. Mostre que para todo conjunto A ⊂ Ω, A ∪∅ = A e A ∩∅ = ∅.
2. Dados conjuntos A e B de um conjunto universo Ω, mostre que A∩B ⊂ A ⊂ A∪B.
3. A ⊂ B se e somente se A ∪B = B.
4. A ⊂ B se e somente se A ∩B = A.
5. Dados os conjuntos A,B,C ⊂ Ω, mostre que: A ∪ (B ∪ C) = (A ∪ B) ∪ C,
A ∩ (B ∩ C) = (A ∩ B) ∩ C, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) =
(A ∪B) ∩ (A ∪ C).
6. Mostre que C ⊂ A é condição necessária e suficiente para que (A ∩ B) ∪ C =
A ∩ (B ∪ C).
7. Dado um subconjunto A de um conjunto universo Ω, mostre que A ∪ AC = Ω e
que A ∩AC = ∅.
8. ∅C = Ω, ΩC = ∅.
9. (AC)C = A, A ⊂ B se e somente se BC ⊂ AC .
10. (Leis de De Morgan) Dados dois conjuntos A e B, mostre que
(a) (A ∪B)C = AC ∩BC
(b) (A ∩B)C = AC ∪BC
11. Considere o conjunto A = {0, 1, 2, 3, 4, 5}. Dê um exemplo de uma partição de A
com 3 conjuntos; com 4 conjuntos. Qual é o maior número de conjuntos que uma
partição de A pode ter? E o menor?
12. Mostre que, dados dois conjuntos A e B, P(A)∩P(B) = P(A∩B) e P(A)∪P(B) ⊂
P(A ∪B). Se A ⊂ B, então P(A) ⊂ P(B).
13. Mostre que, dado um conjunto A,
⋃
P(A) = A e
⋂
P(A) = ∅.
14. Obtenha P(∅), PP(∅) e PPP(∅).
http://m3.ime.unicamp.br/portal/Midias/Videos/index.php?url=http://m3.ime.unicamp.br/portal/Midias/Videos/VideosM3Matematica/MatematicanaEscola/GrandeHotel/
http://m3.ime.unicamp.br/portal/Midias/Videos/index.php?url=http://m3.ime.unicamp.br/portal/Midias/Videos/VideosM3Matematica/MatematicanaEscola/HotelHilbert/
http://www-history.mcs.st-andrews.ac.uk/Biographies/De_Morgan.html
Mãos à obra 7
15. Dados os conjuntos A,B,X, Y , prove que (A ∪ B) × X = (A × X) ∪ (B × X) e
(A ∩B)× (X ∩ Y ) = (A×X) ∩ (B × Y ).
16. Seja Ω = {1, 2, 3, 4}× {1, 2, 3, 4, 5, 6}. Este conjunto pode ser interpretado como o
conjunto de resultados do lançamento de uma dado de 4 faces e um dado de 6 faces.
Considere os conjuntos A = {(x, y) ∈ Ω : x é par } e B = {(x, y) ∈ Ω : x+ y = 5}.
Interprete e liste os elementos de cada um dos conjuntos a seguir: Ω, A, B, A∪B,
A ∩B, A \B, B \A.
17. Seja Ω = {0, 1}3. Este conjunto pode ser visto como o conjunto de resultados
de três lançamentos de uma moeda (0 denotando coroa e 1, cara, por exemplo).
Defina os conjuntos A = {(s1, s2, s3) ∈ Ω : s2 = 1} e B = {(s1, s2, s3) ∈ Ω :
s1 + s2 + s3 = 2}. Interprete e liste os elementos de cada um dos conjuntos a
seguir: Ω, A, B, AC , BC , A ∪B, A ∩B, A \B, B \A.
18. Seja Ω = {0, 1}2, o conjunto de resultados em dois lançamentos de uma moeda.
Liste os elementos do conjunto das partes de Ω, P(Ω).
19. Podemos denotar um conjunto de cartas de baralho como o conjunto produto
Ω = {As, 2, 3, 4, 5, 6, 7, 8, 9, 10, J,Q,K} × {♣,♥,♦,♠},
onde o primeiro elemento do par ordenado indica o valor da carta e o segundo
indica o naipe. Denotemos por A o conjunto de corações, e por B o conjunto de
cartas com personagens. Interprete e liste os elementos dos conjuntos A, B, A∪B,
A ∩B, A \B, B \A.
20. Considere a seqüência de conjuntos An = [0, 1− 1/n], para n ∈ {1, 2, . . . }. Deter-
mine
⋂
An,
⋃
An,
⋂
ACn ,
⋃
ACn .
8 Elementos da teoria de conjuntos
Caṕıtulo 2
Medida de contagem
Vimos, como axioma básico em teoria de conjuntos, que um conjunto é completamente
determinado por seus elementos. Em particular, se quisermos saber quantos elementos
tem um conjunto finito, basta, em prinćıpio, listar seus elementos e contá-los. Esta, no
entanto, pode-se mostrar uma tarefa desmesurada.
Quando trabalhamos com problemas envolvendo amostragens de um conjunto finito, por
exemplo, o conjunto que queremos contar é tipicamente um conjunto grande, o que nos
leva à necessidade de construir formas eficientes de contagem.
Veremos, neste caṕıtulo, ferramentas básicas para determinar o número de elementos de
um conjunto sem necessidade de listar todos seus elementos.
Uma das regras básicas da contagem é o prinćıpio da adição da medida de contagem,
também conhecido como regra da soma.
Suporemos, a menos que seja explicitado o contrário, que estamos interessados em um
contexto no qual o conjunto universo Ω é um conjunto finito.
Neste caso, dado A ⊂ Ω, a cardinalidade de A é o número de elementos de A, e será
denotado por #(A) ou simplesmente #A. A função # é chamada medida de contagem
e é fundamental na teoria de probabilidades discretas.
2.1 Prinćıpio da adição
Dados A e B, dois conjuntos disjuntos contendo p e q elementos, respectivamente, então
A ∪B tem p+ q elementos.
10 Medida de contagem
Em geral, sejam A1, A2, . . . , An uma coleção finita de subconjuntos disjuntos dois a dois
de Ω. Então
#
(
n⋃
k=1
Ak
)
=
n∑
k=1
#(Ak).A visualização deste axioma é imediata: sejam A = {a, b} e B = {c, d, e}, conjuntos com
#A = 2 e #B = 3; então #(A ∪ B) = #{a, b, c, d, e} = 5 = 2 + 3. Do mesmo modo, a
necessidade de serem conjuntos disjuntos também é clara: se A = {a, b} e B = {b, c, d},
com #A = 2 e #B = 3; então #(A ∪B) = #{a, b, c, d} = 4 6= 2 + 3.
Uma conseqüência imediata desta propriedade é que, dados dois conjuntos A e B tais
que A ⊂ B, então #A ≤ #B (mostre isto). Dizemos, então, que # é uma função
crescente relativa à ordem parcial dos subconjuntos de Ω e à ordem usual dos números
reais.
2.2 Algumas desigualdades
As seguintes desigualdades nos permitem obter limitantes para o número de elementos
de um conjunto formado a partir da união ou da interseção de outros conjuntos.
Desigualdade de Boole
Sejam A1, A2, . . . , An uma coleção finita de subconjuntos disjuntos de Ω. Então
#
(
n⋃
k=1
Ak
)
≤
n∑
k=1
#(Ak).
Demonstração. Vejamos inicialmente o caso n = 2, para entender o argumento da prova.
Dados os conjuntos A1 e A2, consideremos os conjuntos B1 = A1 e B2 = A2 \ B1 =
A2 \A1. Então B1 ∪B2 = A1 ∪A2, ou seja, #(B1 ∪B2) = #(A1 ∪A2). Como B1 e B2
são disjuntos, pelo prinćıpio da adição, #(B1 ∪ B2) = #B1 + #B2. Finalmente, como
B1 ⊂ A1 e B2 ⊂ A2, temos #B1 ≤ #A1 e #B2 ≤ #A2. Assim,
#(A1 ∪A2) = #(B1 ∪B2) = #B1 + #B2 ≤ #A1 + #A2 .
Para n qualquer, dados os conjuntos A1, A2, . . . , An, definamos os conjuntos B1 = A1,
B2 = A2 \ B1, B3 = A3 \ B2, e assim por diante, ou seja, Bk = Ak \ (A1 ∪ · · · ∪Ak−1)
para k ∈ {2, . . . , n}.
http://www-history.mcs.st-andrews.ac.uk/Biographies/Boole.html
Algumas desigualdades 11
 
 
 
Figura 2.1: Construção da prova da desigualdade de Boole.
Observe que os elementos de B2 são os elementos de A2 que não estão em A1. Do mesmo
modo, os elementos de B3 são os elementos de A3 que não estão nem em A1 nem em
A2, e assim por diante. A Figura 2.1 mostra o caso para 3 conjuntos.
Portanto, os conjuntos B1, B2, . . . , Bn são disjuntos dois a dois e têm a mesma união
que A (Prove estas afirmações formalmente dentro da teoria de conjuntos). Desta forma
#(∪Ak) = #(∪Bk).
Pela regra da adição, #(∪Bk) =
∑
#Bk.
Finalmente, como Bk ⊂ Ak, temos que
# (∪kAk) = # (∪kBk) =
∑
#Bk ≤
∑
#Ak,
como queŕıamos provar.
Em palavras, o total de elementos da união de conjuntos é menor ou igual que a soma dos
totais de elementos de cada conjunto, já que se houver interseção não-vazia, contaremos
os elementos da interseção mais de uma vez.
12 Medida de contagem
Desigualdade de Bonferroni
Seja A1, A2, . . . , An uma coleção finita de subconjuntos disjuntos de Ω. Então
#
(⋂
i
Ai
)
≥ #Ω−
∑
i
(
#ACi
)
.
Demonstração. Aplique a desigualdade de Boole aos conjuntos AC1 , A
C
2 , . . . , A
C
n e use as
leis de De Morgan.
2.3 Prinćıpio de inclusão-exclusão
Dados os conjuntos A,B ⊂ Ω,
#(A ∪B) = #A+ #B −#(A ∩B).
Demonstração. Observemos que podemos escrever A ∪ B como a união dos conjuntos
disjuntos A e B \A. Pela regra da adição, chegamos ao resultado.
Esta fórmula nos dá o total exato de elementos de uma união, indicando que devemos so-
mar os totais de elementos de cada conjunto e subtrair o total de elementos da interseção
(que foram contados duas vezes).
Este resultado pode ser estendido para mais de dois conjuntos, de forma natural. Por
exemplo, para n = 3 conjuntos, temos que
#(A ∪B ∪ C) = #A+ #B −#(A ∩B)−#(A ∩ C)−#(B ∩ C) + #(A ∩B ∩ C),
que pode ser visualizado no diagrama da Figura 2.2.
Figura 2.2: Diagrama de Euler-Venn para 3 conjuntos.
http://www-history.mcs.st-andrews.ac.uk/Biographies/Bonferroni.html
Prinćıpio da multiplicação 13
Exemplo Quantos inteiros entre 1 e 1000 são diviśıveis por 3 ou 7?
Denotemos por A e B os conjuntos
A = inteiros entre 1 e 1000 diviśıveis por 3;
B = inteiros entre 1 e 1000 diviśıveis por 7.
Queremos calcular #(A ∪B).
Como
#A =
⌊
1000
3
⌋
= 333 ,
#B =
⌊
1000
7
⌋
= 142 ,
#(A ∩B) =
⌊
1000
21
⌋
= 47 ,
onde bxc é a parte inteira de x, pelo prinćıpio de inclusão-exclusão, temos que
#(A ∪B) = 333 + 142− 47 = 428 .
2.4 Prinćıpio da multiplicação
O prinćıpio da multiplicação, também conhecido como a regra do produto em contagem,
se baseia na formulação de um procedimento ou algoritmo sequencial que permita gerar
os objetos que devem ser contados.
Em outras palavras, suponha que o procedimento de contagem pode ser visto como um
processo com duas etapas. Se a primeira etapa puder ser realizada de n1 maneiras dife-
rentes, e a segunda, de n2 maneiras diferentes, independentemente da maneira escolhida
na etapa anterior, então o total de maneiras de realizar o processo é n1 × n2.
Por exemplo, considere um grupo com 3 meninos e 4 meninas, do qual escolheremos uma
dupla menino-menina. Podemos ver este procedimento como o processo de escolher um
menino e, depois de ter escolhido o menino, escolher uma menina. Para o primeiro
passo, temos 3 possibilidade de escolha, e para o segundo, temos 4 possibilidades, inde-
pendentemente do menino escolhido. Assim, podemos formar esta dupla de 3× 4 = 12
formas diferentes.
Observe que podeŕıamos ter escolhido primeiro a menina e depois o menino, obtendo o
mesmo resultado final.
Em geral, suponha que o procedimento pode ser visto como um processo com k passos,
a serem realizados sucessivamente, e que cada passo j pode ser realizado de nj formas
diferentes, independentemente das escolhas feitas previamente.
14 Medida de contagem
Então o número total de formas de realizar o procedimento é igual a n1×n2× · · · ×nk,
que é também o número total de posśıveis objetos gerados.
Podemos visualizar este algoritmo em uma árvore de contagem. Consideremos uma
árvore com k ńıveis de galhos, de modo que cada galho do ńıvel i se divida em ni+1
novos galhos no ńıvel i+ 1, para i = 1, . . . , k − 1, como mostrado na Figura 2.3.
Figura 2.3: Diagrama de árvore de contagem.
O total de nodos no lado direito da árvore é igual ao produto n1 n2 . . . nk.
Em particular, se em cada passo do algoritmo tivermos o mesmo número de possibili-
dades, n, então o procedimento completo pode ser realizado de nk maneiras posśıveis.
Exemplo A placa de um carro consiste em 3 letras e 4 d́ıgitos. Quantas placas dife-
rentes podem ser licenciadas?
Considerando um total de 26 letras e 10 d́ıgitos, temos 26×26×26×10×10×10×10 =
175 760 000 placas diferentes.
O fundamental para a correta aplicação deste prinćıpio em um problema de contagem é
fazer uma formulação clara do algoritmo que gera os diversos posśıveis objetos, de modo
que cada objeto seja contado e que seja contado uma única vez.
Prinćıpio da multiplicação 15
Exemplo Uma bandeira é formada por 4 listras, que devem ser coloridas cada uma
de uma cor, usando no máximo as cores branco, verde e cinza. Se listras adjacentes não
devem ter a mesma cor, de quantas formas pode ser colorida a bandeira?
Podemos ver este problema como um processo em 4 etapas, uma etapa para cada listra.
Assim, a primeira listra pode ser de qualquer uma das 3 cores; a segunda não pode ser
da cor anterior, então pode ser qualquer uma das outras 2 cores; o mesmo vale para
a terceira e para a quarta listra. Portanto, pelo prinćıpio da multiplicação, a bandeira
pode ser pintada de 3 × 2 × 2 × 2 = 24 formas diferentes, algumas delas com apenas
duas cores.
Exemplo Determine a quantidade de números naturais entre 100 e 999, formados com
três algarismos diferentes.
Observe que aqui temos duas condições: uma de que os d́ıgitos devem ser diferentes, e
outra de que o primeiro d́ıgito não pode ser igual a zero. Podemos ver o problema como
um processo em 3 etapas diferentes, uma para cada d́ıgito, começando, por exemplo,
com o primeiro d́ıgito. Como ele não pode ser zero, temos 9 possibilidades; para o
segundo algarismo, ele pode ser zero mas tem que ser diferente do primeiro, assim temos
9 possibilidades; e para o terceiro,como já foram dois, temos 8 possibilidades. Portanto,
o total requerido é igual a 9× 9× 8 = 648.
Neste exemplo, podeŕıamos ter começado o processo por outro algarismo, que não o
primeiro. Por exemplo, se tivéssemos começado do último, teŕıamos 10 possibilidades,
para o segundo algarismo, 9 possibilidades, e para o primeiro... não sabeŕıamos dizer
quantas possibilidades: se o zero já tiver sáıdo, temos 8 possibilidades; e se não tiver
sáıdo, temos 7 possibilidades. Ou seja, deveŕıamos saber em quantas das 9 × 10 = 90
possibilidades o 0 aparece, para poder completar a solução do problema.
Exemplo Quantos números naturais de 4 algarismos, que sejam menores que 5003 e
diviśıveis por 5, podem ser formados apenas com os algarismos 2, 3, 4 e 5?
A recomendação para abordar o problema é começar pelo algarismo com mais restrições,
até o algarismo com menos restrições. Assim, começando pelo último algarismo, temos
apenas uma opção (o d́ıgito 5); para o primeiro algarismo, temos 3 opções (pois o número
deve ser menor que 5000); para os outros dois, temos 4 opções para cada. Ou seja, temos
3× 4× 4× 1 = 48 números satisfazendo as condições.
Em muitos problemas aplicados, tipicamente, o total de galhos de um nodo depende não
só da etapa do processo como também do nodo considerado. Nesses casos, o processo
16 Medida de contagem
de contagem deve ser analisado separadamente levando em conta estas condições, como
no exemplo seguinte.
Exemplo Quantos números pares de três algarismos podemos escrever com algarismos
diferentes?
Daremos três soluções para este problema.
solução 1 O último algarismo pode ser escrito de 5 modos: 0, 2, 4, 6, 8. O primeiro
dependerá de qual algarismo foi usado no passo anterior. Se foi zero, então o primeiro
pode ser escolhido de 9 modos; se o zero não foi usado, temos 8 modos. Precisamos
assim contar quantos casos têm o zero e quantos não o têm como último algarismo.
Terminando em zero, temos 1 modo de escolher o último algarismo, 9 modos de escolher
o primeiro, e 8, o segundo: 9× 8× 1 = 72 números.
Não terminando em zero, temos 4 modos para o último algarismo, 8 para o primeiro e
8 para o segundo: 8× 8× 4 = 256.
Finalmente, pelo prinćıpio da adição, o total de números satisfazendo a condição é
72 + 256 = 328.
solução 2 Podemos ignorar uma das restrições. Por exemplo, ignoremos que o pri-
meiro algarismo não pode ser zero. Temos assim 5 modos de escolher o último algarismo,
9 modos de escolher o primeiro e 8, o segundo: 9× 8× 5 = 360 números. Estes números
incluem aqueles com 0 no primeiro algarismo, que tem que ser descontados. Começando
em zero, temos 1 forma de escolher o primeiro, 4 de escolher o último, e 8, o segundo:
1× 8× 4 = 32.
Portanto, temos 360− 32 = 328 números com a condição pedida.
solução 3 Similarmente à estratégia anterior, consideremos todos os números com 3
algarismos diferentes: 9× 9× 8 = 648. Destes, descontamos os números ı́mpares com 3
algarismos distintos: 8× 8× 5 = 320, obtendo 648− 320 = 328 números.
O v́ıdeo Desejos e o software Geometria do Táxi, dispońıveis no site do projeto Mate-
mática Multimı́dia [10] tratam de algumas regras de contagem, podendo ser utilizados
como material auxiliar em sala de aula.
http://m3.ime.unicamp.br/portal/Midias/Videos/index.php?url=http://m3.ime.unicamp.br/portal/Midias/Videos/VideosM3Matematica/MatematicanaEscola/Desejos/
http://www.m3.ime.unicamp.br/portal/Midias/Softwares/Recursos/taxi_contagem/taxi_contagem/visualizar.html
Mãos à obra 17
Uma referência bibliográfica clássica é o livro de Feller [2], que aborda este tópico nos
primeiros caṕıtulos, com problemas que podem ser verdadeiros desafios. Um texto muito
claro é o de Análise Combinatória [1] da Coleção do Professor de Matemática, da SBM.
Os seguintes exerćıcios são importantes para perceber diferentes abordagens do prinćıpio
de adição.
2.5 Mãos à obra
Para os seguintes exerćıcios, considere os subconjuntos A,B,C,A1, A2, . . . , An ⊂ Ω, com
Ω finito.
Dica: antes de fazer as demonstrações, construa pelo menos um exemplo, atribuindo
valores para as quantidades e conjuntos envolvidos.
1. Mostre que #AC = #Ω−#A.
2. Mostre que #(B \A) = #B −#(B ∩A).
3. Mostre que se A ⊂ B então #(B \A) = #B −#A.
4. Suponha que Ω é um conjunto de seqüências de comprimento k, com elementos da
forma (x1, x2, . . . , xk). Mostre que se cada coordenada j tiver nj posśıveis valores,
independentemente das demais coordenadas, então
#Ω = n1 × n2 × · · · × nk.
5. Mostre que se Ω tem n elementos, então Ωk tem nk elementos.
6. Mostre que o número de amostras ordenadas de k elementos que podem ser sele-
cionadas com reposição de uma população de n objetos é igual a nk.
7. Mostre que o número total de funções de um conjunto A com n elementos em um
conjunto B com m elementos é mn. Este resultado é uma motivação para usar a
notação BA para o conjunto de todas as funções de A em B.
8. Suponha que Ω tem n elementos. Mostre que o conjunto das partes de Ω tem
2n elementos. Dica: para cada subconjunto A de Ω, defina a função sobre Ω que
atribui o valor 0 se o elemento não pertencer a A, e 1, se pertencer. Mostre que
esta função determina unicamente o subconjunto A. Quantas funções deste tipo
existem?
18 Medida de contagem
9. Um experimento consiste em: primeiro, lançar um dado comum de 6 faces, depois
escolher uma carta de um baralho de 52 cartas e, finalmente, lançar uma moeda
comum. Quantos posśıveis resultados tem este experimento?
10. Uma moeda comum é lançada 10 vezes, observando a seqüência de resultados
de cada lançamento. Quantas seqüências posśıveis há? Quantas seqüências têm
exatamente 3 caras?
11. Um experimento com dados e moedas consiste em lançar um dado e depois lançar
uma moeda o número de vezes mostrado no dado, observando a seqüência de
resultados da moeda. Quantos resultados posśıveis existem? Quantos deles têm
exatamente duas caras?
12. Um experimento consiste em lançar um dado comum de 6 faces, e: parar o ex-
perimento, se o resultado for ı́mpar; ou escolher uma carta de um baralho de 52
cartas, se o resultado for par, e, neste caso, lançar uma moeda balanceada o total
de vezes indicado na carta selecionada. Suponha que Ás vale 1, e as figuras valem
10. Quantos posśıveis resultados têm este experimento?
13. Quantos inteiros entre 1 e 1000, inclusive:
(a) são diviśıveis por pelo menos dois dos números 2, 3, 7 e 10?
(b) são diviśıveis por pelo menos três dos números 2, 3, 7 e 10?
(c) não são diviśıveis por nenhum dos números 2, 3, 7 e 10?
(d) são diviśıveis por exatamente um dos números 2, 3, 7 e 10?
(e) são diviśıveis por pelo menos um dos números 2, 3, 7 e 10?
14. Quantos inteiros entre 1000 e 10000 não são diviśıveis nem por 2, nem por 3, nem
por 5?
Caṕıtulo 3
Estruturas de contagem
A construção de um algoritmo para gerar os elementos de um conjunto permite deter-
minar uma estrutura de contagem. Veremos aqui duas estruturas básicas: permutações
e combinações.
3.1 Permutações
Consideremos um conjunto D = {d1, d2, . . . , dn} com n elementos. Uma permutação
de k elementos de D é uma seqüência ordenada de k elementos diferentes de D,
(x1, x2, . . . , xk) ∈ Dk , onde xi ∈ D e xi 6= xj se i 6= j , para todos i, j.
Claramente, k não pode ser maior que n. Uma permutação de n elementos de D, ou seja,
uma ordenação de todos os elementos de D, é chamada simplesmente uma permutação
de D.
Com esta interpretação, observemos que na primeira extração, temos todos os n elemen-
tos de D como posśıveis resultados. Para a segunda extração, como o primeiro elemento
extráıdo não é reposto, temos n−1 posśıveis resultados. Para a terceira extração, temos
n − 2 posśıveis resultados. Assim por diante, até a k-ésima extração, em que temos
n− k + 1 posśıveis resultados,como mostra a Figura 3.1.
Assim, pela regra do produto, temos que o total de permutações de k elementos em n,
que denotaremos n(k), é igual a
n(k) = n(n− 1) · · · (n− k + 1) = n!
(n− k)!
,
onde n! = n(n− 1) · · · 1 é o fatorial de n.
20 Estruturas de contagem
Figura 3.1: Árvore de contagem para uma permutação de k elementos em n.
Exemplo De quantas formas diferentes podemos escolher o revezamento para goleiro
entre 11 jogadores, sendo que todos devem ser goleiro em algum momento do jogo, uma
única vez?
Como temos 11 jogadores, temos 11! = 39916800, quase 40 milhões, de formas posśıveis.
Exemplo Uma turma de alunos é formada por 6 alunos de biologia e por 4 alunos de
qúımica. Eles serão classificados de acordo com seu desempenho. Suponha que não há
empate na classificação.
(a) Quantas classificações diferentes são posśıveis?
(b) Se os alunos de qúımica forem classificados apenas entre si, e os de biologia apenas
entre si, quantas classificações diferentes são posśıveis?
(a) Como temos 10 alunos no total, temos 10! = 3628800 classificações posśıveis.
(b) Temos 6! classificações diferentes para os alunos de biologia entre si, e 4!, para os
de qúımica entre si. Pelo prinćıpio multiplicativo, temos 6! × 4! = 720 × 24 = 17280
classificações posśıveis neste caso.
Exemplo Ana tem 14 livros que pretende colocar em sua estante. Destes, 7 são de
Harry Potter, 3 são de Jogos Vorazes, 3 são do Senhor dos Anéis e 1 do Hobbit. Sua
mãe pediu que ela arrumasse a estante de acordo com a coleção, mantendo a ordem
Permutações 21
dentro de cada coleção (suponha que a mãe não sabe que o Hobbit faz parte da trilogia
do Senhor dos Anéis).
(a) Quantos arranjos diferentes são posśıveis?
(b) E se a Ana não se preocupar com a ordem dentro de cada coleção?
(a) Como os livros de uma mesma coleção devem ser ordenados, podemos ver cada
coleção como um item apenas. Ou seja, devemos ordenar 4 itens, obtendo assim, 4! = 24
posśıveis ordenações diferentes.
(b) Para cada uma das 4! ordenações anteriores, observe que HP pode ser ordenado
de 7! formas diferentes, JV de 3!, SA de 3! e o Hobbit, apenas de 1. Temos, no total,
4!7!3!3!1! = 4 354 560 ordenações diferentes.
Podemos interpretar uma permutação de k elementos de D como o resultado de um me-
canismo f́ısico que extrai k elementos da população D, sequencialmente e sem reposição.
Desta forma, podemos usar o prinćıpio da multiplicação e um mecanismo de extração
como um algoritmo de construção de permutações de k elementos de D para contar o
total de posśıveis permutações.
Em todos os exemplos anteriores, os objetos a serem ordenados eram diferentes entre si.
Outro problema aparece quando alguns dos objetos são indistingúıveis entre si.
Exemplo Quantas ordenações diferentes podem ser obtidos com as letras da palavra
matemática (desconsidere o acento da letra a)?
Primeiro, suponhamos que todas as 10 letras sejam diferentes. Nesse caso, temos 10!
arranjos posśıveis.
Mas, no caso da palavra dada, para cada um destes arranjos, permutar os m’s entre si
ou os a’s entre si ou os t’s entre si, não muda a sequência obtida. Ou seja, todas estas
2!3!2! permutações são iguais.
Portanto, temos um total de 10!/(2!3!2!) = 151 200 ordenações posśıveis.
Em geral, este mesmo racioćınio mostra que temos
n!
n1!n2! . . . nk!
permutações diferentes de n objetos, quando n1 são parecidos entre si, n2 são parecidos
entre si (e diferentes dos anteriores), e assim por diante.
22 Estruturas de contagem
Exemplo Um torneio de xadrez tem 10 competidores, dos quais 4 são russos, 3 dos
Estados Unidos, 2 da Grã-Bretanha e 1 do Brasil. Em uma lista das colocações apenas
por nacionalidade, quantos resultados são posśıveis?
Pelo anterior, temos 10!/(4!3!2!1!) = 12 600 resultados diferentes.
3.2 Combinações
Consideremos um conjunto D = {d1, d2, . . . , dn} com n elementos. Uma combinação de
k elementos de D é um subconjunto (não-ordenado) de k elementos diferentes de D,
{x1, x2, . . . , xk} , onde xi ∈ D e xi 6= xj se i 6= j , para todos i, j.
Novamente, k não pode ser maior que n.
Podemos interpretar uma combinação como o resultado do mecanismo f́ısico que extrai
uma amostra não-ordenada de uma população D sem reposição.
Denotemos por C(n, k) o total de combinações de k elementos de um grupo de n.
Observemos que cada combinação permite construir k! ordenações diferentes, ou seja,
k! permutações de comprimento k dos elementos selecionados.
Figura 3.2: Uma combinação de k elementos gera k! permutações desses elementos.
Isto nos permite obter o total de combinações posśıveis de k elementos dentre n a partir
do total de permutações de k elementos, já que
n(k) = k!C(n, k) =⇒ C(n, k) = n!
(n− k)! k!
=
(
n
k
)
,
chamado coeficiente binomial. Este coeficiente representa, portanto, o total de com-
binações posśıveis de k objetos extráıdos de um conjunto com n objetos, quando a
ordem da seleção não for relevante.
Combinações 23
Por convenção, definimos 0! = 1. Com isto,
(
n
0
)
=
(
n
n
)
= 1. Além disto,
(
n
k
)
= 0, quando
k < 0 ou k > n.
Veja que, com esta construção reobtemos a mesma interpretação de C(n, k) que fizemos
na atividade ABRACADABRA, considerando n o total de passos e k, o total de passos
para a direita, a partir do vértice superior.
Exemplo Um comitê de 3 pessoas deve ser formado de um grupo de 20 pessoas.
Quantos comitês diferentes podemos formar?
De maneira imediata, temos
(
20
3
)
= 1140 comitês diferentes.
Exemplo Voltando à estante de Ana, suponha que ela vai viajar e quer levar três
livros para reler.
(a) De quantas formas ela pode escolher estes três livros?
(b) Suponha que ela quer levar um de cada coleção para reler. Como ela já leu todos
esses livros, ela sabe que o Hobbit faz parte da trilogia do Senhor dos Anéis. Neste caso,
de quantas formas ela pode escolher estes livros?
No primeiro item, ela tem
(
14
3
)
= 364 opções. No segundo item, para HP, ela tem 7
possibilidades, 3 para JV e 4 para SA. Assim, ela pode escolher os livros de
(
7
1
)
×
(
3
1
)
×(
4
1
)
= 84 formas diferentes.
Exemplo De um grupo de 5 mulheres e 7 homens, quantos comitês diferentes podemos
formar com 2 mulheres e 3 homens? E se dois dos homens não puderem trabalhar juntos?
Para a primeira parte, temos
(
5
2
)
= 10 formas de escolher as duas mulheres, e
(
7
3
)
= 35, de
escolher os 3 homens. Assim, pelo prinćıpio multiplicativo, temos 350 comitês posśıveis.
Com a restrição da segunda parte, temos que dos 35 grupos de 3 homens, em 5 deles,
os dois homens estão juntos (o terceiro membro pode ser qualquer um dos 5 homens
restantes). Assim, temos um total de 10× 30 = 300 comitês posśıveis.
Exemplo Considere um conjunto de n antenas, indistingúıveis entre si, das quais m
estão defeituosas e n −m funcionam. Estas antenas devem ser colocadas em fila. De
quantas maneiras isto pode ser feito sem que duas antenas com defeito sejam colocadas
lado a lado?
Imagine que todas as antenas que funcionam são colocadas em fila. Para que não haja
duas antenas defeituosas lado a lado, então entre duas antenas que funcionam pode ser
http://www.ime.unicamp.br/%7Elaurarifo/ma220/lista_pascal.pdf
24 Estruturas de contagem
colocada no máximo uma antena defeituosa. O mesmo vale para as posições anterior e
posterior às antenas que funcionam.
Como temos (n−m+ 1) posições posśıveis para as antenas defeituosas, e só pode haver
no máximo uma defeituosa em cada uma destas posições, uma condição que aparece
naturalmente é que m ≤ n−m+ 1.
Pelo anterior, podemos alocar as antenas defeituosas nestas posições de
(
n−m+1
m
)
manei-
ras diferentes, indicando aqui as m posições ocupadas.
O racioćınio anterior nos leva a um novo algoritmo (com dois passos) para construir per-
mutações: primeiro selecionamos uma combinaçãode k elementos e depois selecionamos
uma ordem para estes elementos.
Teorema 1 (Teorema binomial). Sejam x, y ∈ R e n número natural. Então
(x+ y)n =
n∑
k=0
(
n
k
)
xkyn−k .
Demonstração. Podemos fazer a prova do teorema binomial por indução ou por um
argumento combinatório.
Prova por indução Quando n = 1, o lado direito da equação fica
(
1
0
)
x0y1 +
(
1
1
)
x1y0 = y + x = (x+ y)1 ,
comprovando a igualdade para n = 1.
Suponha que a equação seja válida para um certo valor de n. Assim,
(x+ y)n+1 = (x+ y) (x+ y)n
= (x+ y)
n∑
k=0
(
n
k
)
xkyn−k
=
n∑
k=0
(
n
k
)
xk+1yn−k +
n∑
k=0
(
n
k
)
xkyn+1−k .
Combinações 25
Fazendo a mudança de variável i = k + 1 na primeira soma, e i = k, na segunda, temos
(x+ y)n+1 =
n+1∑
i=1
(
n
i− 1
)
xiyn−i+1 +
n∑
i=0
(
n
i
)
xiyn+1−i
= xn+1 +
n∑
i=1
(
n
i− 1
)
xiyn−i+1 +
n∑
i=1
(
n
i
)
xiyn+1−i + yn+1
= xn+1 +
n∑
i=1
[(
n
i− 1
)
+
(
n
i
)]
xiyn−i+1 + yn+1
= xn+1 +
n∑
i=1
(
n+ 1
i
)
xiyn+1−i + yn+1
=
n+1∑
i=0
(
n+ 1
i
)
xiyn+1−i ,
o que mostra que a igualdade é válida para n+ 1, concluindo a prova por indução.
Prova por argumento combinatório Considere o produto
(x1 + y1)(x2 + y2) . . . (xn + yn) .
Sua expansão será formada pela soma de termos, cada um deles igual a um produto
contendo xi ou yi (mas não ambos), para cada i = 1, . . . , n. Por exemplo,
(x1 + y1)(x2 + y2) = x1x2 + x1y2 + y1x2 + y1y2 .
Pelo prinćıpio multiplicativo, temos um total de 2n destes termos.
Quantos destes termos contém k dos xi’s, e n− k dos yi’s?
Esta escolha corresponde a escolher k posições dentre as n, para os xi’s, ficando as
restantes para os yi’s. Temos assim
(
n
k
)
destas opções.
Fazendo xi = x e yi = y, para todo i = 1, . . . , n, temos o resultado.
Exemplo Quantos subconjuntos existem em um conjunto Ω com n elementos?
Como temos,
(
n
k
)
subconjuntos com k elementos, o total de subconjuntos é
n∑
k=0
(
n
k
)
= (1 + 1)n = 2n .
Outra forma de provar este resultado é percebendo que podemos descrever qualquer
subconjunto atribuindo 0 ou 1 a cada elemento do conjunto Ω: com 1 indicamos que o
elemento pertence ao subconjunto, e com 0, que não. Assim, pelo prinćıpio multiplica-
tivo, temos 2n possibilidades.
26 Estruturas de contagem
Se quisermos obter o total de subconjuntos não vazios de Ω, este total é simplesmente
2n − 1.
Podemos usar argumentos combinatórios para provar algumas identidades envolvendo
coeficientes binomiais.
Exemplo Mostre que, para 1 ≤ k ≤ n,(
n
k
)
=
(
n− 1
k − 1
)
+
(
n− 1
k
)
.
Consideremos um conjunto com n elementos e fixemos um deles, a, digamos.
Já sabemos que o total de maneiras de formar um subconjunto com k elementos é
(
n
k
)
,
que é o primeiro termo da igualdade anterior.
Por outro lado, podemos pensar neste total de maneiras, considerando aqueles conjuntos
que não contém o elemento a, e aqueles que o contém.
Aqueles que não contém o elemento a são formados portanto com n−1 elementos: o total
posśıvel destes conjuntos é
(
n−1
k
)
, o segundo somando do segundo termo da igualdade.
Aqueles que contém o elemento a representam o total de conjuntos de tamanho k − 1
que podem ser formados com n− 1 elementos; temos
(
n−1
k−1
)
deles.
Com isto, terminamos a prova.
Os exerćıcios desta seção mostram algumas propriedades teóricas básicas dos conceitos
definidos.
3.3 Mãos à obra
Nos exerćıcios abaixo, considere n,m, k inteiros não negativos.
Dica: antes de fazer as demonstrações, construa pelo menos um exemplo, atribuindo
valores para as quantidades envolvidas. Mais dicas para alguns dos problemas, no fim
do caṕıtulo; mas só olhe as dicas depois de ter pensado no problema.
1. Mostre que
(
n
0
)
=
(
n
n
)
= 1.
2. Mostre que se n < k então
(
n
k
)
= 0.
Mãos à obra 27
3. Utilizando argumento combinatório, mostre que(
n
k
)
=
(
n
n− k
)
,
ou seja, mostre que cada lado da igualdade representa uma forma diferente de
contar a mesma coleção.
4. Utilizando um argumento combinatório, mostre que
k
(
n
k
)
= n
(
n− 1
k − 1
)
.
5. Utilizando um argumento combinatório, mostre que(
n+m
k
)
=
k∑
j=0
(
n
j
)(
m
k − j
)
.
6. Use o exerćıcio anterior para mostrar que(
2n
n
)
=
n∑
j=0
(
n
j
)2
.
7. Utilize um argumento combinatório para mostrar que(
n
k
)
=
n∑
i=k
(
i− 1
k − 1
)
, n ≥ k .
Esta igualdade é chamada identidade combinatória de Fermat.
8. Utilize um argumento combinatório para mostrar que
n∑
k=1
k
(
n
k
)
= n 2n−1 .
9. Utilize um argumento combinatório para mostrar que
n∑
k=1
k2
(
n
k
)
= n (n+ 1) 2n−2 .
Dicas:
Exerćıcio 3: observe que ao selecionar um subconjunto de k elementos de um conjunto
de tamanho n, deixamos n− k elementos não selecionados.
Exerćıcio 4: considere duas formas de escolher um comitê de tamanho k de um grupo
de tamanho n; na primeira, o comitê é escolhido e depois um chefe dentre os escolhidos,
28 Estruturas de contagem
e na segunda, um chefe é escolhido da população e então k − 1 membros são escolhidos
do restante n− 1 membros da população.
Exerćıcio 5: considere duas formas de escolher um comitê de tamanho k de um grupo de
tamanho n+m com n homens e m mulheres; conte o número de comitês com j homens
e k − j mulheres.
Exerćıcio 7: considere o conjunto de números naturais de 1 até n. Quantos subconjuntos
de tamanho k tem i como maior elemento?
Exerćıcio 8: considere um conjunto de n pessoas e determine, de duas maneiras diferen-
tes, o total de posśıveis opções para um comitê de qualquer tamanho com um presidente.
Exerćıcio 9: considere um conjunto de n pessoas e determine, de duas maneiras diferen-
tes, o total de posśıveis opções para um comitê de qualquer tamanho com um presidente
e um secretário (que poderia acumular a função de presidente).
3.4 Amostragem
Um dos experimentos básicos e importantes em probabilidade é o de obter uma amostra
de uma população finita, o que é representado pelo experimento f́ısico de extrair objetos
da população.
Neste tipo de experimento, duas propriedades essenciais do procedimento de amostragem
devem ser bem especificadas:
• se a ordem em que os objetos são extráıdos da população é ou não importante, e
• se um objeto amostrado é ou não reposto na população antes da extração seguinte.
Consideremos uma população D = {d1, d2, . . . , dn} com n objetos, da qual queremos
obter uma amostra de k objetos, chamados unidades amostrais.
Cada uma das quatro formas posśıveis de uma amostragem será descrita com mais
detalhe a seguir.
Amostra ordenada sem reposição
Se a ordem for importante e as extrações forem feitas sem reposição, então uma amostra
de k elementos é simplesmente uma permutação de tamanho k escolhida de D. Nova-
mente, pela regra do produto, o total de amostras posśıveis é igual a n(k). Este tipo de
amostra é também chamado arranjo simples de classe k em n elementos.
Amostragem 29
Figura 3.3: Amostra de tamanho k de uma população D com n elementos.
Amostra ordenada com reposição
Se a ordem for importante e as extrações forem feitas com reposição, então uma amostra é
um elemento do produto cartesiano Dk, ou seja, uma amostra é um vetor (a1, a2, . . . , ak),
onde ai representa o i-ésimo elemento extráıdo de D.
Observemos que podemos ter coordenadas repetidas, indicando que um mesmo elemento
foi extráıdo mais de uma vez.
Neste caso, pela regra do produto, o total de amostras posśıveis de k elementos é igual
ao total de vetores posśıveis em Dk, igual a nk.
Este tipo de amostra também é chamada arranjo completo de classe k dos n elementos.
Amostra não ordenada sem reposição
Se a ordem não for importante e as extrações forem feitas sem reposição, então uma
amostra é uma combinação de k elementos de D; neste caso, o total de amostras posśıveis
é C(n, k). Este tipo de amostragem também é chamado combinação simples de k ele-mentos em n.
Amostra não ordenada com reposição
Finalmente, consideremos o caso em que a ordem não é importante e as extrações são
feitas com reposição. As posśıveis amostras podem ter apenas um elemento repetido
k vezes, ou apenas dois elementos diferentes no total de k extrações, ou apenas três
diferentes, ou assim por diante, até k elementos diferentes, não-ordenados. O total de
30 Estruturas de contagem
amostras posśıveis, neste caso, é igual a(
k + n− 1
k
)
.
Este tipo de amostra é também chamado um multiconjunto ou combinação com-
pleta de k elementos em n.
Demonstração. Para sistematizar a contagem, denotemos por xj o total de vezes em
que o j-ésimo elemento da população é observado em uma amostra, para j = 1, . . . , n.
Como observamos uma amostra de tamanho k, temos que x1 + x2 + · · ·+ xn = k.
O total de amostras posśıveis, corresponde portanto ao total de soluções inteiras não
negativas da equação anterior, nas variáveis xi´s.
Uma forma bonita de resolver este problema é via modelo de urnas e bolinhas. Consi-
deremos n urnas e k bolinhas, que serão dispostas aleatoriamente nas urnas. A equação
anterior representa este problema, com xi representando o total de bolinhas na i-ésima
urna. Uma forma de preencher as urnas corresponde a uma solução desta equação e,
portanto, a uma amostra não ordenada com reposição.
Assim, basta contar o total de formas de preencher as urnas.
Indiquemos as n urnas por n + 1 barras verticais |, de modo que os espaços entre as
barras representam cada uma das n urnas. Indiquemos as k bolinhas por k śımbolos ◦.
Por exemplo, a configuração
| | ◦ ◦ ◦ | ◦ |
representa 3 urnas: a primeira está vazia, a segunda tem 3 bolinhas e a terceira tem
uma bolinha.
Queremos contar o número de maneiras de dispor k śımbolos ◦ entre n+1 barras |. Como
a primeira e a última barras devem permanecer nos extremos (já que as bolinhas não
podem ficar fora das urnas), devemos considerar todas as combinações entre k śımbolos
◦ e n− 1 barras |.
Com isto, o total de amostras não ordenadas e com reposição de k elementos de uma
população contendo n elementos diferentes é igual a(
k + n− 1
k
)
.
Coeficientes multinomiais 31
O software Probabilidade com urnas, dispońıvel no site do projeto Matemática Mul-
timı́dia [10] trata de diversos tipos de amostragens, podendo ser utilizados como material
auxiliar com os alunos.
Para pensar: em um jogo de bingo, qual tipo de amostragem estamos realizando? e em
uma loteria?
Mãos à obra
1. Um lote contém 12 itens bons e 8 itens defeituosos. Uma amostra de 5 itens
é extráıda. Determine o total de amostras contendo exatamente 3 itens bons.
Considere cada um dos quatro tipos de amostragem definidos.
2. De 10 casais queremos selecionar um grupo de 6 pessoas, no qual a presença de
um casal não é permitida.
(a) Quantas opções existem?
(b) Se o grupo também tiver que ser formado por 3 homens e 3 mulheres, quantas
opções existem?
3. Considere um grupo formado por 7 homens e 8 mulheres, do qual devemos sele-
cionar uma amostra de 6 pessoas. Quantas amostras diferentes são posśıveis se ela
tiver que conter pelos menos 3 mulheres e pelo menos 2 homens?
4. Quantos subconjuntos de tamanho 4 do conjunto S = {1, 2, . . . , 20} contêm pelo
menos um dos elementos 1, 2, 3, 4, 5?
5. Mostre que existe uma correspondência biuńıvoca entre cada par das seguintes
coleções:
(a) multiconjuntos de tamanho k de uma população D com n elementos;
(b) sequências de 0’s e 1’s, de comprimentos n + k − 1, contendo exatamente k
valores 1’s;
(c) soluções inteiras não-negativas, (x1, . . . , xn), da equação x1 + · · ·+ xn = k.
Cada uma destas coleções tem
(
n+k−1
k
)
elementos.
3.5 Coeficientes multinomiais
Consideremos o conjunto D = {d1, d2, . . . , dn} com n elementos.
http://m3.ime.unicamp.br/portal/Midias/Softwares/SoftwaresM3Matematica/probabilidade_com_urnas/urnas/
32 Estruturas de contagem
Observemos que uma combinação de j elementos de D define uma partição de D, for-
mada por um conjunto A, contendo os j elementos da combinação, e AC , contendo os
n− j elementos restantes.
Figura 3.4: Partição de um conjunto em dois subconjuntos, com cardinalidades j e n−j.
Uma generalização natural deste conceito é o de partição de D em até k subconjuntos
diferentes e disjuntos dois a dois, {A1, A2, . . . , Ak}, com #Ai = ni ≥ 0, para todo
i = 1, 2, . . . , k, tais que n1 + n2 + · · ·+ nk = n.
Figura 3.5: Partição de um conjunto em k subconjuntos, cada um com cardinalidade
ni.
O total de partições posśıveis de D em até k subconjuntos, C(n;n1, n2, . . . , nk), é igual
a
C(n;n1, n2, . . . , nk) =
n!
n1!n2! . . . nk!
,
onde ni ≥ 0, para todo i, e
∑
ni = n. Este número é chamado coeficiente multino-
mial e é denotado também por (
n
n1, n2, . . . , nk
)
.
Demonstração. Dado o conjunto D = {d1, d2, . . . , dn} com n elementos, consideremos
uma permutação de todos os elementos
π(d1, d2, . . . , dn) = (dπ1 , dπ2 , . . . , dπn).
Coeficientes multinomiais 33
Dados n1, n2, . . . , nk inteiros não-negativos tais que n1 + n2 + · · · + nk = n, definamos
o conjunto A1 como o conjunto formado pelos primeiros n1 elementos da permutação
anterior. Definamos A2 como o conjunto formado pelos seguintes n2 elementos da per-
mutação, e assim por diante, até obter Ak definido como o conjunto formado pelos
últimos nk elementos da permutação. Se para algum i, ni = 0, tomamos o conjunto Ai
como o conjunto vazio.
Desta forma, para cada uma das n! posśıveis permutações, constrúımos os conjuntos
A1, A2, . . . , Ak da mesma maneira.
Observemos que estes conjuntos são disjuntos entre si e sua união corresponde ao con-
junto D, já que todos os elementos aparecem na permutação, e aparecem uma única
vez. Em outras palavras, os conjuntos A1, A2, . . . , Ak definem uma partição de D.
Observemos também que qualquer permutação envolvendo apenas os n1 primeiros ele-
mentos, define o mesmo conjunto A1; do mesmo modo, qualquer permutação envolvendo
apenas os n2 elementos seguintes, define o mesmo conjunto A2, e assim por diante.
Sendo assim, dada uma permutação definindo os conjuntos A1, A2, . . . , Ak, temos
n1!n2! . . . nk!
permutações diferentes definindo os mesmos conjuntos A1, A2, . . . , Ak, que são aquelas
que permutam apenas os elementos de cada conjunto entre si.
Portanto, o total de partições diferentes de D é igual a n!/(n1!n2! . . . nk!), como que-
ŕıamos provar.
Exemplo Dez crianças devem ser agrupadas em dois times A e B, com 5 crianças
cada. O time A jogará em uma liga e o time B, em outra. Quantas formações diferentes
são posśıveis? E se os times forem jogar na mesma liga?
Exemplo Consideremos o conjunto T = {1, 2, . . . , k}n. Os elementos de T são vetores
de comprimento n em que cada coordenada é um valor natural entre 1 e k, como por
exemplo os vetores
t = (1, 1, 2, 1, . . . , 1) t = (k, k, . . . , k) t = (k, 4, 5, k, 4, 5, . . . , 5), etc.
Para cada valor i ∈ {1, 2, . . . , k}, denotemos por ni o total de vezes em que o valor i
aparece no vetor t.
Por exemplo, se n = 3 e k = 5, T é o conjunto de todos os vetores com três coordenadas,
onde cada coordenada é um valor inteiro entre 1 e 5. Para o vetor t = (3, 3, 2), temos
34 Estruturas de contagem
que n1 = 0 = n4 = n5, já que os valores 1, 4 e 5 não aparecem no vetor, e n2 = 1 e
n3 = 2, já que o valor 2 aparece uma vez e o valor 3 aparece duas vezes.
Com esta definição, podemos perceber que a soma n1 +n2 + · · ·+nk deve ser igual a n,
que é o total de coordenadas do vetor t.
Então, o total de seqüências em T tais que o valor i ocorre ni vezes, para i = 1, 2, . . . , k,
é igual a C(n;n1, n2, . . . , nk).
Demonstração. Para provar o resultado, consideremos um conjunto D = {d1, d2, . . . , dn}
com n elementos.
Observemos que cada t ∈ T = {1, 2, . . . , k}n define umapartição de D.
De fato, para cada vetor t = (t1, t2, . . . , tn) ∈ T , definamos os conjuntos A1, A2, . . . , Ak
de modo que o elemento di ∈ D pertença ao conjunto Ati , dado pela coordenada i-ésima
de t. Se o vetor t não tiver nenhuma coordenada com valor igual a j ∈ {1, 2, . . . , k},
então Aj = ∅.
Esta relação define biunivocamente cada partição de D a partir de t ∈ T . Portanto, o
total de elementos em T é igual ao total de partições de D em até k conjuntos.
Com este resultado, no exemplo anterior temos que o total de seqüências de 3 elementos
de {1, 2, 3, 4, 5}, formada por um 2 e dois 3’s (e nenhum 1, 4 ou 5) é igual a
C(3; 0, 1, 2, 0, 0) =
(
3
0, 1, 2, 0, 0
)
=
3!
0! 1! 2! 0! 0!
=
3 · 2 · 1
2
= 3,
e são elas: (3, 3, 2), (3, 2, 3), (2, 3, 3).
Exemplo Consideremos n objetos de k tipos diferentes, k ≤ n, com ni elementos do
tipo i, para cada i = 1, 2, . . . , n. Por exemplo, 5 cadeiras, 2 azuis, 1 branca, 1 preta e 1
verde.
Admitindo que objetos de um mesmo tipo são indistingúıveis entre si, então o total de
permutações distingúıveis dos n objetos é igual a C(n;n1, n2, . . . , nk).
Observemos que cada permutação distingúıvel destes objetos corresponde a um único
elemento de T do exemplo anterior, e cada elemento de T define uma única permutação
distingúıvel, provando assim o resultado.
No exemplo das cadeiras, temos portanto C(5; 2, 1, 1, 1) = 60 formas diferentes de colocar
as cadeiras em linha.
Coeficientes multinomiais 35
Podemos verificar isto, contando da seguinte maneira: chamemos por 1, 2, 3, 4, 5 as
posśıveis posições de cada cadeira.
As cadeiras azuis podem ser vizinhas nas posições 1-2, 2-3, 3-4, 4-5. Para cada uma
destas, as outras 3 cadeiras podem ser ordenadas de 3!=6 formas diferentes.
Do mesmo modo, as cadeiras azuis podem estar a uma cadeira de distância nas posições
1-3, 2-4, 3-5; a duas cadeiras de distância, nas posições 1-4, 2-5; e totalmente afastadas
na posição 1-5. Para cada uma destas possibilidade, temos 3! formas de ordenar as
restantes.
Assim, temos 3!(4 + 3 + 2 + 1) = 60 posśıveis ordenações distingúıveis.
O seguinte resultado generaliza o Teorema binomial e sua demonstração segue analoga-
mente.
Teorema 2 (Teorema multinomial). Sejam x1 . . . , xr ∈ R e n número natural. Então
(x1 + · · ·+ xr)n =
∑( n
n1, . . . , nr
)
xn11 . . . x
nr
r ,
com soma definida no conjunto dos vetores (n1, . . . , nr) com valores inteiros não nega-
tivos tais que n1 + · · ·+ nr = n.
Mãos à obra
1. Em uma corrida com 10 cavalos, os três primeiros lugares são anotados. Quantos
resultados posśıveis existem?
2. Uma placa de carro tem 3 letras e 4 d́ıgitos. Determine o total de placas com
letras e d́ıgitos todos diferentes.
3. Quatro casais estão sentados em uma fileira com 8 cadeiras. Determine o total de
arranjos em que eles podem estar sentados. Determine o total de arranjos em que
eles podem estar sentados de modo que:
(a) os homens fiquem juntos e as mulheres fiquem juntas;
(b) os homens fiquem juntos;
(c) os casais fiquem juntos.
4. Refaça o exerćıcio anterior, assumindo agora que os casais estão sentados em uma
mesa redonda.
36 Estruturas de contagem
5. Em uma estante há 12 livros, dos quais 3 são de f́ısica, 5 são de matemática e 4
são de história. Determine o total de arranjos de modo que:
(a) não há restrição;
(b) os livros de mesmo tipo devem ficar juntos;
(c) os livros de matemática devem ficar juntos.
6. Determine o total de arranjos diferentes das letras de: probabilidade, arranjo.
7. Um clube tem 20 membros: 12 homens e 8 mulheres, com os quais é necessário
criar um comitê de 6 pessoas. De quantas formas pode ser composto o comitê se:
(a) não há restrição;
(b) o comitê deve ter 4 mulheres e 2 homens;
(c) o comitê deve ter pelo menos 2 mulheres e pelo menos 2 homens.
8. Em um grupo de 10 pessoas, todas elas se apertam as mãos uma vez. Quantos
apertos de mão são dados?
9. De quantos modos podemos formar uma roda com 5 crianças?
10. De quantos modos podemos distribuir 8 pessoas em dois grupos de 4 pessoas cada?
Dica: a distribuição pode ser feita colocando as 8 pessoas em fila, atribuindo os 4
primeiros para um dos grupos.
11. De quantas formas podemos distribuir 12 pessoas:
(a) em dois grupos de 6?
(b) em três grupos de 4?
(c) em um grupo de 5 e um grupo de 7?
(d) em seis grupos de 2?
(e) em dois grupos de 4 e dois grupos de 2?
12. Suponha que 5 dados distingúıveis de 6 faces são lançados e que a seqüência obtida
é observada. Determine o total de seqüências. Determine o total de seqüências
com todos os resultados diferentes.
13. Refaça o exerćıcio anterior, assumindo que os dados são idênticos.
14. Um sinal será formado usando nove bandeiras alinhadas, sendo 4 brancas, 3 ver-
melhas e 2 azuis. Bandeiras da mesma cor são indistingúıveis. Quantos sinais
diferentes podem ser formados?
Coeficientes multinomiais 37
15. Considere dois pontos na malha inteira Z× Z, A = (0, 0) e B = (4, 3), e suponha
que uma part́ıcula se move na malha somente para cima ou para a direita.
(a) Quantos caminhos existem para esta part́ıcula entre A e B?
(b) Quantos destes caminhos passam pelo ponto C = (2, 2)?
16. Determine o total de vetores (x1, . . . , xn) ∈ {0, 1}n tais que
∑
xi = k (responda
em função de k).
17. Determine o total de vetores (x1, . . . , xk) ∈ {1, . . . , n}k tais que x1 < x2 < · · · <
xk.
18. Delegados de 10 páıses devem se sentar em 10 cadeiras em fila. De quantos modos
isso pode ser feito se os delegados do Brasil e de Portugal devem se sentar juntos
e o da Arábia Saudita e o dos Estados Unidos não podem sentar juntos?
19. Um cubo de madeira tem uma face de cada cor. Quantos dados diferentes podemos
formar gravando números de 1 a 6 sobre essas faces?
20. Quantos dados diferentes podemos formar gravando números de 1 a 6 sobre as
faces indistingúıveis de um cubo de madeira?
21. Resolva o problema anterior para:
(a) números de 1 a 4, tetraedro regular;
(b) números de 1 a 8, octaedro regular;
(c) números de 1 a 12, dodecaedro regular;
(d) números de 1 a 20, icosaedro regular;
(e) números 1 a 8, prisma hexagonal regular;
(f) números de 1 a 5, pirâmide quadrangular regular.
22. Temos 5 pontos sobre uma reta R e 8 pontos sobre uma reta R′, paralela a R.
Quantos quadriláteros convexos com vértices em 4 desses 13 pontos existem?
23. Em um torneio no qual cada participante enfrenta todos os demais uma única vez,
são jogadas 780 partidas. Quantos são os participantes?
24. Considere os conjuntos Im = {1, . . . ,m} e In = {1, . . . , n}, com m ≤ n. Quantas
são as funções f : Im → In, estritamente crescentes?
25. Quantos são os números naturais de 7 d́ıgitos nos quais o d́ıgito 4 aparece exata-
mente 3 vezes e o d́ıgito 8, exatamente 2 vezes?
38 Estruturas de contagem
26. Quantos são os números naturais de 7 d́ıgitos nos quais o d́ıgito 4 aparece pelo
menos 3 vezes e o d́ıgito 8, pelo menos 2 vezes?
27. Quantos são os p-conjuntos (isto é, subconjuntos com p elementos) de {a1, . . . , an}
nos quais:
(a) a1 aparece;
(b) a1 não aparece;
(c) a1 e a2 aparecem;
(d) pelo menos um dos elementos a1, a2 aparece;
(e) exatamente um dos elementos a1, a2 aparece.
28. Um conjunto A possui p elementos e o conjunto B, n elementos. Determine o
número de funções f : A → B sobrejetoras para: (a) p = n; (b) p = n + 1; (c)
p = n+ 2.
29. Nove cientistas trabalham em um projeto sigiloso. Por questões de segurança, os
planos são guardados em um cofre protegido por muitos cadeados de modo que só
é posśıvel abŕı-los todos se houver pelo menos 5 cientistas presentes.
(a) Qual é o número mı́nimo posśıvel de cadeados?
(b) Na situação do item (a), quantas chaves cada cientista deve ter?
30. Formam-se as combinações com p elementos extráıdos de a1, . . . , a12, as quais
são escritas com os elementos em ordem crescente de ı́ndices. Quantassão as
combinações nas quais o elementos a8 ocupa o 3o lugar?
31. O conjunto A possui n elementos. Determine o número de relações que podem ser
constrúıdas em A:
(a) sem nenhuma outra condição;
(b) que sejam refexivas;
(c) que sejam simétricas;
(d) que sejam anti-simétricas;
(e) que sejam reflexivas e simétricas;
(f) que sejam reflexivas e anti-simétricas;
(g) que sejam simétricas e anti-simétricas;
(h) que sejam reflexivas, simétricas e anti-simétricas.
32. De quantos modos se pode iluminar uma sala que tem m lâmpadas?
33. Em uma escola, x professores se distribuem em 8 bancas examinadoras, de modo
que cada professor participa de exatamente duas bancas e quaisquer duas bancas
Coeficientes multinomiais 39
têm exatamente um professor em comum.
(a) calcule x;
(b) determine quantos professores tem em cada banca.
34. Prove que um produto de p inteiros consecutivos é sempre diviśıvel por p!.
35. Prove, usando um argumento combinatório, que os números abaixo são inteiros
para qualquer n natural:
(a) (2n)!/2n; (b) (3n)!/(2n3n); (c) (3n)!/(n! 2n3n);
(d) (n2)!/(n!)n+1; (e) (n!)!/(n!)n−1.
36. C(1000, 500) é diviśıvel por 7?
37. Qual é o número de soluções inteiras e não negativas da equação x+ y + z = 5?
38. De quantos modos podemos comprar 3 refrigerantes em uma loja onde há 5 tipos
de refrigerantes?
39. Quantas são as soluções inteiras e não negativas da inequação x+ y + z ≤ 5?
40. Quantas são as soluções inteiras da equação x + y + z = 20, com x ≥ 2, y ≥ 2,
z ≥ 2?
41. Quantas são as soluções inteiras não negativas de
x1 + x2 + · · ·+ x6 = 20 ,
nas quais exatamente 3 incógnitas são nulas? Em quantas pelo menos 3 são nulas?
42. Quantas são as soluções inteiras não negativas de x + y + z + w = 20, nas quais
x > y?
43. Quantos números inteiros entre 1 e cem mil têm a soma dos algarismos igual a 6?
44. No experimento do tabuleiro de Galton (clique aqui),
(a) mova a part́ıcula de (0, 0) até (10, 6), pelo caminho que você quiser.
(b) gere a sequência 0011101001. Note o subconjunto e o caminho corresponden-
tes;
(c) gere o subconjunto {1, 4, 5, 7, 8, 10}. Note a sequência de bits e caminho cor-
respondentes;
(d) gere todos os caminhos de (0, 0) até (5, 3). Quantos tem?
http://www.math.uah.edu/stat/applets/GaltonBoardGame.html
40 Estruturas de contagem
Bibliografia
[1] Morgado, A.C.O., de Carvalho, J.B.P., Carvalho, P.C.P., Fernandez, P. (2006, 9a
ed.) Análise Combinatória e Probabilidade. Coleção do Professor de Matemática,
Editora SBM.
[2] Feller, P. (1976) Introdução à Teoria de Probabilidades e suas Aplicações. Editora
Edgard Blücher.
[3] Gnedenko, B. (2008) A Teoria da Probabilidade. Editora Ciência Moderna.
[4] Halmos, P. (2001) Teoria Ingênua dos Conjuntos. Editora Ciência Moderna.
[5] James, B. (1996) Probabilidade: um curso em ńıvel intermediário. Coleção Projeto
Euclides.
[6] Meyer, P. (2000) Probabilidade: aplicações à estat́ıstica. Editora LTC.
[7] Ross, S. (2010) Probabilidade: um curso moderno com aplicações. Editora Bookman
Co.
Páginas da internet
Em português
[8] ALEA, Acção Local de Estat́ıstica Aplicada, Portugal.
[9] Mais - Recursos Educacionais em Matemática, Brasil.
[10] Matemática Multimı́dia, Unicamp.
Em inglês
[11] História da Matemática, Universidade de St. Andrews, Escócia.
[12] Laboratório de Probabilidade e Estat́ıstica, Universidade do Alabama, EUA.
http://alea-estp.ine.pt/
http://www.mais.mat.br/recursos.html
http://www.m3.ime.unicamp.br/portal/
http://www-groups.dcs.st-and.ac.uk/~history/
http://www.math.uah.edu/stat/index.xhtml
	Elementos da teoria de conjuntos
	Conjuntos
	Relações entre conjuntos
	Coleções de conjuntos
	Produto cartesiano
	Mãos à obra
	Medida de contagem
	Princípio da adição
	Algumas desigualdades
	Desigualdade de Boole
	Desigualdade de Bonferroni
	Princípio de inclusão-exclusão
	Princípio da multiplicação
	Mãos à obra
	Estruturas de contagem
	Permutações
	Combinações
	Mãos à obra
	Amostragem
	Amostra ordenada sem reposição
	Amostra ordenada com reposição
	Amostra não ordenada sem reposição
	Amostra não ordenada com reposição
	Mãos à obra
	Coeficientes multinomiais
	Mãos à obra