Probabilidade Combinatória João Paulo Silva do Monte Lima (jpsml@cin.ufpe.br) 2004, João Paulo...

Probabilidade Combinatória

João Paulo Silva do Monte Lima(jpsml@cin.ufpe.br)

2004, João Paulo Silva do Monte Lima.

Roteiro

2004, João Paulo Silva do Monte Lima.

•Noções Fundamentais

•Alguns Métodos de Enumeração:

Progressão Aritmética

Combinação

Noções Fundamentais

2004, João Paulo Silva do Monte Lima.

Sejam A e B subconjuntos de um espaço amostral S, valem as seguintes propriedades:

)()()()( BAPBPAPBAP (baseado no Princípio da Inclusão-Exclusão)

A e B são independentes )()()( BPAPBAP

A e B são excludentes )( BAP

Alguns Métodos de Enumeração

Listamos a seguir algumas maneiras de enumerar os elementos de um evento ou um espaço amostral

2004, João Paulo Silva do Monte Lima.

1) Progressão Aritmética (P.A.)

Dada uma P.A. de n elementos, em que a1 é seu primeiro elemento, an é seu último elemento e r é sua razão, temos:

an = a1 + (n – 1)rDesenvolvendo a igualdade acima, temos:

11

r

aan n

Alguns Métodos de Enumeração

Problema 5.11) Escolha um inteiro uniformemente do conjunto {1, 2, 3, ..., 30}. Seja o evento A de que ele é divisível por 2; seja B o evento de que ele é divisível por 3; seja C o evento de que ele é divisível por 7.(a) Determine as probabilidades de A, B e C.

(b) Quais dos pares (A,B), (B,C) e (A,C) são independentes?

Resolução:(a) A quantidade de números do espaço amostral que são divisíveis por k será o número de elementos de uma P.A. de razão k, com primeiro elemento k.

2004, João Paulo Silva do Monte Lima.

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

(continuação)

1512

23011

A

AAn

r

aaA

2

1

30

15)(

S

AAP

1013

33011

B

BBn

r

aaB

3

1

30

10)(

S

BBP

417

72811

C

CCn

r

aaC

15

2

30

4)(

S

CCP

Alguns Métodos de Enumeração

(continuação)

(b)A e B são independentes?Ser divisível por 2 e 3 é o mesmo que ser divisível

pelo mmc(2,3) = 6

51

6

63011

BA

BABAn

r

aaBA

)()(3

1

2

1

6

1

30

5)( BPAP

S

BABAP

2004, João Paulo Silva do Monte Lima.

Logo, A e B são independentes

Alguns Métodos de Enumeração

(continuação)

A e C são independentes?Ser divisível por 2 e 7 é o mesmo que ser divisível

pelo mmc(2,7) = 14

21

14

142811

CA

CACAn

r

aaCA

)()(15

2

2

1

15

1

30

2)( CPAP

S

CACAP

2004, João Paulo Silva do Monte Lima.

Logo, A e C são independentes

Alguns Métodos de Enumeração

(continuação)

B e C são independentes?Ser divisível por 3 e 7 é o mesmo que ser divisível

pelo mmc(3,7) = 21

11

21

212111

CB

CBCBn

r

aaCB

)()(15

2

3

1

30

1)( CPBP

S

CBCBP

2004, João Paulo Silva do Monte Lima.

Logo, B e C não são independentes

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

2) Combinação

A contagem dos elementos de um evento ou espaço amostral pode ser feita por combinação. Muitas vezes é interessante lançar mão de algumas identidades combinatórias, como por exemplo:

A soma das combinações “pares” de n é igual à soma das combinações

“ímpares” de n

1...31...20 2

nnnnn

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

Problema 5.13) Selecionamos um subconjunto X do conjunto S = {1, 2, ..., 100} aleatoriamente e uniformemente (de modo que todo subconjunto tem a mesma probabilidade de ser selecionado). Qual é a probabilidade de que:

(a) X tenha um número par de elementos.(b) Ambos 1 e 100 pertençam a X.(c) O maior elemento de X seja 50.(d) X tenha no máximo 2 elementos.

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

Resolução:

(a) 1002S A = { subconjuntos “pares” }

991100...2

1000100 22

A2

1

2

2)(

100

99

S

AAP

(b)

1002S B = { subconjuntos com 1 e 100 }

98...1

98098 2 B

4

1

2

2)(

100

98

S

BBP

Basta escolher os demais elementos dos subconjuntos:

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

(continuação)

(c) 1002S C = { subconjuntos cujo maior é 50 }

49...1

49049 2 C 51

100

49

22

2)(

S

CCP

(d)

1002S D = { subconjuntos com cardinalidade 2 }

21001100

0100

D

Basta escolher entre os elementos menores que 50:

S

DDP )(

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

Observando o Triângulo de Pascal e lançando mão da identidade...

knn

kn

... podemos concluir que a seguinte identidade é válida:

nn

nn

nn

nnnn

...22/12/12/...10

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

Em outras palavras, a identidade anterior consiste em dizer que a soma das combinações da esquerda de uma linha do Triângulo de Pascal é igual à soma das combinações da direita.

Quando n é ímpar, a soma de cada lado da igualdade é: 12 n

Quando n é par, a soma de cada lado da igualdade é:

2

2 2/nnn

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

Problema 5.14) Jogamos uma moeda n vezes (n 1). Para quais valores de n os seguintes pares de eventos são independentes?

(a) A primeira jogada foi Cara;O número de Caras foi par.

(b)A primeira jogada foi Cara;O número de Caras foi mais que o número de

Coroas.

(c) O número de Caras foi par;O número de Caras foi mais que o número de

Coroas.

Resolução:

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

(a)

Ca1 = { primeira jogada Cara }

CaP = { número de Caras par }

nS 2 ...Ca/Co Ca/Co Ca/Co

2

1

2

2)(

11

1

n

n

S

CaCaP

11 2 nCa ...

Ca/Co Ca/Co

Ca

2

1

2

2)(

1

n

nP

P S

CaCaP 1

...20 2 nnn

PCa

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

(continuação)Ca1 CaP= {1ª jogada Cara e n.º Caras par}

= {1ª jogada Cara e n.º Caras ímpar nas outras}

)()(2

1

2

1

4

1

2

2)(

1

21

1

P

n

nP

P

CaPCaP

S

CaCaCaCaP

2...3

111

1 2

nnnPCaCa

Logo, Ca1 e CaP são independentes para

qualquer valor válido de n

(continuação)

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

(b) Vamos testar duas situações:

B = { n.° Caras > n.° Coroas }

nS 2 ...Ca/Co Ca/Co Ca/Co

• n ímpar:

1...12/ 2

nnn

nnB

2

1

2

2)(

1

n

n

S

BBP

Ca1 B= {1ª jog. Cara e n.º Caras > n.º Coroas }

= {1ª jog. Cara e n.º Caras n.º Coroas nas outras}

2

1)( 1 CaP

(continuação)

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

)()(2

1

2

1

24

1

2)(

1

1

2/)1(1

2

2/)1(12

11

1

BPCaP

S

BCaBCaP

n

nn

n

nnn

2

2/)1(12

2

2/)1(12

2/)1(1

11

...12/)1(1

2/)1(1

1

11

nn

nn

nn

nn

nn

nn

nn

BCa

Logo, Ca1 e B não são independentes para n

ímpar

(continuação)

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

• n par:

2

2 2/

...22/12/

nnn

nn

nn

nnB

1

2/

2/

22

1

22

2

)(

n

nn

n

nnn

S

BBP

211

...22/)1(1

12/)1(1

1 2

n

nn

nn

nnBCa

)()(

22

1

2

1

4

1

2

2)( 11

2/2

11 BPCaP

S

BCaBCaP

n

nn

n

n

Logo, Ca1 e B não são independentes para n par, e portanto não são independentes, qualquer que

seja n

nS 22

1)( 1 CaP

(continuação)

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

(c) Vamos testar duas situações: • n par: nS 2

CaP B= { n.º Caras par e n.º Caras > n.º Coroas }

2

1)( PCaP

1

2/

22

1)(

n

nn

BP

6656

46

36

26

16

06

44

34

24

14

04

22

12

02

Observando as linhas “pares” do Triângulo de Pascal, notamos que, quando a combinação central é “ímpar”, a quantidade de combinações “pares” à esquerda é a metade das combinações pares da linha

(continuação)

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

Se o n que estivermos considerando tiver combinação central “ímpar”, então temos: 22 n

P BCa

)()(

22

1

2

1

4

1

2

2)(

1

2/2

BPCaPS

BCaBCaP Pn

nn

n

nP

P

Se o n que estivermos considerando tiver combinação central “par”, então temos:

2

2 2/1

nnn

P BCa

)()(

22

1

2

1

24

1

22

2

)(

1

2/

1

2/

2/1

BPCaP

S

BCaBCaP

Pn

nn

n

nn

n

nnn

PP

(continuação)

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

Logo, CaP e B não são independentes para n par• n ímpar: nS 2

2

1)( PCaP

2

1)( BP

776

757

47

37

27

17

07

55

45

35

25

15

05

33

23

13

03

11

01 Observando as linhas

“ímpares” do Triângulo de Pascal, notamos que, quando n = 4x + 3, x natural (em outras palavras, linha não, linha sim), a quantidade de combinações “pares” à esquerda é a metade das combinações pares da linha

(continuação)

Alguns Métodos de Enumeração

2004, João Paulo Silva do Monte Lima.

(continuação)Se o n que estivermos considerando não for igual a 4x + 3, x natural, então temos:

)()(2

1

2

1

4

1

2

2)(

2

BPCaPS

BCaBCaP Pn

nP

P

Se o n que estivermos considerando for igual a 4x + 3, x natural, então temos:

22 nP BCa

)()(2

1

2

1

4

1

2

2)(

2

BPCaPS

BCaBCaP Pn

nP

P

22 nP BCa

Logo, CaP e B são independentes para todo n = 4x + 3, x natural

* Todas as questões contidas neste material foram retiradas do livro:

“Discrete Mathematics: Elementary and Beyond”, L. Lovász, J. Pelikán & K. Vesztergombi. Springer, January 2003, ISBN 0387955852. Tradução parcial datada de 20/09/2003 por Ruy J. Guerra B. de Queiroz disponível em:http://www.cin.ufpe.br/~if670

2004, João Paulo Silva do Monte Lima.

Probabilidade Combinatória

João Paulo Silva do Monte Lima(jpsml@cin.ufpe.br)

2004, João Paulo Silva do Monte Lima.