ANÁLISE COMBINATÓRIA, PROBABILIDADE E NOÇÕES DE ESTATÍSTICA - LAULA RIFO

Prévia do material em texto

Universidade Estadual de Campinas
Mo´dulo III - D6
Ana´lise Combinato´ria, Probabilidade
Noc¸o˜es de Estat´ıstica
Tema 1 - Elementos da Teoria de Conjuntos
Prof. Laura L. R. Rifo
- Novembro, 2010 -
Suma´rio
1 Elementos da teoria de conjuntos 1
1.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Relac¸o˜es entre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Colec¸o˜es de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Produto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Medida de contagem 5
2.1 Regra da soma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Algumas desigualdades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Desigualdade de Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Desigualdade de Bonferroni . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Fo´rmula de inclusa˜o-exclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Regra do produto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Estruturas de contagem 9
3.1 Permutac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Combinac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Amostras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Amostra ordenada com reposic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 12
Amostra ordenada sem reposic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 12
Amostra na˜o ordenada sem reposic¸a˜o . . . . . . . . . . . . . . . . . . . . 12
Amostra na˜o ordenada com reposic¸a˜o . . . . . . . . . . . . . . . . . . . 13
ii Suma´rio
3.4 Coeficientes multinomiais . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Exemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Exemplo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A Exerc´ıcios 17
A.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
A.2 Medida de Contagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
A.3 Estruturas de contagem . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Amostras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Coeficientes multinomiais . . . . . . . . . . . . . . . . . . . . . . . . . . 20
B Demonstrac¸o˜es 23
B.1 Desigualdade de Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
B.2 Desigualdade de Bonferroni . . . . . . . . . . . . . . . . . . . . . . . . . 24
B.3 Fo´rmula de inclusa˜o-exclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . 24
B.4 Amostragem na˜o-ordenada sem reposic¸a˜o . . . . . . . . . . . . . . . . . 24
B.5 Coeficientes multinomiais . . . . . . . . . . . . . . . . . . . . . . . . . . 25
B.6 Coeficientes multinomiais - Exemplo 1 . . . . . . . . . . . . . . . . . . . 26
Cap´ıtulo 1
Elementos da teoria de conjuntos
1.1 Conjuntos
A teoria de conjuntos e´ a base para toda a probabilidade e estat´ıstica, assim como de
outras a´reas da matema´tica. Nesta sec¸a˜o, faremos uma pequena revisa˜o do material
necessa´rio para este mo´dulo.
Lembremos que um conjunto e´ uma colec¸a˜o de objetos, chamados os elementos do con-
junto. A afirmac¸a˜o de que s e´ um elemento do conjunto A e´ escrita como s ∈ A.
Por definic¸a˜o, um conjunto fica completamente determinado por seus elementos; em
particular dois conjuntos A e B sa˜o iguais se eles tiverem os mesmos elementos:
A = B se e somente se (s ∈ A ⇐⇒ s ∈ B) .
Se a A e B sa˜o conjuntos, enta˜o A e´ um subconjunto de B se todo elemento de A for
tambe´m elemento de B:
A ⊂ B se e somente se (s ∈ A⇒ s ∈ B) .
Figura 1.1: Diagrama de Euler-Venn para dois conjuntos, A ⊂ B.
Podemos representar conjuntos e relac¸o˜es entre eles com desenhos esquema´ticos chama-
dos diagramas de Euler - Venn. O diagrama da Figura 1.1 por exemplo representa a
relac¸a˜o de subconjunto.
2 Elementos da teoria de conjuntos
Trabalharemos usualmente com conjuntos que sera˜o todos subconjuntos de um conjunto
espec´ıfico Ω, chamado conjunto universo. Definimos tambe´m o conjunto vazio, denotado
por ∅, como o conjunto sem elementos.
Consideremos um predicado q(s), ou seja, uma afirmac¸a˜o matema´tica que ou e´ ver-
dadeira ou e´ falsa para cada elemento s ∈ Ω. Enta˜o {s ∈ Ω : q(s) e´ verdadeira} define
completamente um subconjunto de Ω: o conjunto de todos os elementos de Ω que satis-
fazem q(s).
1.2 Relac¸o˜es entre conjuntos
Lembremos que as operac¸a˜o ba´sicas em teoria de conjuntos permitem definir novos con-
juntos. Mais precisamente, sejam A e B subconjuntos de um mesmo conjunto universo,
Ω. Enta˜o definimos a unia˜o entre A e B, como o conjunto que combina os elementos de
A e B,
A ∪B = {s ∈ Ω : s ∈ A ou s ∈ B}.
A intersec¸a˜o de A e B e´ o conjunto dos elementos em comum entre A e B,
A ∩B = {s ∈ Ω : s ∈ A e s ∈ B}.
A diferenc¸a de conjuntos de B e A e´ o conjunto dos elementos que esta˜o em B mas na˜o
em A,
B \A = {s ∈ Ω : s ∈ B e s /∈ A}.
O complementar de A e´ o conjunto de elementos que na˜o esta˜o em A,
AC = {s ∈ Ω : s /∈ A}.
Dizemos que os conjuntos A e B sa˜o disjuntos se sua intersec¸a˜o for o conjunto vazio,
A ∩B = ∅.
Uma discussa˜o mais aprofundada de teoria de conjuntos pode ser encontrada no livro
cla´ssico de Halmos [4]. O projeto Laborato´rio de Probabilidade e Estat´ıstica da Univer-
sidade do Alabama [12] disponibiliza um applet sobre o diagrama de Euler-Venn para
visualizar as poss´ıveis relac¸o˜es entre dois conjuntos (deve ser usado o navegador Mozilla).
Colec¸o˜es de conjuntos 3
1.3 Colec¸o˜es de conjuntos
Podemos estender as relac¸o˜es anteriores para colec¸o˜es finitas ou infinitas de conjuntos.
Seja A uma colec¸a˜o de subconjuntos de Ω. Podemos indexar os subconjuntos em A por
um conjunto de ı´ndices I, escrevendo assim A = {Ai ⊂ Ω : i ∈ I}.
A unia˜o da colec¸a˜o A e´ 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 intersec¸a˜o da colec¸a˜o A e´ 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 conjuntos a partir de uma colec¸a˜o.
Figura 1.2: Diagrama de Euler-Venn para a unia˜o e a intersec¸a˜o de uma colec¸a˜o de
conjuntos.
A colec¸a˜o A e´ disjunta dois a dois se a intersec¸a˜o de quaisquer dois conjuntos da colec¸a˜o
for vazia,
A ∩B = ∅ para quaisquer A ∈ A e B ∈ A , com A 6= B.
Dizemos que a colec¸a˜o A forma uma partic¸a˜o de um conjunto B se A for disjunta dois
a dois e
⋃A = B.
Dado um conjunto Ω, uma colec¸a˜o importante e´ a colec¸a˜o de todos os subconjuntos de
Ω, chamado o conjunto das partes de Ω, que denotaremos por P(Ω) ou 2Ω.
4 Elementos da teoria de conjuntos
1.4 Produto cartesiano
Consideremos os conjuntos Ω1,Ω2, . . . ,Ωn. Definimos o produto cartesiano como o con-
junto
Ω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 definic¸a˜o para uma sequ¨eˆncia infinita de conjuntos (Ω1,Ω2, . . . )
como
Ω1 × Ω2 × · · · = {(s1, s2, . . . ) : si ∈ Ωi para todo i ∈ {1, 2, . . . }}.
Denotaremos os elementos de um produto cartesiano com a notac¸a˜o vetorial
(s1, s2, . . . , sn)
ou simplesmente como letras de uma palavra s1s2 . . . sn.
O experimento A matema´tica dos calenda´rios, dispon´ıveis no site do projeto Matema´tica
Multimı´dia [10] tratam de conjuntos em geral e de conjuntos nume´ricos, emparticular,
podendo ser utilizados como material auxiliar com os alunos.
Ma˜os a` obra. Exerc´ıcios A.1.
Cap´ıtulo 2
Medida de contagem
Suponhamos que Ω e´ um conjunto finito.
Se A ⊂ Ω enta˜o a cardinalidade de A e´ o nu´mero de elementos de A, e sera´ denotado por
#(A) ou simplesmente #A. A func¸a˜o # e´ chamada medida de contagem e e´ fundamental
na teoria de probabilidades discretas.
Em particular, quando trabalhamos com problemas envolvendo amostragens de um con-
junto finito, o conjunto Ω e´ tipicamente um conjunto grande, o que nos leva a` necessidade
de construir formas eficientes de contagem.
Uma das regras ba´sicas da contagem e´ o axioma de aditividade da medida de contagem,
mais conhecido como regra da soma.
2.1 Regra da soma
Seja A1, A2, . . . , An uma colec¸a˜o finita de subconjuntos disjuntos de Ω. Enta˜o
#
(⋃
i
Ai
)
=
∑
i
#(Ai).
Uma consequ¨eˆncia imediata desta propriedade e´ que dados dois conjuntos A e B tais
que A ⊂ B enta˜o #A ≤ #B. Desta forma, # e´ uma func¸a˜o crescente relativa a` ordem
parcial dos subconjuntos de Ω e a` ordem usual em R.
2.2 Algumas desigualdades
As seguintes desigualdades nos permitem obter limitantes para o nu´mero de elementos
de um conjunto.
6 Medida de contagem
Desigualdade de Boole
Seja A1, A2, . . . , An uma colec¸a˜o finita de subconjuntos disjuntos de Ω. Enta˜o
#
(⋃
i
Ai
)
≤
∑
i
#(Ai).
Veja a prova B.1.
Em palavras, se n = 2, o total de elementos da unia˜o de dois conjuntos e´ menor ou
igual que a soma dos totais de elementos de cada conjunto, ja´ que se houver intersec¸a˜o
na˜o-vazia, contaremos os elementos da intersec¸a˜o duas vezes.
Desigualdade de Bonferroni
Seja A1, A2, . . . , An uma colec¸a˜o finita de subconjuntos disjuntos de Ω. Enta˜o
#
(⋂
i
Ai
)
≥ #Ω−
∑
i
(#Ω−#Ai) .
Veja a prova B.2, que e´ uma consequ¨eˆncia da Desigualdade de Boole e da lei de De
Morgan.
2.3 Fo´rmula de inclusa˜o-exclusa˜o
Dados A,B ⊂ Ω,
#(A ∪B) = #A+ #B −#(A ∩B).
Veja a prova B.3.
Esta fo´rmula nos da´ o total exato de elementos de uma unia˜o, indicando que devemos so-
mar os totais de elementos de cada conjunto e subtrair o total de elementos da intersec¸a˜o
(que foram contados duas vezes).
Este resultado pode ser estendido para mais de dois elementos, 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.1.
Regra do produto 7
Figura 2.1: Diagrama de Euler-Venn para 3 conjuntos.
2.4 Regra do produto
A regra do produto em contagem se baseia na formulac¸a˜o de um procedimento ou algo-
ritmo que permita gerar os objetos que devem ser contados. Suponha que o procedimento
consiste em k passos, a serem realizados sucessivamente, e que cada passo j pode ser
realizado de nj formas diferentes, independentemente das escolhas feitas previamente.
Enta˜o o nu´mero total de formas de realizar o procedimento e´ igual a n1 n2 . . . nk, que e´
tambe´m o nu´mero total de poss´ıveis objetos.
Podemos visualizar este algoritmo em uma a´rvore de contagem. Consideremos uma
a´rvore com k n´ıveis de galhos, de modo que cada galho do n´ıvel i − 1 se divida em ni
novos galhos, para i = 1, . . . , k, como mostrado na Figura 2.2.
O total de nodos no extremo da a´rvore e´ igual a n1 n2 . . . nk.
Em particular, se em cada passo do algoritmo tivermos o mesmo nu´mero de possibili-
dades, n, enta˜o o procedimento completo pode ser realizado de nk maneiras poss´ıveis.
Exemplo. A placa de um carro consiste em 3 letras e 4 d´ıgitos. Quantas placas diferentes
podem ser licenciadas?
O fundamental para a correta aplicac¸a˜o desta regra em um problema de contagem e´
fazer uma formulac¸a˜o clara do algoritmo que gera os diversos poss´ıveis objetos, de modo
que cada objeto seja contado e que seja contado uma u´nica vez.
Os exerc´ıcios ao fim desta sec¸a˜o sa˜o importantes para perceber diferentes abordagens
desta regra.
O v´ıdeo Desejos e o software Geometria do Ta´xi, dispon´ıveis no site do projeto Mate-
ma´tica Multimı´dia [10] tratam de algumas regras de contagem, podendo ser utilizados
como material auxiliar com os alunos.
8 Medida de contagem
Figura 2.2: Diagrama de a´rvore de contagem.
Uma refereˆncia bibliogra´fica cla´ssica e´ o livro de Feller [2], que aborda este to´pico nos
primeiros cap´ıtulos, com problemas que sa˜o verdadeiros desafios.
Ma˜os a` obra. Exerc´ıcios A.2.
Cap´ıtulo 3
Estruturas de contagem
A definic¸a˜o de um algoritmo para gerar os elementos de um conjunto permite determinar
uma estrutura de contagem. Veremos aqui duas estruturas ba´sicas: permutac¸o˜es e
combinac¸o˜es.
3.1 Permutac¸o˜es
Consideremos um conjunto D = {d1, d2, . . . , dn} com n elementos. Uma permutac¸a˜o de
k elementos de D e´ uma sequ¨eˆ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 na˜o pode ser maior que n. Uma permutac¸a˜o de n elementos de D, ou seja,
uma ordenac¸a˜o de todos os elementos de D, e´ chamada simplesmente uma permutac¸a˜o
de D.
Podemos interpretar uma permutac¸a˜o de k elementos de D como um resultado de um
mecanismo f´ısico que extrai k elementos da populac¸a˜o D sem reposic¸a˜o.
Com esta interpretac¸a˜o, observemos que na primeira extrac¸a˜o, temos todos os n elemen-
tos de D como poss´ıveis resultados. Para a segunda extrac¸a˜o, como o primeiro elemento
extra´ıdo na˜o e´ reposto, temos n−1 poss´ıveis resultados. Para a terceira extrac¸a˜o, temos
n − 2 poss´ıveis resultados. Assim por diante, ate´ a k-e´sima extrac¸a˜o, em que temos
n− k + 1 poss´ıveis resultados, como mostra a Figura 3.1.
Assim, pela regra do produto, temos que o total de permutac¸o˜es de k elementos em n,
que denotaremos n(k), e´ igual a
n(k) = n(n− 1) . . . (n− k + 1) = n!
(n− k)! ,
10 Estruturas de contagem
Figura 3.1: A´rvore de contagem para uma permutac¸a˜o de k elementos em n.
onde n! = n(n− 1) . . . 1 e´ o fatorial de n.
Usaremos a regra do produto e o mecanismo de extrac¸a˜o como um algoritmo de con-
struc¸a˜o de permutac¸o˜es de k elementos de D para contar o total de poss´ıveis per-
mutac¸o˜es.
3.2 Combinac¸o˜es
Consideremos um conjunto D = {d1, d2, . . . , dn} com n elementos. Uma combinac¸a˜o de
k elementos de D e´ um subconjunto (na˜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 na˜o pode ser maior que n.
Podemos interpretar uma combinac¸a˜o como o resultado do mecanismo f´ısico que extrai
uma amostra na˜o-ordenada de uma populac¸a˜o D sem reposic¸a˜o.
Denotemos por C(n, k) o total de combinac¸o˜es de k elementos de um grupo de n.
Observemos que cada combinac¸a˜o permite construir k! ordenac¸o˜es diferentes, ou seja,
k! permutac¸o˜es de comprimento k.
Amostras 11
Figura 3.2: Uma combinac¸a˜o de k elementos gera k! permutac¸o˜es desses elementos.
Isto nos permite obter o total de combinac¸o˜es poss´ıveis de k elementos a partir do total
de permutac¸o˜es de k elementos, ja´ que
n(k) = k!C(n, k) =⇒ C(n, k) = n
(n− k)!k! =
(
n
k
)
.
O nu´mero
(
n
k
)
e´ chamado coeficiente binomial.
Note que se n e k sa˜o inteiros na˜o negativos e k > n, enta˜o
(
n
k
)
= 0. Por convenc¸a˜o,
definimos
(
n
k
)
= 0, se k < 0.
O racioc´ınio anterior nos leva a um novo algoritmo (com dois passos) para construir per-
mutac¸o˜es: primeiro selecionamos uma combinac¸a˜o de k elementos e depois selecionamos
uma ordem para estes elementos.
Os exerc´ıcios desta sec¸a˜o mostram algumas propriedades ba´sicas dos conceitos definidos.
Ma˜os a` obra. Exerc´ıcios A.3.
3.3 AmostrasUm dos experimentos ba´sicos e importantes em probabilidade e´ o de obter uma amostra
de uma populac¸a˜o finita.
Neste tipo de experimento, duas propriedades da amostragem sa˜o essenciais:
• se a ordem e´ ou na˜o importante, e
• se um objeto amostrado e´ ou na˜o reposto na populac¸a˜o antes da pro´xima extrac¸a˜o.
12 Estruturas de contagem
Figura 3.3: Amostra de tamanho k de uma populac¸a˜o D com n elementos.
Consideremos uma populac¸a˜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 poss´ıveis de amostragens sera´ descrita com mais detalhe
a seguir.
Amostra ordenada com reposic¸a˜o
Se a ordem for importante e as extrac¸o˜es forem feitas com reposic¸a˜o, enta˜o uma amostra e´
um elemento do produto cartesiano Dk, ou seja, uma amostra e´ um vetor (a1, a2, . . . , ak),
onde ai representa o i-e´simo elemento extra´ıdo de D.
Observemos que podemos ter coordenadas repetidas, indicando que um mesmo elemento
foi extra´ıdo mais de uma vez.
Neste caso, pela regra do produto, o total de amostras poss´ıveis de k elementos e´ igual
ao total de vetores poss´ıveis em Dk, igual a nk.
Amostra ordenada sem reposic¸a˜o
Se a ordem for importante e as extrac¸o˜es forem feitas sem reposic¸a˜o, enta˜o uma amostra
de k elementos e´ simplesmente uma permutac¸a˜o de tamanho k escolhida de D. Nova-
mente, pela regra do produto, o total de amostras poss´ıveis e´ igual a n(k).
Amostra na˜o ordenada sem reposic¸a˜o
Se a ordem na˜o for importante e as extrac¸o˜es forem feitas sem reposic¸a˜o, enta˜o uma
amostra e´ uma combinac¸a˜o de k elementos de D; neste caso, o total de amostras poss´ıveis
Coeficientes multinomiais 13
e´ C(n, k).
Amostra na˜o ordenada com reposic¸a˜o
Finalmente, consideremos o caso em que a ordem na˜o e´ importante e as extrac¸o˜es sa˜o
feitas com reposic¸a˜o. As poss´ıveis amostras podem ter apenas um elemento repetido
k vezes, ou apenas dois elementos diferentes no total de k extrac¸o˜es, ou apenas treˆs
diferentes, ou assim por diante, ate´ k elementos diferentes, na˜o-ordenados. O total de
amostras poss´ıveis, neste caso, e´ igual a(
k + n− 1
k
)
.
Veja a prova B.4.
O software Probabilidade com urnas, dispon´ıveis no site do projeto Matema´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?
Ma˜os a` obra. Exerc´ıcios A.3.
3.4 Coeficientes multinomiais
Consideremos o conjunto D = {d1, d2, . . . , dn} com n elementos.
Observemos que uma combinac¸a˜o de j elementos de D define uma partic¸a˜o de D, for-
mada por um conjunto A, contendo os j elementos da combinac¸a˜o, e AC , contendo os
n− j elementos restantes.
Figura 3.4: Partic¸a˜o de um conjunto em dois subconjuntos, com cardinalidades j e n−j.
14 Estruturas de contagem
Uma generalizac¸a˜o natural deste conceito e´ o de partic¸a˜o de D em ate´ 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: Partic¸a˜o de um conjunto em k subconjuntos, cada um com cardinalidade
nk.
O total de partic¸o˜es poss´ıveis de D em ate´ k subconjuntos, C(n;n1, n2, . . . , nk), e´ igual
a
C(n;n1, n2, . . . , nk) =
n!
n1!n2! . . . nk!
.
Veja a prova B.5.
Este nu´mero e´ chamado coeficiente multinomial e e´ denotado tambe´m por(
n
n1, n2, . . . , nk
)
.
Exemplo 1
Consideremos o conjunto T = {1, 2, . . . , k}n. Os elementos de T sa˜o vetores de compri-
mento n em que cada coordenada e´ 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 e´ o conjunto de todos os vetores com treˆs coordenadas,
onde cada coordenada e´ um valor inteiro entre 1 e 5. Para o vetor t = (3, 3, 2), temos
que n1 = 0 = n4 = n5, ja´ que os valores 1, 4 e 5 na˜o aparecem no vetor, e n2 = 1 e
n3 = 2, ja´ que o valor 2 aparece uma vez e o valor 3 aparece duas vezes.
Com esta definic¸a˜o, podemos perceber que a soma n1 +n2 + · · ·+nk deve ser igual a n,
que e´ o total de coordenadas do vetor t.
Coeficientes multinomiais 15
Enta˜o, o total de sequ¨eˆncias em T tais que o valor i ocorre ni vezes, para i = 1, 2, . . . , k,
e´ igual a C(n;n1, n2, . . . , nk).
Veja a prova B.6.
Com este resultado, no exemplo anterior temos que o total de sequ¨eˆncias de 3 elementos
com um 2 e dois 3’s (e nenhum 1, 4 ou 5) e´ 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,
que sa˜o (3, 3, 2), (3, 2, 3), (2, 3, 3).
Exemplo 2
Consideremos n objetos de k tipos diferentes, k ≤ n, com ni elementos do tipo i, para
cada i = 1, 2, . . . , n.
Por exemplo, Joa˜o tem 5 cadeiras, 2 azuis, 1 branca, 1 preta e 1 verde.
Admitindo que objetos de um mesmo tipo sa˜o indistingu´ıveis entre si, enta˜o o total de
permutac¸o˜es distingu´ıveis dos n objetos e´ igual a C(n;n1, n2, . . . , nk).
Observemos que cada permutac¸a˜o distingu´ıvel destes objetos corresponde a um u´nico el-
emento T do Exemplo 1, e cada elemento de T define uma u´nica permutac¸a˜o distingu´ıvel,
provando assim o resultado.
No exemplo das cadeiras, o Joa˜o tem portanto C(5; 2, 1, 1, 1) = 120 formas diferentes de
colocar as cadeiras em linha.
Podemos verificar isto, contando da seguinte maneira: chamemos por 1, 2, 3, 4, 5 as
poss´ıveis posic¸o˜es de cada cadeira.
As cadeiras azuis podem ser vizinhas nas posic¸o˜es 1-2, 2-3, 3-4, 4-5. Para cada uma
destas as outras 3 cadeiras podem se ordenar de 3!=6 formas diferentes.
Do mesmo modo, as cadeiras azuis podem estar a uma cadeira de distaˆncia nas posic¸o˜es
1-3, 2-4, 3-5; a duas cadeiras de distaˆncia, nas posic¸o˜es 1-4, 2-5; e totalmente afastadas
na posic¸a˜o 1-5. Para cada uma destas possibilidade, temos 3! formas de ordenar as
restantes.
Finalmente, as cadeiras azuis podem ocupar cada uma dessas posic¸o˜es de duas maneiras
poss´ıveis, trocando-as de lugar entre si.
Assim, temos 3!(4 + 3 + 2 + 1)2 = 120 possibilidades.
Ma˜os a` obra. Exerc´ıcios A.3.
16 Estruturas de contagem
Apeˆndice A
Exerc´ıcios
A.1 Conjuntos
1. Mostre que ∅ ⊂ A, para qualquer conjunto A.
2. Dados conjuntos A e B, mostre que A ∩B ⊂ A ⊂ A ∪B.
3. Dado um subconjunto A de um conjunto universo Ω, mostre que A ∪ AC = Ω e
que A ∩AC = ∅.
4. (Leis de De Morgan) Dados dois conjuntos A e B, mostre que
(a) (A ∪B)C = AC ∩BC
(b) (A ∩B)C = AC ∪BC
5. Seja Ω = {1, 2, 3, 4}× {1, 2, 3, 4, 5, 6}. Este conjunto pode ser interpretado como o
conjunto de resultados do lanc¸amento de uma dado de 4 faces e um dado de 6 faces.
Considere os conjuntos A = {(x, y) ∈ Ω : x e´ par } e B = {(x, y) ∈ Ω : x+ y = 5}.
Liste os elementos de cada um dos conjuntos a seguir: A, B, A∪B, A∩B, A \B,
B \A.
6. Seja Ω = {0, 1}3. Este conjunto pode ser visto como o conjunto de resultados
de treˆs lanc¸amentos de uma moeda (0 denota coroa e 1 denota cara). Defina os
conjuntos A = {(s1, s2, s3) ∈ Ω : s2 = 1} e B = {(s1, s2, s3) ∈ Ω : s1 +s2 +s3 = 2}.
Liste os elementos de cada um dos conjuntos a seguir: Ω, A, B, AC , BC , A ∪ B,
A ∩B, A \B, B \A.
7. Seja Ω = {0, 1}2, o conjunto de resultados em dois lanc¸amentos de uma moeda.
Determine P(Ω).
18 Exerc´ıcios
8. 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 indicao valor da carta e o segundo
indica o naipe. Denotemos por A o conjunto de corac¸o˜es, e por B o conjunto de
cartas com personagens. Determine os conjuntos A ∪B, A ∩B, A \B, B \A.
9. * Considere a sequ¨eˆncia de conjuntos An = [0, 1 − 1/n], para n ∈ {1, 2, . . . }.
Determine
⋂
An,
⋃
An,
⋂
ACn ,
⋃
ACn .
Voltar 1.4.
A.2 Medida de Contagem
Considere os subconjuntos A,B,C,A1, A2, . . . , An ⊂ Ω, com Ω finito, para os seguintes
exerc´ıcios.
Dica: antes de fazer as demonstrac¸o˜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 enta˜o #(B \A) = #B −#A.
4. Suponha que Ω e´ um conjunto de sequ¨eˆncias de comprimento k, com elementos da
forma (x1, x2, . . . , xk). Mostre que se cada coordenada j tiver nj poss´ıveis valores,
independente das demais coordenadas, enta˜o
#Ω = n1 n2 . . . nk.
5. Mostre que se Ω tem n elementos, enta˜o Sk tem nk elementos.
6. Mostre que o nu´mero de amostras ordenadas de k elementos que pode ser sele-
cionada com reposic¸a˜o de uma populac¸a˜o de n objetos e´ igual a nk.
7. Mostre que o nu´mero total de func¸o˜es de um conjunto A com n elementos em um
conjunto B com m elementos e´ mn. Este resultado e´ uma motivac¸a˜o para usar a
notac¸a˜o BA para o conjunto de todas as func¸o˜es de A em B.
Estruturas de contagem 19
8. Suponha que Ω tem n elementos. Mostre que o conjunto das partes de Ω tem 2n
elementos.
9. Um experimento consiste em lanc¸ar um dado comum de 6 faces, escolher uma
carta de um baralho e lanc¸ar uma moeda honesta. Quantos poss´ıveis resultados
tem este experimento?
10. Uma moeda honesta e´ lanc¸ada 10 vezes, observando a sequ¨eˆncia de resultados.
Quantas sequ¨eˆncias poss´ıveis ha´? Quantas sequ¨eˆncias teˆm exatamente 3 caras?
11. Um experimento com dados e moedas consiste em lanc¸ar um dado e depois lanc¸ar a
moeda o nu´mero de vezes mostrado no dado, observando a sequ¨eˆncia de resultados
da moeda. Quantos resultados poss´ıveis existem? Quantos deles tem exatamente
duas caras?
Voltar 2.4.
A.3 Estruturas de contagem
Nos exerc´ıcios abaixo, considere n,m, k inteiros na˜o negativos.
Dica: antes de fazer as demonstrac¸o˜es, construa pelo menos um exemplo, atribuindo
valores para as quantidades envolvidas.
1. Mostre que
(
n
0
)
=
(
n
n
)
= 1.
2. Mostre que se n < k enta˜o
(
n
k
)
= 0.
3. Utilizando argumento combinato´rio, mostre que(
n
k
)
=
(
n
n− k
)
,
ou seja, mostre que cada lado da igualdade representa uma forma diferente de
contar a mesma colec¸a˜o. Dica: observe que ao selecionar um subconjunto de k
elementos de um conjunto de tamanho n, deixamos n−k elementos na˜o seleciona-
dos.
4. Utilizando um argumento combinato´rio, mostre que(
n
k
)
=
(
n− 1
k − 1
)
+
(
n− 1
k
)
.
Dica: fixe um elemento do conjunto, e conte o total de subconjuntos de tamanho k
que conte´m o elemento e o total de subconjuntos de tamanho k que na˜o o conte´m.
20 Exerc´ıcios
5. Utilizando um argumento combinato´rio, mostre que
k
(
n
k
)
= n
(
n− 1
k − 1
)
.
Dica: considere duas formas de escolher um comiteˆ de tamanho k de um grupo
de tamanho n; na primeira, o comiteˆ e´ escolhido e depois um chefe dentre os
escolhidos, e na segunda, um chefe e´ escolhido da populac¸a˜o e enta˜o k−1 membros
sa˜o escolhidos do restante n− 1 membros da populac¸a˜o.
6. Utilizando um argumento combinato´rio, mostre que
k∑
j=0
(
n
j
)(
m
k − j
)
=
(
n+m
k
)
.
Dica: considere duas formas de escolher um comiteˆ de tamanho k de um grupo de
tamanho n + m com n homens e m mulheres; conte o nu´mero de comiteˆs com j
homens e k − j mulheres.
Voltar 3.2.
Amostras
1. Um lote conte´m 12 itens bons e 8 itens defeituosos. Uma amostra de 5 itens e´
extra´ıda. Determine o total de amostras contendo exatamente 3 itens bons.
Voltar 3.3
Coeficientes multinomiais
1. Em uma corrida com 10 cavalos, os treˆs primeiros lugares sa˜o anotados. Quantos
resultados poss´ı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 esta˜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;
Estruturas de contagem 21
(c) os casais fiquem juntos.
4. Refac¸a o exerc´ıcio anterior, assumindo agora que os casais esta˜o sentados em uma
mesa redonda.
5. Em uma estante ha´ 12 livros, dos quais 3 sa˜o de f´ısica, 5 sa˜o de matema´tica e 4
sa˜o de histo´ria. Determine o total de arranjos de modo que:
(a) na˜o ha´ restric¸a˜o;
(b) os livros de mesmo tipo devem ficar juntos;
(c) os livros de matema´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 e´ necessa´rio
criar um comiteˆ de 6 pessoas. De quantas formas pode ser composto o comiteˆ se:
(a) na˜o ha´ restric¸a˜o;
(b) o comiteˆ deve ter 4 mulheres e 2 homens;
(c) o comiteˆ deve ter pelo menos 2 mulheres e pelo menos 2 homens.
8. Em um grupo de 10 pessoas, todas elas se apertam as ma˜os. Quantos apertos de
ma˜o sa˜o dados?
9. Suponha que 5 dados distingu´ıveis de 6 faces sa˜o lanc¸ados e que a sequ¨eˆncia obtida
e´ observada. Determine o total de sequ¨eˆncias. Determine o total de sequ¨eˆncias
com todos os resultados diferentes.
10. Refac¸a o exerc´ıcio anterior, assumindo que os dados sa˜o ideˆnticos.
Voltar 3.4.
22 Exerc´ıcios
Apeˆndice B
Demonstrac¸o˜es
B.1 Desigualdade de Boole
Definamos os conjuntos B1 = A1 e Bi = Ai \ (A1 ∪ · · · ∪Ai−1) para i ∈ {1, 2, . . . , n}.
Observe que os elementos de B2 sa˜o os elementos de A2 que na˜o esta˜o em A1. Do mesmo
modo, os elementos de B3 sa˜o os elementos de A3 que na˜o esta˜o nem em A1 nem em
A2, e assim por diante. A Figura B.1 mostra o caso para 3 conjuntos.
 
 
 
Figura B.1: Construc¸a˜o da prova da desigualdade de Boole.
24 Demonstrac¸o˜es
Portanto, os conjuntos B1, B2, . . . , Bn sa˜o disjuntos dois a dois e tem a mesma unia˜o
que A. (Prove estas afirmac¸o˜es formalmente dentro da teoria de conjuntos) Desta forma
#(∪Ai) = #(∪Bi).
Pela regra da adic¸a˜o, #(∪Bi) =
∑
#Bi.
Finalmente, como Bi ⊂ Ai, temos que
# (∪iAi) = # (∪iBi) =
∑
#Bi ≤
∑
#Ai,
como queriamos provar.
Voltar 2.2.
B.2 Desigualdade de Bonferroni
Aplique a desigualdade de Boole aos conjuntos AC1 , A
C
2 , . . . , A
C
n e use as leis de De
Morgan.
Voltar 2.2.
B.3 Fo´rmula de inclusa˜o-exclusa˜o
Observemos que podemos escrever A ∪ B como a unia˜o dos conjuntos disjuntos A e
B \A. Pela regra da adic¸a˜o, chegamos ao resultado.
A generalizac¸a˜o para n conjuntos segue o mesmo racioc´ınio.
Voltar 2.3.
B.4 Amostragem na˜o-ordenada sem reposic¸a˜o
Para sistematizar a contagem, denotemos por xj o total de vezes em que o j-e´simo
elemento da populac¸a˜o foi observado na amostra, para j = 1, . . . , n. Como observamos
uma amostra de tamanho k, temos que x1 + x2 + · · ·+ xn = k.
O total de amostras poss´ıveis, corresponde portanto ao total de soluc¸o˜es inteiras na˜o
negativas da equac¸a˜o anterior.
Uma forma bonita de resolver este problema e´ via modelo de urnas e bolinhas. Consid-
eremos n urnas e k bolinhas, k < n, que sera˜o dispostas aleatoriamente nas urnas. A
Coeficientes multinomiais 25
equac¸a˜o anterior representa este problema, e uma soluc¸a˜o poss´ıvel corresponde a umaforma poss´ıvel de preencher as urnas.
Denotemos as urnas por n+ 1 barras verticais |, indicando os limitantes das urnas. Os
espac¸os entre as barras indicam cada uma das n urnas. Denotemos as k bolinhas por k
s´ımbolos ◦.
Por exemplo, a configurac¸a˜o
| | ◦ ◦ ◦ | ◦ |
representa 3 urnas: a primeira esta´ vazia, a segunda tem 3 bolinha e a terceira tem uma
bolinha.
Queremos contar o nu´mero de maneiras de dispor k s´ımbolos ◦ entre n+1 barras |. Como
a primeira e a u´ltima barras devem permanecer nos extremos (ja´ que as bolinhas na˜o
podem ficar fora das urnas), devemos considerar todas as combinac¸o˜es entre k s´ımbolos
◦ entre n− 1 barras |.
Com isto, o total de amostras poss´ıveis de k elementos de uma populac¸a˜o com n ele-
mentos diferentes, sem ordem e com reposic¸a˜o, e´ igual a(
k + n− 1
k
)
.
Voltar 3.3.
B.5 Coeficientes multinomiais
Dado o conjunto D = {d1, d2, . . . , dn} com n elementos, consideremos uma permutac¸a˜o
de todos os elementos
pi(d1, d2, . . . , dn) = (dpi1 , dpi2 , . . . , dpin).
Dados n1, n2, . . . , nk inteiros na˜o-negativos tais que n1 + n2 + · · · + nk = n, definamos
o conjunto A1 como o conjunto formado pelo primeiros n1 elementos da permutac¸a˜o
anterior. Definamos A2 como o conjunto formado pelo seguintes n2 elementos da per-
mutac¸a˜o, e assim por diante, ate´ obter Ak definido como o conjunto formado pelo u´ltimos
nk elementos da permutac¸a˜o. Se para algum i, ni = 0, definimos o conjunto Ai como o
conjunto vazio.
Desta forma, para cada uma das n! poss´ıveis permutac¸o˜es, constru´ımos os conjuntos
A1, A2, . . . , Ak da mesma maneira.
26 Demonstrac¸o˜es
Observemos que estes conjuntos sa˜o disjuntos entre si e sua unia˜o corresponde ao con-
junto D, ja´ que todos os elementos aparecem na permutac¸a˜o, e aparecem uma u´nica
vez. Em outras palavras, os conjuntos A1, A2, . . . , Ak definem uma partic¸a˜o de D.
Observemos tambe´m que qualquer permutac¸a˜o envolvendo apenas os n1 primeiros ele-
mentos, define o mesmo conjunto A1; do mesmo modo, qualquer permutac¸a˜o envolvendo
apenas os n2 elementos seguintes, define o mesmo conjunto A2, e assim por diante.
Sendo assim, dada uma pemutac¸a˜o definindo os conjuntos A1, A2, . . . , Ak, temos
n1!n2! . . . nk!
permutac¸o˜es diferentes definindo os mesmos conjuntos A1, A2, . . . , Ak, que sa˜o aquelas
que permutam apenas os elementos de cada conjunto entre si.
Portanto, o total de partic¸o˜es diferentes de D e´ igual a n!/(n1!n2! . . . nk!), como que-
r´ıamos provar.
Voltar 3.4.
B.6 Coeficientes multinomiais - Exemplo 1
Para provar o resultado, consideremos um conjunto D = {d1, d2, . . . , dn} com n elemen-
tos.
Observemos que cada t ∈ T = {1, 2, . . . , k}n define uma partic¸a˜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 pertenc¸a ao conjunto Ati , dado pela coordenada i-e´sima
de t. Se o vetor t na˜o tiver nenhuma coordenada com valor igual a j ∈ {1, 2, . . . , k},
enta˜o Aj = ∅.
Esta relac¸a˜o define biunivocamente cada partic¸a˜o de D a partir de t ∈ T . Portanto, o
total de elementos em T e´ igual ao total de partic¸o˜es de D em ate´ k conjuntos.
Voltar 3.4.
Refereˆncias Bibliogra´ficas
[1] Carvalho, P.C.P., de Carvalho, J.B.P., Fernandez, P., Morgado, A.C.O. (2004)
Ana´lise Combinato´ria e Probabilidade. Editora SBM.
[2] Feller, P. (1976) Introduc¸a˜o a` Teoria de Probabilidades e suas Aplicac¸o˜es. Editora
Edgard Blu¨cher.
[3] Gnedenko, B. (2008) A Teoria da Probabilidade. Editora Cieˆncia Moderna.
[4] Halmos, P. (2001) Teoria Ingeˆnua dos Conjuntos. Editora Cieˆncia Moderna.
[5] James, B. (1996) Probabilidade: um curso em n´ıvel intermedia´rio. Colec¸a˜o Projeto
Euclides.
[6] Meyer, P. (2000) Probabilidade: aplicac¸o˜es a` estat´ıstica. Editora LTC.
[7] Ross, S. (2010) Probabilidade: um curso moderno com aplicac¸o˜es. Editora Bookman
Co.
Pa´ginas da internet
Em portugueˆs
[8] ALEA, Acc¸a˜o Local de Estat´ıstica Aplicada, Portugal.
[9] Mais - Recursos Educacionais em Matema´tica, Brasil.
[10] Matema´tica Multimı´dia, Unicamp.
Em ingleˆs
[11] Histo´ria da Matema´tica, Universidade de St. Andrews, Esco´cia.
[12] Laborato´rio de Probabilidade e Estat´ıstica, Universidade do Alabama, EUA.
	Elementos da teoria de conjuntos
	Conjuntos
	Relações entre conjuntos
	Coleções de conjuntos
	Produto cartesiano
	Medida de contagem
	Regra da soma
	Algumas desigualdades
	Desigualdade de Boole
	Desigualdade de Bonferroni
	Fórmula de inclusão-exclusão
	Regra do produto
	Estruturas de contagem
	Permutações
	Combinações
	Amostras
	Amostra ordenada com reposição
	Amostra ordenada sem reposição
	Amostra não ordenada sem reposição
	Amostra não ordenada com reposição
	Coeficientes multinomiais
	Exemplo 1
	Exemplo 2
	Exercícios
	Conjuntos
	Medida de Contagem
	Estruturas de contagem
	Amostras
	Coeficientes multinomiais
	Demonstrações
	Desigualdade de Boole
	Desigualdade de Bonferroni
	Fórmula de inclusão-exclusão
	Amostragem não-ordenada sem reposição
	Coeficientes multinomiais
	Coeficientes multinomiais - Exemplo 1