Universidade Estadual de Campinas

Analise Combinatoria, ProbabilidadeNocoes de Estatıstica

Tema 1 - Elementos da teoria de conjuntos eestruturas de contagem

Prof. Laura Rifolaurarifo at ime.unicamp.br

- 1o semestre 2017 -

Conteudo

1 Elementos da teoria de conjuntos 1

1.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Relacoes entre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Colecoes de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Produto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5 Maos a obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Medida de contagem 9

2.1 Princıpio da adicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Algumas desigualdades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Desigualdade de Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Desigualdade de Bonferroni . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Princıpio de inclusao-exclusao . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4 Princıpio da multiplicacao . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5 Maos a obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Estruturas de contagem 19

3.1 Permutacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2 Combinacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3 Maos a obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.4 Amostragem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Amostra ordenada sem reposicao . . . . . . . . . . . . . . . . . . . . . . 28

ii Conteudo

Amostra ordenada com reposicao . . . . . . . . . . . . . . . . . . . . . . 29

Amostra nao ordenada sem reposicao . . . . . . . . . . . . . . . . . . . . 29

Amostra nao ordenada com reposicao . . . . . . . . . . . . . . . . . . . 29

Maos a obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.5 Coeficientes multinomiais . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Maos a obra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Capıtulo 1

Elementos da teoria de conjuntos

1.1 Conjuntos

A teoria de conjuntos e a base para todo o calculo de probabilidades, assim como para

outras areas da matematica. Nesta secao, faremos uma pequena revisao do material

necessario para este modulo.

Lembremos que um conjunto e uma colecao de objetos, chamados os elementos do con-

junto. Tipicamente, denotaremos os conjuntos por letras maiusculas do comeco do alfa-

beto, A,B, . . . , e seus elementos por letras minusculas do alfabeto, a, b, c, s, t, x, y, . . . .

Alguns conjuntos serao denotados por sımbolos especiais, como veremos mais adiante.

A afirmacao de que s e um elemento do conjunto A e 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 sao iguais,

A = B, se eles tiverem os mesmos elementos,

A = B se e somente se (s ∈ A ⇐⇒ s ∈ B) .

Esta relacao entre pertinencia e igualdade e conhecida como o Axioma da Extensao.

Dados os conjuntos A e B, dizemos que A e um subconjunto de B, A ⊂ B, se todo

elemento de A for tambem elemento de B,

A ⊂ B se e somente se (s ∈ A⇒ s ∈ B) ,

e diremos que A ⊂ B e um subconjunto proprio de B se existe algum elemento b ∈ Bque nao 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 inclusao de conjuntos nos permite reescrever o Axioma da Extensao da

seguinte maneira

A = B se e somente se (A ⊂ B e B ⊂ A) .

Esta condicao equivalente e a comumente usada nas demonstracoes de igualdade entre

dois conjuntos: primeiro mostramos que A ⊂ B e depois que B ⊂ A.

Podemos representar conjuntos e relacoes entre eles com desenhos esquematicos chama-

dos diagramas de Euler - Venn. O diagrama da Figura 1.1, por exemplo, representa

a relacao de subconjunto, com A ⊂ B.

Consideremos um conjunto Ω. Para cada elemento s ∈ Ω, um predicado q(s) e uma

afirmacao que ou e verdadeira ou e falsa. Assim, s ∈ Ω : q(s) e 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 numeros pares nao-negativos.

A existencia de um conjunto a partir de um predicado e garantido pelo chamado Axioma

da Especificacao.

Assumiremos agora a seguinte hipotese de existencia: existe um conjunto. Com esta

hipotese e com o Axioma da Especificacao, 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 tambem, pelo Axioma da Extensao, temos que este conjunto e unico: o chamado

conjunto vazio, denotado por ∅.

Observe que o conjunto vazio e subconjunto de qualquer conjunto A. De fato, se isto

nao fosse verdade, deveria existir um elemento s ∈ ∅ que nao pertence a A, o que nao

e possıvel.

Relacoes entre conjuntos 3

Trabalharemos, em qualquer contexto, com conjuntos que serao todos subconjuntos de

um conjunto especıfico, Ω, que chamaremos conjunto universo, no sentido de um

conjunto que contem todos os elementos pertinentes ao contexto dado.

1.2 Relacoes entre conjuntos

Lembremos que as operacao basicas 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 uniao entre A e B, como o conjunto que contem

todos os elementos de A ou de B, e apenas estes,

A ∪B = s ∈ Ω : s ∈ A ou s ∈ B.

A intersecao de A e B e o conjunto dos elementos em comum entre A e B,

A ∩B = s ∈ Ω : s ∈ A e s ∈ B.

A diferenca de conjuntos de B e A e o conjunto dos elementos que estao em B mas

nao em A,

B \A = s ∈ Ω : s ∈ B e s /∈ A.

O complementar de A e o conjunto de elementos de Ω que nao estao em A,

AC = s ∈ Ω : s /∈ A = Ω \A.

Observe que B \A e igual a A ∩BC . (Prove.)

Dizemos que os conjuntos A e B sao disjuntos se sua intersecao for o conjunto vazio,

A ∩B = ∅.

Uma discussao mais aprofundada de teoria de conjuntos pode ser encontrada no livro

classico de Halmos [4]. O projeto Laboratorio 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 relacoes entre dois conjuntos.

1.3 Colecoes de conjuntos

Podemos estender as operacoes anteriores para colecoes finitas ou infinitas de conjuntos.

4 Elementos da teoria de conjuntos

Assim, se tivermos tres conjuntos A,B,C, a uniao deles e

A ∪B ∪ C = (A ∪B) ∪ C = A ∪ (B ∪ C) = s ∈ Ω : s ∈ A ou s ∈ B ou s ∈ C ,

e a intersecao e

A ∩B ∩ C = (A ∩B) ∩ C = A ∩ (B ∩ C) = s ∈ Ω : s ∈ A e s ∈ B e s ∈ C.

Mais geralmente, seja A uma colecao de subconjuntos de Ω, A = Ai ⊂ Ω : i ∈ I.

A uniao da colecao 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 intersecao da colecao 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 colecao.

Figura 1.2: Diagrama de Euler-Venn para a uniao e a intersecao de uma colecao de

conjuntos.

Dizemos que os conjuntos da colecao A sao disjuntos dois a dois se a intersecao de

quaisquer dois conjuntos diferentes da colecao for vazia,

A ∩B = ∅ para quaisquer A ∈ A e B ∈ A , com A 6= B.

Dizemos que a colecao A forma uma particao de um conjunto B se A for disjunta dois

a dois e⋃A = B. Por exemplo, se B = a, b, c, entao A = a, b, c e uma particao

de B.

Produto cartesiano 5

Dado um conjunto Ω, uma colecao importante e a colecao de todos os subconjuntos de

Ω, chamado o conjunto das partes ou conjunto potencia de Ω, que denotaremos

por P(Ω) ou 2Ω. A existencia desta colecao e garantida pelo Axioma das potencias.

Por exemplo, se Ω = ∅, entao P(Ω) e o conjunto ∅. Se Ω = a, b, entao P(Ω) =

∅, a, b,Ω. O conjunto potencia e tipicamente grande com relacao ao conjunto

original: se Ω tem n elementos, entao 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 e elemento de

A, e b e 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 e valida

e outro onde ela nao e.

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 definicao para uma sequencia enumeravel de conjuntos (Ω1,Ω2, . . . )

como ∏i

Ωi = Ω1 × Ω2 × · · · = (s1, s2, . . . ) : si ∈ Ωi para todo i ∈ 1, 2, . . . ,

ou para uma famılia nao-enumeravel, como, por exemplo, Ωt, t ∈ [0, 1]. Neste ultimo

exemplo, podemos pensar o conjunto de ındices como o tempo, e Ωt como o conjunto

considerado no instante t. No caso enumeravel, esta interpretacao tambem se aplica,

considerando o conjunto de ındices como as etapas de um processo e Ωn como o conjunto

considerado da n-esima etapa.

Denotaremos os elementos de um produto cartesiano com a notacao vetorial usual

(s1, s2, . . . , sn) ou simplesmente como letras de uma palavra s1s2 . . . sn.

Alguns produtos do portal Matematica 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 formalizacao e A revanche de Alice mostram alguns dos paradoxos em teoria de

6 Elementos da teoria de conjuntos

conjuntos e suas solucoes formais. Os vıdeos Grande hotel e Hotel de Hilbert abordam

conjuntos numericos infinitos e alguns resultados pouco intuitivos relacionados.

1.5 Maos a 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 e condicao necessaria 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. De um exemplo de uma particao de A

com 3 conjuntos; com 4 conjuntos. Qual e o maior numero de conjuntos que uma

particao 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, entao P(A) ⊂ P(B).

13. Mostre que, dado um conjunto A,⋃P(A) = A e

⋂P(A) = ∅.

14. Obtenha P(∅), PP(∅) e PPP(∅).

Maos a 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 lancamento 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.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, 13. Este conjunto pode ser visto como o conjunto de resultados

de tres lancamentos 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, 12, o conjunto de resultados em dois lancamentos 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 coracoes, 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 sequencia de conjuntos An = [0, 1− 1/n], para n ∈ 1, 2, . . . . Deter-

mine⋂An,

⋃An,

⋂ACn ,

⋃ACn .

8 Elementos da teoria de conjuntos

Capıtulo 2

Medida de contagem

Vimos, como axioma basico em teoria de conjuntos, que um conjunto e completamente

determinado por seus elementos. Em particular, se quisermos saber quantos elementos

tem um conjunto finito, basta, em princıpio, listar seus elementos e conta-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 e tipicamente um conjunto grande, o que nos

leva a necessidade de construir formas eficientes de contagem.

Veremos, neste capıtulo, ferramentas basicas para determinar o numero de elementos de

um conjunto sem necessidade de listar todos seus elementos.

Uma das regras basicas da contagem e o princıpio da adicao da medida de contagem,

tambem conhecido como regra da soma.

Suporemos, a menos que seja explicitado o contrario, que estamos interessados em um

contexto no qual o conjunto universo Ω e um conjunto finito.

Neste caso, dado A ⊂ Ω, a cardinalidade de A e o numero de elementos de A, e sera

denotado por #(A) ou simplesmente #A. A funcao # e chamada medida de contagem

e e fundamental na teoria de probabilidades discretas.

2.1 Princıpio da adicao

Dados A e B, dois conjuntos disjuntos contendo p e q elementos, respectivamente, entao

A ∪B tem p+ q elementos.

10 Medida de contagem

Em geral, sejam A1, A2, . . . , An uma colecao finita de subconjuntos disjuntos dois a dois

de Ω. Entao

#

(n⋃k=1

Ak

)=

n∑k=1

#(Ak).

A visualizacao deste axioma e imediata: sejam A = a, b e B = c, d, e, conjuntos com

#A = 2 e #B = 3; entao #(A ∪ B) = #a, b, c, d, e = 5 = 2 + 3. Do mesmo modo, a

necessidade de serem conjuntos disjuntos tambem e clara: se A = a, b e B = b, c, d,com #A = 2 e #B = 3; entao #(A ∪B) = #a, b, c, d = 4 6= 2 + 3.

Uma consequencia imediata desta propriedade e que, dados dois conjuntos A e B tais

que A ⊂ B, entao #A ≤ #B (mostre isto). Dizemos, entao, que # e uma funcao

crescente relativa a ordem parcial dos subconjuntos de Ω e a ordem usual dos numeros

reais.

2.2 Algumas desigualdades

As seguintes desigualdades nos permitem obter limitantes para o numero de elementos

de um conjunto formado a partir da uniao ou da intersecao de outros conjuntos.

Desigualdade de Boole

Sejam A1, A2, . . . , An uma colecao finita de subconjuntos disjuntos de Ω. Entao

#

(n⋃k=1

Ak

)≤

n∑k=1

#(Ak).

Demonstracao. 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. Entao B1 ∪B2 = A1 ∪A2, ou seja, #(B1 ∪B2) = #(A1 ∪A2). Como B1 e B2

sao disjuntos, pelo princıpio da adicao, #(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.

Algumas desigualdades 11

Figura 2.1: Construcao da prova da desigualdade de Boole.

Observe que os elementos de B2 sao os elementos de A2 que nao estao em A1. Do mesmo

modo, os elementos de B3 sao os elementos de A3 que nao estao 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 sao disjuntos dois a dois e tem a mesma uniao

que A (Prove estas afirmacoes formalmente dentro da teoria de conjuntos). Desta forma

#(∪Ak) = #(∪Bk).

Pela regra da adicao, #(∪Bk) =∑

#Bk.

Finalmente, como Bk ⊂ Ak, temos que

# (∪kAk) = # (∪kBk) =∑

#Bk ≤∑

#Ak,

como querıamos provar.

Em palavras, o total de elementos da uniao de conjuntos e menor ou igual que a soma dos

totais de elementos de cada conjunto, ja que se houver intersecao nao-vazia, contaremos

os elementos da intersecao mais de uma vez.

12 Medida de contagem

Desigualdade de Bonferroni

Seja A1, A2, . . . , An uma colecao finita de subconjuntos disjuntos de Ω. Entao

#

(⋂i

Ai

)≥ #Ω−

∑i

(#ACi

).

Demonstracao. Aplique a desigualdade de Boole aos conjuntos AC1 , AC2 , . . . , A

Cn e use as

leis de De Morgan.

2.3 Princıpio de inclusao-exclusao

Dados os conjuntos A,B ⊂ Ω,

#(A ∪B) = #A+ #B −#(A ∩B).

Demonstracao. Observemos que podemos escrever A ∪ B como a uniao dos conjuntos

disjuntos A e B \A. Pela regra da adicao, chegamos ao resultado.

Esta formula nos da o total exato de elementos de uma uniao, indicando que devemos so-

mar os totais de elementos de cada conjunto e subtrair o total de elementos da intersecao

(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.

Princıpio da multiplicacao 13

Exemplo Quantos inteiros entre 1 e 1000 sao divisıveis por 3 ou 7?

Denotemos por A e B os conjuntos

A = inteiros entre 1 e 1000 divisıveis por 3;

B = inteiros entre 1 e 1000 divisıveis por 7.

Queremos calcular #(A ∪B).

Como

#A =

⌊1000

3

⌋= 333 ,

#B =

⌊1000

7

⌋= 142 ,

#(A ∩B) =

⌊1000

21

⌋= 47 ,

onde bxc e a parte inteira de x, pelo princıpio de inclusao-exclusao, temos que

#(A ∪B) = 333 + 142− 47 = 428 .

2.4 Princıpio da multiplicacao

O princıpio da multiplicacao, tambem conhecido como a regra do produto em contagem,

se baseia na formulacao 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, entao o total de maneiras de realizar o processo e 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 poderı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

Entao o numero total de formas de realizar o procedimento e igual a n1×n2× · · · ×nk,que e tambem o numero total de possıveis objetos gerados.

Podemos visualizar este algoritmo em uma arvore de contagem. Consideremos uma

arvore com k nıveis de galhos, de modo que cada galho do nıvel i se divida em ni+1

novos galhos no nıvel i+ 1, para i = 1, . . . , k − 1, como mostrado na Figura 2.3.

Figura 2.3: Diagrama de arvore de contagem.

O total de nodos no lado direito da arvore e igual ao produto n1 n2 . . . nk.

Em particular, se em cada passo do algoritmo tivermos o mesmo numero de possibili-

dades, n, entao 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 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 aplicacao deste princıpio em um problema de contagem e

fazer uma formulacao clara do algoritmo que gera os diversos possıveis objetos, de modo

que cada objeto seja contado e que seja contado uma unica vez.

Princıpio da multiplicacao 15

Exemplo Uma bandeira e formada por 4 listras, que devem ser coloridas cada uma

de uma cor, usando no maximo as cores branco, verde e cinza. Se listras adjacentes nao

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 nao pode ser

da cor anterior, entao pode ser qualquer uma das outras 2 cores; o mesmo vale para

a terceira e para a quarta listra. Portanto, pelo princıpio da multiplicacao, a bandeira

pode ser pintada de 3 × 2 × 2 × 2 = 24 formas diferentes, algumas delas com apenas

duas cores.

Exemplo Determine a quantidade de numeros naturais entre 100 e 999, formados com

tres algarismos diferentes.

Observe que aqui temos duas condicoes: uma de que os dıgitos devem ser diferentes, e

outra de que o primeiro dıgito nao pode ser igual a zero. Podemos ver o problema como

um processo em 3 etapas diferentes, uma para cada dıgito, comecando, por exemplo,

com o primeiro dıgito. Como ele nao 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 ja foram dois, temos 8 possibilidades. Portanto,

o total requerido e igual a 9× 9× 8 = 648.

Neste exemplo, poderıamos ter comecado o processo por outro algarismo, que nao o

primeiro. Por exemplo, se tivessemos comecado do ultimo, terıamos 10 possibilidades,

para o segundo algarismo, 9 possibilidades, e para o primeiro... nao saberıamos dizer

quantas possibilidades: se o zero ja tiver saıdo, temos 8 possibilidades; e se nao tiver

saıdo, temos 7 possibilidades. Ou seja, deverıamos saber em quantas das 9 × 10 = 90

possibilidades o 0 aparece, para poder completar a solucao do problema.

Exemplo Quantos numeros naturais de 4 algarismos, que sejam menores que 5003 e

divisıveis por 5, podem ser formados apenas com os algarismos 2, 3, 4 e 5?

A recomendacao para abordar o problema e comecar pelo algarismo com mais restricoes,

ate o algarismo com menos restricoes. Assim, comecando pelo ultimo algarismo, temos

apenas uma opcao (o dıgito 5); para o primeiro algarismo, temos 3 opcoes (pois o numero

deve ser menor que 5000); para os outros dois, temos 4 opcoes para cada. Ou seja, temos

3× 4× 4× 1 = 48 numeros satisfazendo as condicoes.

Em muitos problemas aplicados, tipicamente, o total de galhos de um nodo depende nao

so da etapa do processo como tambem do nodo considerado. Nesses casos, o processo

16 Medida de contagem

de contagem deve ser analisado separadamente levando em conta estas condicoes, como

no exemplo seguinte.

Exemplo Quantos numeros pares de tres algarismos podemos escrever com algarismos

diferentes?

Daremos tres solucoes para este problema.

solucao 1 O ultimo algarismo pode ser escrito de 5 modos: 0, 2, 4, 6, 8. O primeiro

dependera de qual algarismo foi usado no passo anterior. Se foi zero, entao o primeiro

pode ser escolhido de 9 modos; se o zero nao foi usado, temos 8 modos. Precisamos

assim contar quantos casos tem o zero e quantos nao o tem como ultimo algarismo.

Terminando em zero, temos 1 modo de escolher o ultimo algarismo, 9 modos de escolher

o primeiro, e 8, o segundo: 9× 8× 1 = 72 numeros.

Nao terminando em zero, temos 4 modos para o ultimo algarismo, 8 para o primeiro e

8 para o segundo: 8× 8× 4 = 256.

Finalmente, pelo princıpio da adicao, o total de numeros satisfazendo a condicao e

72 + 256 = 328.

solucao 2 Podemos ignorar uma das restricoes. Por exemplo, ignoremos que o pri-

meiro algarismo nao pode ser zero. Temos assim 5 modos de escolher o ultimo algarismo,

9 modos de escolher o primeiro e 8, o segundo: 9× 8× 5 = 360 numeros. Estes numeros

incluem aqueles com 0 no primeiro algarismo, que tem que ser descontados. Comecando

em zero, temos 1 forma de escolher o primeiro, 4 de escolher o ultimo, e 8, o segundo:

1× 8× 4 = 32.

Portanto, temos 360− 32 = 328 numeros com a condicao pedida.

solucao 3 Similarmente a estrategia anterior, consideremos todos os numeros com 3

algarismos diferentes: 9× 9× 8 = 648. Destes, descontamos os numeros ımpares com 3

algarismos distintos: 8× 8× 5 = 320, obtendo 648− 320 = 328 numeros.

O vıdeo Desejos e o software Geometria do Taxi, disponıveis no site do projeto Mate-

matica Multimıdia [10] tratam de algumas regras de contagem, podendo ser utilizados

como material auxiliar em sala de aula.

Maos a obra 17

Uma referencia bibliografica classica e o livro de Feller [2], que aborda este topico nos

primeiros capıtulos, com problemas que podem ser verdadeiros desafios. Um texto muito

claro e o de Analise Combinatoria [1] da Colecao do Professor de Matematica, da SBM.

Os seguintes exercıcios sao importantes para perceber diferentes abordagens do princıpio

de adicao.

2.5 Maos a obra

Para os seguintes exercıcios, considere os subconjuntos A,B,C,A1, A2, . . . , An ⊂ Ω, com

Ω finito.

Dica: antes de fazer as demonstracoes, 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 entao #(B \A) = #B −#A.

4. Suponha que Ω e um conjunto de sequencias de comprimento k, com elementos da

forma (x1, x2, . . . , xk). Mostre que se cada coordenada j tiver nj possıveis valores,

independentemente das demais coordenadas, entao

#Ω = n1 × n2 × · · · × nk.

5. Mostre que se Ω tem n elementos, entao Ωk tem nk elementos.

6. Mostre que o numero de amostras ordenadas de k elementos que podem ser sele-

cionadas com reposicao de uma populacao de n objetos e igual a nk.

7. Mostre que o numero total de funcoes de um conjunto A com n elementos em um

conjunto B com m elementos e mn. Este resultado e uma motivacao para usar a

notacao BA para o conjunto de todas as funcoes 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 funcao sobre Ω que

atribui o valor 0 se o elemento nao pertencer a A, e 1, se pertencer. Mostre que

esta funcao determina unicamente o subconjunto A. Quantas funcoes deste tipo

existem?

18 Medida de contagem

9. Um experimento consiste em: primeiro, lancar um dado comum de 6 faces, depois

escolher uma carta de um baralho de 52 cartas e, finalmente, lancar uma moeda

comum. Quantos possıveis resultados tem este experimento?

10. Uma moeda comum e lancada 10 vezes, observando a sequencia de resultados

de cada lancamento. Quantas sequencias possıveis ha? Quantas sequencias tem

exatamente 3 caras?

11. Um experimento com dados e moedas consiste em lancar um dado e depois lancar

uma moeda o numero de vezes mostrado no dado, observando a sequencia de

resultados da moeda. Quantos resultados possıveis existem? Quantos deles tem

exatamente duas caras?

12. Um experimento consiste em lancar 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, lancar uma moeda balanceada o total

de vezes indicado na carta selecionada. Suponha que As vale 1, e as figuras valem

10. Quantos possıveis resultados tem este experimento?

13. Quantos inteiros entre 1 e 1000, inclusive:

(a) sao divisıveis por pelo menos dois dos numeros 2, 3, 7 e 10?

(b) sao divisıveis por pelo menos tres dos numeros 2, 3, 7 e 10?

(c) nao sao divisıveis por nenhum dos numeros 2, 3, 7 e 10?

(d) sao divisıveis por exatamente um dos numeros 2, 3, 7 e 10?

(e) sao divisıveis por pelo menos um dos numeros 2, 3, 7 e 10?

14. Quantos inteiros entre 1000 e 10000 nao sao divisıveis nem por 2, nem por 3, nem

por 5?

Capıtulo 3

Estruturas de contagem

A construcao de um algoritmo para gerar os elementos de um conjunto permite deter-

minar uma estrutura de contagem. Veremos aqui duas estruturas basicas: permutacoes

e combinacoes.

3.1 Permutacoes

Consideremos um conjunto D = d1, d2, . . . , dn com n elementos. Uma permutacao

de k elementos de D e uma sequencia 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 nao pode ser maior que n. Uma permutacao de n elementos de D, ou seja,

uma ordenacao de todos os elementos de D, e chamada simplesmente uma permutacao

de D.

Com esta interpretacao, observemos que na primeira extracao, temos todos os n elemen-

tos de D como possıveis resultados. Para a segunda extracao, como o primeiro elemento

extraıdo nao e reposto, temos n−1 possıveis resultados. Para a terceira extracao, temos

n − 2 possıveis resultados. Assim por diante, ate a k-esima extracao, 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 permutacoes de k elementos em n,

que denotaremos n(k), e igual a

n(k) = n(n− 1) · · · (n− k + 1) =n!

(n− k)!,

onde n! = n(n− 1) · · · 1 e o fatorial de n.

20 Estruturas de contagem

Figura 3.1: Arvore de contagem para uma permutacao 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

unica vez?

Como temos 11 jogadores, temos 11! = 39916800, quase 40 milhoes, de formas possıveis.

Exemplo Uma turma de alunos e formada por 6 alunos de biologia e por 4 alunos de

quımica. Eles serao classificados de acordo com seu desempenho. Suponha que nao ha

empate na classificacao.

(a) Quantas classificacoes diferentes sao possıveis?

(b) Se os alunos de quımica forem classificados apenas entre si, e os de biologia apenas

entre si, quantas classificacoes diferentes sao possıveis?

(a) Como temos 10 alunos no total, temos 10! = 3628800 classificacoes possıveis.

(b) Temos 6! classificacoes diferentes para os alunos de biologia entre si, e 4!, para os

de quımica entre si. Pelo princıpio multiplicativo, temos 6! × 4! = 720 × 24 = 17280

classificacoes possıveis neste caso.

Exemplo Ana tem 14 livros que pretende colocar em sua estante. Destes, 7 sao de

Harry Potter, 3 sao de Jogos Vorazes, 3 sao do Senhor dos Aneis e 1 do Hobbit. Sua

mae pediu que ela arrumasse a estante de acordo com a colecao, mantendo a ordem

Permutacoes 21

dentro de cada colecao (suponha que a mae nao sabe que o Hobbit faz parte da trilogia

do Senhor dos Aneis).

(a) Quantos arranjos diferentes sao possıveis?

(b) E se a Ana nao se preocupar com a ordem dentro de cada colecao?

(a) Como os livros de uma mesma colecao devem ser ordenados, podemos ver cada

colecao como um item apenas. Ou seja, devemos ordenar 4 itens, obtendo assim, 4! = 24

possıveis ordenacoes diferentes.

(b) Para cada uma das 4! ordenacoes 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 ordenacoes diferentes.

Podemos interpretar uma permutacao de k elementos de D como o resultado de um me-

canismo fısico que extrai k elementos da populacao D, sequencialmente e sem reposicao.

Desta forma, podemos usar o princıpio da multiplicacao e um mecanismo de extracao

como um algoritmo de construcao de permutacoes de k elementos de D para contar o

total de possıveis permutacoes.

Em todos os exemplos anteriores, os objetos a serem ordenados eram diferentes entre si.

Outro problema aparece quando alguns dos objetos sao indistinguıveis entre si.

Exemplo Quantas ordenacoes diferentes podem ser obtidos com as letras da palavra

matematica (desconsidere o acento da letra a)?

Primeiro, suponhamos que todas as 10 letras sejam diferentes. Nesse caso, temos 10!

arranjos possı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, nao muda a sequencia obtida. Ou seja, todas estas

2!3!2! permutacoes sao iguais.

Portanto, temos um total de 10!/(2!3!2!) = 151 200 ordenacoes possıveis.

Em geral, este mesmo raciocınio mostra que temos

n!

n1!n2! . . . nk!

permutacoes diferentes de n objetos, quando n1 sao parecidos entre si, n2 sao 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 sao russos, 3 dos

Estados Unidos, 2 da Gra-Bretanha e 1 do Brasil. Em uma lista das colocacoes apenas

por nacionalidade, quantos resultados sao possıveis?

Pelo anterior, temos 10!/(4!3!2!1!) = 12 600 resultados diferentes.

3.2 Combinacoes

Consideremos um conjunto D = d1, d2, . . . , dn com n elementos. Uma combinacao de

k elementos de D e um subconjunto (nao-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 nao pode ser maior que n.

Podemos interpretar uma combinacao como o resultado do mecanismo fısico que extrai

uma amostra nao-ordenada de uma populacao D sem reposicao.

Denotemos por C(n, k) o total de combinacoes de k elementos de um grupo de n.

Observemos que cada combinacao permite construir k! ordenacoes diferentes, ou seja,

k! permutacoes de comprimento k dos elementos selecionados.

Figura 3.2: Uma combinacao de k elementos gera k! permutacoes desses elementos.

Isto nos permite obter o total de combinacoes possıveis de k elementos dentre n a partir

do total de permutacoes de k elementos, ja 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-

binacoes possıveis de k objetos extraıdos de um conjunto com n objetos, quando a

ordem da selecao nao for relevante.

Combinacoes 23

Por convencao, definimos 0! = 1. Com isto,(n0

)=(nn

)= 1. Alem disto,

(nk

)= 0, quando

k < 0 ou k > n.

Veja que, com esta construcao reobtemos a mesma interpretacao 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 vertice superior.

Exemplo Um comite de 3 pessoas deve ser formado de um grupo de 20 pessoas.

Quantos comites diferentes podemos formar?

De maneira imediata, temos(

203

)= 1140 comites diferentes.

Exemplo Voltando a estante de Ana, suponha que ela vai viajar e quer levar tres

livros para reler.

(a) De quantas formas ela pode escolher estes tres livros?

(b) Suponha que ela quer levar um de cada colecao para reler. Como ela ja leu todos

esses livros, ela sabe que o Hobbit faz parte da trilogia do Senhor dos Aneis. Neste caso,

de quantas formas ela pode escolher estes livros?

No primeiro item, ela tem(

143

)= 364 opcoes. No segundo item, para HP, ela tem 7

possibilidades, 3 para JV e 4 para SA. Assim, ela pode escolher os livros de(

71

)×(

31

)×(

41

)= 84 formas diferentes.

Exemplo De um grupo de 5 mulheres e 7 homens, quantos comites diferentes podemos

formar com 2 mulheres e 3 homens? E se dois dos homens nao puderem trabalhar juntos?

Para a primeira parte, temos(

52

)= 10 formas de escolher as duas mulheres, e

(73

)= 35, de

escolher os 3 homens. Assim, pelo princıpio multiplicativo, temos 350 comites possıveis.

Com a restricao da segunda parte, temos que dos 35 grupos de 3 homens, em 5 deles,

os dois homens estao juntos (o terceiro membro pode ser qualquer um dos 5 homens

restantes). Assim, temos um total de 10× 30 = 300 comites possıveis.

Exemplo Considere um conjunto de n antenas, indistinguıveis entre si, das quais m

estao 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 sao colocadas em fila. Para que nao haja

duas antenas defeituosas lado a lado, entao entre duas antenas que funcionam pode ser

24 Estruturas de contagem

colocada no maximo uma antena defeituosa. O mesmo vale para as posicoes anterior e

posterior as antenas que funcionam.

Como temos (n−m+ 1) posicoes possıveis para as antenas defeituosas, e so pode haver

no maximo uma defeituosa em cada uma destas posicoes, uma condicao que aparece

naturalmente e que m ≤ n−m+ 1.

Pelo anterior, podemos alocar as antenas defeituosas nestas posicoes de(n−m+1

m

)manei-

ras diferentes, indicando aqui as m posicoes ocupadas.

O raciocınio anterior nos leva a um novo algoritmo (com dois passos) para construir per-

mutacoes: primeiro selecionamos uma combinacao de k elementos e depois selecionamos

uma ordem para estes elementos.

Teorema 1 (Teorema binomial). Sejam x, y ∈ R e n numero natural. Entao

(x+ y)n =

n∑k=0

(n

k

)xkyn−k .

Demonstracao. Podemos fazer a prova do teorema binomial por inducao ou por um

argumento combinatorio.

Prova por inducao Quando n = 1, o lado direito da equacao fica

(1

0

)x0y1 +

(1

1

)x1y0 = y + x = (x+ y)1 ,

comprovando a igualdade para n = 1.

Suponha que a equacao seja valida 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 .

Combinacoes 25

Fazendo a mudanca de variavel 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 e valida para n+ 1, concluindo a prova por inducao.

Prova por argumento combinatorio Considere o produto

(x1 + y1)(x2 + y2) . . . (xn + yn) .

Sua expansao sera formada pela soma de termos, cada um deles igual a um produto

contendo xi ou yi (mas nao ambos), para cada i = 1, . . . , n. Por exemplo,

(x1 + y1)(x2 + y2) = x1x2 + x1y2 + y1x2 + y1y2 .

Pelo princıpio multiplicativo, temos um total de 2n destes termos.

Quantos destes termos contem k dos xi’s, e n− k dos yi’s?

Esta escolha corresponde a escolher k posicoes dentre as n, para os xi’s, ficando as

restantes para os yi’s. Temos assim(nk

)destas opcoes.

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,(nk

)subconjuntos com k elementos, o total de subconjuntos e

n∑k=0

(n

k

)= (1 + 1)n = 2n .

Outra forma de provar este resultado e 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 nao. Assim, pelo princıpio multiplica-

tivo, temos 2n possibilidades.

26 Estruturas de contagem

Se quisermos obter o total de subconjuntos nao vazios de Ω, este total e simplesmente

2n − 1.

Podemos usar argumentos combinatorios 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.

Ja sabemos que o total de maneiras de formar um subconjunto com k elementos e(nk

),

que e o primeiro termo da igualdade anterior.

Por outro lado, podemos pensar neste total de maneiras, considerando aqueles conjuntos

que nao contem o elemento a, e aqueles que o contem.

Aqueles que nao contem o elemento a sao formados portanto com n−1 elementos: o total

possıvel destes conjuntos e(n−1k

), o segundo somando do segundo termo da igualdade.

Aqueles que contem o elemento a representam o total de conjuntos de tamanho k − 1

que podem ser formados com n− 1 elementos; temos(n−1k−1

)deles.

Com isto, terminamos a prova.

Os exercıcios desta secao mostram algumas propriedades teoricas basicas dos conceitos

definidos.

3.3 Maos a obra

Nos exercıcios abaixo, considere n,m, k inteiros nao negativos.

Dica: antes de fazer as demonstracoes, construa pelo menos um exemplo, atribuindo

valores para as quantidades envolvidas. Mais dicas para alguns dos problemas, no fim

do capıtulo; mas so olhe as dicas depois de ter pensado no problema.

1. Mostre que(n0

)=(nn

)= 1.

2. Mostre que se n < k entao(nk

)= 0.

Maos a obra 27

3. Utilizando argumento combinatorio, mostre que(n

k

)=

(n

n− k

),

ou seja, mostre que cada lado da igualdade representa uma forma diferente de

contar a mesma colecao.

4. Utilizando um argumento combinatorio, mostre que

k

(n

k

)= n

(n− 1

k − 1

).

5. Utilizando um argumento combinatorio, mostre que(n+m

k

)=

k∑j=0

(n

j

)(m

k − j

).

6. Use o exercıcio anterior para mostrar que(2n

n

)=

n∑j=0

(n

j

)2

.

7. Utilize um argumento combinatorio para mostrar que(n

k

)=

n∑i=k

(i− 1

k − 1

), n ≥ k .

Esta igualdade e chamada identidade combinatoria de Fermat.

8. Utilize um argumento combinatorio para mostrar que

n∑k=1

k

(n

k

)= n 2n−1 .

9. Utilize um argumento combinatorio para mostrar que

n∑k=1

k2

(n

k

)= n (n+ 1) 2n−2 .

Dicas:

Exercıcio 3: observe que ao selecionar um subconjunto de k elementos de um conjunto

de tamanho n, deixamos n− k elementos nao selecionados.

Exercıcio 4: 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,

28 Estruturas de contagem

e na segunda, um chefe e escolhido da populacao e entao k − 1 membros sao escolhidos

do restante n− 1 membros da populacao.

Exercıcio 5: 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 numero de comites com j homens

e k − j mulheres.

Exercıcio 7: considere o conjunto de numeros naturais de 1 ate n. Quantos subconjuntos

de tamanho k tem i como maior elemento?

Exercıcio 8: considere um conjunto de n pessoas e determine, de duas maneiras diferen-

tes, o total de possıveis opcoes para um comite de qualquer tamanho com um presidente.

Exercıcio 9: considere um conjunto de n pessoas e determine, de duas maneiras diferen-

tes, o total de possıveis opcoes para um comite de qualquer tamanho com um presidente

e um secretario (que poderia acumular a funcao de presidente).

3.4 Amostragem

Um dos experimentos basicos e importantes em probabilidade e o de obter uma amostra

de uma populacao finita, o que e representado pelo experimento fısico de extrair objetos

da populacao.

Neste tipo de experimento, duas propriedades essenciais do procedimento de amostragem

devem ser bem especificadas:

• se a ordem em que os objetos sao extraıdos da populacao e ou nao importante, e

• se um objeto amostrado e ou nao reposto na populacao antes da extracao seguinte.

Consideremos uma populacao 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 uma amostragem sera descrita com mais

detalhe a seguir.

Amostra ordenada sem reposicao

Se a ordem for importante e as extracoes forem feitas sem reposicao, entao uma amostra

de k elementos e simplesmente uma permutacao de tamanho k escolhida de D. Nova-

mente, pela regra do produto, o total de amostras possıveis e igual a n(k). Este tipo de

amostra e tambem chamado arranjo simples de classe k em n elementos.

Amostragem 29

Figura 3.3: Amostra de tamanho k de uma populacao D com n elementos.

Amostra ordenada com reposicao

Se a ordem for importante e as extracoes forem feitas com reposicao, entao uma amostra e

um elemento do produto cartesiano Dk, ou seja, uma amostra e um vetor (a1, a2, . . . , ak),

onde ai representa o i-esimo 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.

Este tipo de amostra tambem e chamada arranjo completo de classe k dos n elementos.

Amostra nao ordenada sem reposicao

Se a ordem nao for importante e as extracoes forem feitas sem reposicao, entao uma

amostra e uma combinacao de k elementos de D; neste caso, o total de amostras possıveis

e C(n, k). Este tipo de amostragem tambem e chamado combinacao simples de k ele-

mentos em n.

Amostra nao ordenada com reposicao

Finalmente, consideremos o caso em que a ordem nao e importante e as extracoes sao

feitas com reposicao. As possıveis amostras podem ter apenas um elemento repetido

k vezes, ou apenas dois elementos diferentes no total de k extracoes, ou apenas tres

diferentes, ou assim por diante, ate k elementos diferentes, nao-ordenados. O total de

30 Estruturas de contagem

amostras possıveis, neste caso, e igual a(k + n− 1

k

).

Este tipo de amostra e tambem chamado um multiconjunto ou combinacao com-

pleta de k elementos em n.

Demonstracao. Para sistematizar a contagem, denotemos por xj o total de vezes em

que o j-esimo elemento da populacao e 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 possıveis, corresponde portanto ao total de solucoes inteiras nao

negativas da equacao anterior, nas variaveis xi´s.

Uma forma bonita de resolver este problema e via modelo de urnas e bolinhas. Consi-

deremos n urnas e k bolinhas, que serao dispostas aleatoriamente nas urnas. A equacao

anterior representa este problema, com xi representando o total de bolinhas na i-esima

urna. Uma forma de preencher as urnas corresponde a uma solucao desta equacao e,

portanto, a uma amostra nao ordenada com reposicao.

Assim, basta contar o total de formas de preencher as urnas.

Indiquemos as n urnas por n + 1 barras verticais |, de modo que os espacos entre as

barras representam cada uma das n urnas. Indiquemos as k bolinhas por k sımbolos .

Por exemplo, a configuracao

| | | |

representa 3 urnas: a primeira esta vazia, a segunda tem 3 bolinhas e a terceira tem

uma bolinha.

Queremos contar o numero de maneiras de dispor k sımbolos entre n+1 barras |. Como

a primeira e a ultima barras devem permanecer nos extremos (ja que as bolinhas nao

podem ficar fora das urnas), devemos considerar todas as combinacoes entre k sımbolos

e n− 1 barras |.

Com isto, o total de amostras nao ordenadas e com reposicao de k elementos de uma

populacao contendo n elementos diferentes e igual a(k + n− 1

k

).

Coeficientes multinomiais 31

O software Probabilidade com urnas, disponıvel no site do projeto Matematica 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?

Maos a obra

1. Um lote contem 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.

Considere cada um dos quatro tipos de amostragem definidos.

2. De 10 casais queremos selecionar um grupo de 6 pessoas, no qual a presenca de

um casal nao e permitida.

(a) Quantas opcoes existem?

(b) Se o grupo tambem tiver que ser formado por 3 homens e 3 mulheres, quantas

opcoes 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 sao possı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 contem pelo

menos um dos elementos 1, 2, 3, 4, 5?

5. Mostre que existe uma correspondencia biunıvoca entre cada par das seguintes

colecoes:

(a) multiconjuntos de tamanho k de uma populacao D com n elementos;

(b) sequencias de 0’s e 1’s, de comprimentos n + k − 1, contendo exatamente k

valores 1’s;

(c) solucoes inteiras nao-negativas, (x1, . . . , xn), da equacao x1 + · · ·+ xn = k.

Cada uma destas colecoes tem(n+k−1

k

)elementos.

3.5 Coeficientes multinomiais

Consideremos o conjunto D = d1, d2, . . . , dn com n elementos.

32 Estruturas de contagem

Observemos que uma combinacao de j elementos de D define uma particao de D, for-

mada por um conjunto A, contendo os j elementos da combinacao, e AC , contendo os

n− j elementos restantes.

Figura 3.4: Particao de um conjunto em dois subconjuntos, com cardinalidades j e n−j.

Uma generalizacao natural deste conceito e o de particao 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: Particao de um conjunto em k subconjuntos, cada um com cardinalidade

ni.

O total de particoes 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!,

onde ni ≥ 0, para todo i, e∑ni = n. Este numero e chamado coeficiente multino-

mial e e denotado tambem por (n

n1, n2, . . . , nk

).

Demonstracao. Dado o conjunto D = d1, d2, . . . , dn com n elementos, consideremos

uma permutacao de todos os elementos

π(d1, d2, . . . , dn) = (dπ1 , dπ2 , . . . , dπn).

Coeficientes multinomiais 33

Dados n1, n2, . . . , nk inteiros nao-negativos tais que n1 + n2 + · · · + nk = n, definamos

o conjunto A1 como o conjunto formado pelos primeiros n1 elementos da permutacao

anterior. Definamos A2 como o conjunto formado pelos seguintes n2 elementos da per-

mutacao, e assim por diante, ate obter Ak definido como o conjunto formado pelos

ultimos nk elementos da permutacao. Se para algum i, ni = 0, tomamos o conjunto Ai

como o conjunto vazio.

Desta forma, para cada uma das n! possıveis permutacoes, construımos os conjuntos

A1, A2, . . . , Ak da mesma maneira.

Observemos que estes conjuntos sao disjuntos entre si e sua uniao corresponde ao con-

junto D, ja que todos os elementos aparecem na permutacao, e aparecem uma unica

vez. Em outras palavras, os conjuntos A1, A2, . . . , Ak definem uma particao de D.

Observemos tambem que qualquer permutacao envolvendo apenas os n1 primeiros ele-

mentos, define o mesmo conjunto A1; do mesmo modo, qualquer permutacao envolvendo

apenas os n2 elementos seguintes, define o mesmo conjunto A2, e assim por diante.

Sendo assim, dada uma permutacao definindo os conjuntos A1, A2, . . . , Ak, temos

n1!n2! . . . nk!

permutacoes diferentes definindo os mesmos conjuntos A1, A2, . . . , Ak, que sao aquelas

que permutam apenas os elementos de cada conjunto entre si.

Portanto, o total de particoes diferentes de D e igual a n!/(n1!n2! . . . nk!), como que-

rıamos provar.

Exemplo Dez criancas devem ser agrupadas em dois times A e B, com 5 criancas

cada. O time A jogara em uma liga e o time B, em outra. Quantas formacoes diferentes

sao possıveis? E se os times forem jogar na mesma liga?

Exemplo Consideremos o conjunto T = 1, 2, . . . , kn. Os elementos de T sao vetores

de comprimento 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 tres coordenadas,

onde cada coordenada e um valor inteiro entre 1 e 5. Para o vetor t = (3, 3, 2), temos

34 Estruturas de contagem

que n1 = 0 = n4 = n5, ja que os valores 1, 4 e 5 nao 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 definicao, podemos perceber que a soma n1 +n2 + · · ·+nk deve ser igual a n,

que e o total de coordenadas do vetor t.

Entao, o total de sequencias em T tais que o valor i ocorre ni vezes, para i = 1, 2, . . . , k,

e igual a C(n;n1, n2, . . . , nk).

Demonstracao. Para provar o resultado, consideremos um conjunto D = d1, d2, . . . , dncom n elementos.

Observemos que cada t ∈ T = 1, 2, . . . , kn define uma particao 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 pertenca ao conjunto Ati , dado pela coordenada i-esima

de t. Se o vetor t nao tiver nenhuma coordenada com valor igual a j ∈ 1, 2, . . . , k,entao Aj = ∅.

Esta relacao define biunivocamente cada particao de D a partir de t ∈ T . Portanto, o

total de elementos em T e igual ao total de particoes de D em ate k conjuntos.

Com este resultado, no exemplo anterior temos que o total de sequencias de 3 elementos

de 1, 2, 3, 4, 5, formada por 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 · 12

= 3,

e sao 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 sao indistinguıveis entre si, entao o total de

permutacoes distinguıveis dos n objetos e igual a C(n;n1, n2, . . . , nk).

Observemos que cada permutacao distinguıvel destes objetos corresponde a um unico

elemento de T do exemplo anterior, e cada elemento de T define uma unica permutacao

distinguı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

possıveis posicoes de cada cadeira.

As cadeiras azuis podem ser vizinhas nas posicoes 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 distancia nas posicoes

1-3, 2-4, 3-5; a duas cadeiras de distancia, nas posicoes 1-4, 2-5; e totalmente afastadas

na posicao 1-5. Para cada uma destas possibilidade, temos 3! formas de ordenar as

restantes.

Assim, temos 3!(4 + 3 + 2 + 1) = 60 possıveis ordenacoes distinguıveis.

O seguinte resultado generaliza o Teorema binomial e sua demonstracao segue analoga-

mente.

Teorema 2 (Teorema multinomial). Sejam x1 . . . , xr ∈ R e n numero natural. Entao

(x1 + · · ·+ xr)n =

∑(n

n1, . . . , nr

)xn1

1 . . . xnrr ,

com soma definida no conjunto dos vetores (n1, . . . , nr) com valores inteiros nao nega-

tivos tais que n1 + · · ·+ nr = n.

Maos a obra

1. Em uma corrida com 10 cavalos, os tres primeiros lugares sao 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 estao 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. Refaca o exercıcio anterior, assumindo agora que os casais estao sentados em uma

mesa redonda.

36 Estruturas de contagem

5. Em uma estante ha 12 livros, dos quais 3 sao de fısica, 5 sao de matematica e 4

sao de historia. Determine o total de arranjos de modo que:

(a) nao ha restricao;

(b) os livros de mesmo tipo devem ficar juntos;

(c) os livros de matematica 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 necessario

criar um comite de 6 pessoas. De quantas formas pode ser composto o comite se:

(a) nao ha restricao;

(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 maos uma vez. Quantos

apertos de mao sao dados?

9. De quantos modos podemos formar uma roda com 5 criancas?

10. De quantos modos podemos distribuir 8 pessoas em dois grupos de 4 pessoas cada?

Dica: a distribuicao 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 tres 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 distinguıveis de 6 faces sao lancados e que a sequencia obtida

e observada. Determine o total de sequencias. Determine o total de sequencias

com todos os resultados diferentes.

13. Refaca o exercıcio anterior, assumindo que os dados sao identicos.

14. Um sinal sera formado usando nove bandeiras alinhadas, sendo 4 brancas, 3 ver-

melhas e 2 azuis. Bandeiras da mesma cor sao indistinguı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, 1n tais que∑xi = k (responda

em funcao de k).

17. Determine o total de vetores (x1, . . . , xk) ∈ 1, . . . , nk tais que x1 < x2 < · · · <xk.

18. Delegados de 10 paı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 Arabia Saudita e o dos Estados Unidos nao podem sentar juntos?

19. Um cubo de madeira tem uma face de cada cor. Quantos dados diferentes podemos

formar gravando numeros de 1 a 6 sobre essas faces?

20. Quantos dados diferentes podemos formar gravando numeros de 1 a 6 sobre as

faces indistinguıveis de um cubo de madeira?

21. Resolva o problema anterior para:

(a) numeros de 1 a 4, tetraedro regular;

(b) numeros de 1 a 8, octaedro regular;

(c) numeros de 1 a 12, dodecaedro regular;

(d) numeros de 1 a 20, icosaedro regular;

(e) numeros 1 a 8, prisma hexagonal regular;

(f) numeros de 1 a 5, piramide quadrangular regular.

22. Temos 5 pontos sobre uma reta R e 8 pontos sobre uma reta R′, paralela a R.

Quantos quadrilateros convexos com vertices em 4 desses 13 pontos existem?

23. Em um torneio no qual cada participante enfrenta todos os demais uma unica vez,

sao jogadas 780 partidas. Quantos sao os participantes?

24. Considere os conjuntos Im = 1, . . . ,m e In = 1, . . . , n, com m ≤ n. Quantas

sao as funcoes f : Im → In, estritamente crescentes?

25. Quantos sao os numeros 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 sao os numeros 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 sao os p-conjuntos (isto e, subconjuntos com p elementos) de a1, . . . , annos quais:

(a) a1 aparece;

(b) a1 nao 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

numero de funcoes 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 questoes de seguranca, os

planos sao guardados em um cofre protegido por muitos cadeados de modo que so

e possıvel abrı-los todos se houver pelo menos 5 cientistas presentes.

(a) Qual e o numero mınimo possıvel de cadeados?

(b) Na situacao do item (a), quantas chaves cada cientista deve ter?

30. Formam-se as combinacoes com p elementos extraıdos de a1, . . . , a12, as quais

sao escritas com os elementos em ordem crescente de ındices. Quantas sao as

combinacoes nas quais o elementos a8 ocupa o 3o lugar?

31. O conjunto A possui n elementos. Determine o numero de relacoes que podem ser

construıdas em A:

(a) sem nenhuma outra condicao;

(b) que sejam refexivas;

(c) que sejam simetricas;

(d) que sejam anti-simetricas;

(e) que sejam reflexivas e simetricas;

(f) que sejam reflexivas e anti-simetricas;

(g) que sejam simetricas e anti-simetricas;

(h) que sejam reflexivas, simetricas e anti-simetricas.

32. De quantos modos se pode iluminar uma sala que tem m lampadas?

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

tem 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 e sempre divisıvel por p!.

35. Prove, usando um argumento combinatorio, que os numeros abaixo sao 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) e divisıvel por 7?

37. Qual e o numero de solucoes inteiras e nao negativas da equacao x+ y + z = 5?

38. De quantos modos podemos comprar 3 refrigerantes em uma loja onde ha 5 tipos

de refrigerantes?

39. Quantas sao as solucoes inteiras e nao negativas da inequacao x+ y + z ≤ 5?

40. Quantas sao as solucoes inteiras da equacao x + y + z = 20, com x ≥ 2, y ≥ 2,

z ≥ 2?

41. Quantas sao as solucoes inteiras nao negativas de

x1 + x2 + · · ·+ x6 = 20 ,

nas quais exatamente 3 incognitas sao nulas? Em quantas pelo menos 3 sao nulas?

42. Quantas sao as solucoes inteiras nao negativas de x + y + z + w = 20, nas quais

x > y?

43. Quantos numeros inteiros entre 1 e cem mil tem a soma dos algarismos igual a 6?

44. No experimento do tabuleiro de Galton (clique aqui),

(a) mova a partıcula de (0, 0) ate (10, 6), pelo caminho que voce quiser.

(b) gere a sequencia 0011101001. Note o subconjunto e o caminho corresponden-

tes;

(c) gere o subconjunto 1, 4, 5, 7, 8, 10. Note a sequencia de bits e caminho cor-

respondentes;

(d) gere todos os caminhos de (0, 0) ate (5, 3). Quantos tem?

40 Estruturas de contagem

Bibliografia

[1] Morgado, A.C.O., de Carvalho, J.B.P., Carvalho, P.C.P., Fernandez, P. (2006, 9a

ed.) Analise Combinatoria e Probabilidade. Colecao do Professor de Matematica,

Editora SBM.

[2] Feller, P. (1976) Introducao a Teoria de Probabilidades e suas Aplicacoes. Editora

Edgard Blucher.

[3] Gnedenko, B. (2008) A Teoria da Probabilidade. Editora Ciencia Moderna.

[4] Halmos, P. (2001) Teoria Ingenua dos Conjuntos. Editora Ciencia Moderna.

[5] James, B. (1996) Probabilidade: um curso em nıvel intermediario. Colecao Projeto

Euclides.

[6] Meyer, P. (2000) Probabilidade: aplicacoes a estatıstica. Editora LTC.

[7] Ross, S. (2010) Probabilidade: um curso moderno com aplicacoes. Editora Bookman

Co.

Paginas da internet

Em portugues

[8] ALEA, Accao Local de Estatıstica Aplicada, Portugal.

[9] Mais - Recursos Educacionais em Matematica, Brasil.

[10] Matematica Multimıdia, Unicamp.

Em ingles

[11] Historia da Matematica, Universidade de St. Andrews, Escocia.

[12] Laboratorio de Probabilidade e Estatıstica, Universidade do Alabama, EUA.