1.200.000 VISUALIZAÇÕES! OBRIGADO!!

domingo, 23 de agosto de 2009

Análise Combinatória

1 - Introdução

Foi a necessidade de calcular o número de possibilidades existentes nos chamados jogos de azar que levou ao desenvolvimento da Análise Combinatória, parte da Matemática que estuda os métodos de contagem. Esses estudos foram iniciados já no século XVI, pelo matemático italiano Niccollo Fontana (1500-1557), conhecido como Tartaglia. Depois vieram os franceses Pierre de Fermat (1601-1665) e Blaise Pascal (1623-1662).
A Análise Combinatória visa desenvolver métodos que permitam contar - de uma forma indireta - o número de elementos de um conjunto, estando esses elementos agrupados sob certas condições.

2 - Fatorial

Seja n um número inteiro não negativo. Definimos o fatorial de n (indicado pelo símbolo n! ) como sendo:

n! = n .(n-1) . (n-2) . ... .4.3.2.1 para n ³ 2.

Para n = 0 , teremos : 0! = 1.
Para n = 1 , teremos : 1! = 1

Exemplos:

a) 6! = 6.5.4.3.2.1 = 720
b) 4! = 4.3.2.1 = 24
c) observe que 6! = 6.5.4!
d) 10! = 10.9.8.7.6.5.4.3.2.1
e) 10! = 10.9.8.7.6.5!
f ) 10! = 10.9.8!

3 - Princípio fundamental da contagem - PFC

Se determinado acontecimento ocorre em n etapas diferentes, e se a primeira etapa pode ocorrer de k1 maneiras diferentes, a segunda de k2 maneiras diferentes, e assim sucessivamente, então o número total T de maneiras de ocorrer o acontecimento é dado por:
T = k1. k2 . k3 . ... . kn

Exemplo:

O DETRAN decidiu que as placas dos veículos do Brasil serão codificadas usando-se 3 letras do alfabeto e 4 algarismos. Qual o número máximo de veículos que poderá ser licenciado?

Solução:

Usando o raciocínio anterior, imaginemos uma placa genérica do tipo PWR-USTZ.
Como o alfabeto possui 26 letras e nosso sistema numérico possui 10 algarismos (de 0 a 9), podemos concluir que: para a 1ª posição, temos 26 alternativas, e como pode haver repetição, para a 2ª, e 3ª também teremos 26 alternativas. Com relação aos algarismos, concluímos facilmente que temos 10 alternativas para cada um dos 4 lugares. Podemos então afirmar que o número total de veículos que podem ser licenciados será igual a: 26.26.26.10.10.10.10 que resulta em 175.760.000. Observe que se no país existissem 175.760.001 veículos, o sistema de códigos de emplacamento teria que ser modificado, já que não existiriam números suficientes para codificar todos os veículos. Perceberam?

4 - Permutações simples

4.1 - Permutações simples de n elementos distintos são os agrupamentos formados com todos os n elementos e que diferem uns dos outros pela ordem de seus elementos.

Exemplo: com os elementos A,B,C são possíveis as seguintes permutações: ABC, ACB, BAC, BCA, CAB e CBA.

4.2 - O número total de permutações simples de n elementos distintos é dado por n!, isto é
Pn = n! onde n! = n(n-1)(n-2)... .1 .

Exemplos:

a) P6 = 6! = 6.5.4.3.2.1 = 720
b) Calcule o número de formas distintas de 5 pessoas ocuparem os lugares de um banco retangular de cinco lugares.
P5 = 5! = 5.4.3.2.1 = 120

4.3 - Denomina-se ANAGRAMA o agrupamento formado pelas letras de uma palavra, que podem ter ou não significado na linguagem comum.

Exemplo:

Os possíveis anagramas da palavra REI são:
REI, RIE, ERI, EIR, IRE e IER.

5 - Permutações com elementos repetidos

Se entre os n elementos de um conjunto, existem a elementos repetidos, b elementos repetidos, c elementos repetidos e assim sucessivamente , o número total de permutações que podemos formar é dado por:

Exemplo:
Determine o número de anagramas da palavra MATEMÁTICA.(não considere o acento)

Solução:
Temos 10 elementos, com repetição. Observe que a letra M está repetida duas vezes, a letra A três , a letra T, duas vezes. Na fórmula anterior, teremos: n=10, a=2, b=3 e c=2. Sendo k o número procurado, podemos escrever:
k= 10! / (2!.3!.2!) = 151200
Resposta: 151200 anagramas.

6 - Arranjos simples

6.1 - Dado um conjunto com n elementos , chama-se arranjo simples de taxa k , a todo agrupamento de k elementos distintos dispostos numa certa ordem. Dois arranjos diferem entre si, pela ordem de colocação dos elementos. Assim, no conjunto E = {a,b,c}, teremos:
a) arranjos de taxa 2: ab, ac, bc, ba, ca, cb.
b) arranjos de taxa 3: abc, acb, bac, bca, cab, cba.

6.2 - Representando o número total de arranjos de n elementos tomados k a k (taxa k) por An,k , teremos a seguinte fórmula:

Obs : é fácil perceber que An,n = n! = Pn . (Verifique)

Exemplo:

Um cofre possui um disco marcado com os dígitos 0,1,2,...,9. O segredo do cofre é marcado por uma seqüência de 3 dígitos distintos. Se uma pessoa tentar abrir o cofre, quantas tentativas deverá fazer(no máximo) para conseguir abri-lo?

Solução:

As seqüências serão do tipo xyz. Para a primeira posição teremos 10 alternativas, para a segunda, 9 e para a terceira, 8. Podemos aplicar a fórmula de arranjos, mas pelo princípio fundamental de contagem, chegaremos ao mesmo resultado:
10.9.8 = 720.
Observe que 720 = A10,3

7 - Combinações simples

7.1 - Denominamos combinações simples de n elementos distintos tomados k a k (taxa k) aos subconjuntos formados por k elementos distintos escolhidos entre os n elementos dados. Observe que duas combinações são diferentes quando possuem elementos distintos, não importando a ordem em que os elementos são colocados.

Exemplo:

No conjunto E= {a,b.c,d} podemos considerar:
a) combinações de taxa 2: ab, ac, ad,bc,bd, cd.
b) combinações de taxa 3: abc, abd,acd,bcd.
c) combinações de taxa 4: abcd.

7.2 - Representando por Cn,k o número total de combinações de n elementos tomados k a k (taxa k) , temos a seguinte fórmula:



Nota: o número acima é também conhecido como Número binomial e indicado por:



Exemplo:

Uma prova consta de 15 questões das quais o aluno deve resolver 10. De quantas formas ele poderá escolher as 10 questões?

Solução:

Observe que a ordem das questões não muda o teste. Logo, podemos concluir que trata-se de um problema de combinação de 15 elementos com taxa 10.

Aplicando simplesmente a fórmula chegaremos a:
C15,10 = 15! / [(15-10)! . 10!] = 15! / (5! . 10!) = 15.14.13.12.11.10! / 5.4.3.2.1.10! = 3003


Agora que você viu o resumo da teoria, tente resolver os 3 problemas seguintes:

01 - Um coquetel é preparado com duas ou mais bebidas distintas. Se existem 7 bebidas distintas, quantos coquetéis diferentes podem ser preparados?
Resp: 120

02 - Sobre uma circunferência são marcados 9 pontos distintos. Quantos triângulos podem ser construídos com vértices nos 9 pontos marcados?
Resp: 84

03 - Uma família com 5 pessoas possui um automóvel de 5 lugares. Sabendo que somente 2 pessoas sabem dirigir, de quantos modos poderão se acomodar para uma viagem?
Resp: 48

Exercício resolvido:

Um salão tem 6 portas. De quantos modos distintos esse salão pode estar aberto?

Solução:

Para a primeira porta temos duas opções: aberta ou fechada
Para a segunda porta temos também, duas opções, e assim sucessivamente.
Para as seis portas, teremos então, pelo Princípio Fundamental da Contagem - PFC:
N = 2.2.2.2.2.2 = 64
Lembrando que uma dessas opções corresponde a todas as duas portas fechadas, teremos então que o número procurado é igual a 64 - 1 = 63.

Resposta: o salão pode estar aberto de 63 modos possíveis.

PROBABILIDADE



PROBABILIDADE

A história da teoria das probabilidades, teve início com os jogos de cartas, dados e de roleta. Esse é o motivo da grande existência de exemplos de jogos de azar no estudo da probabilidade. A teoria da probabilidade permite que se calcule a chance de ocorrência de um número em um experimento aleatório.

Experimento Aleatório

É aquele experimento que quando repetido em iguais condições, podem fornecer resultados diferentes, ou seja, são resultados explicados ao acaso. Quando se fala de tempo e possibilidades de ganho na loteria, a abordagem envolve cálculo de experimento aleatório.

Espaço Amostral

É o conjunto de todos os resultados possíveis de um experimento aleatório. A letra que representa o espaço amostral, é S.

Exemplo:

Lançando uma moeda e um dado, simultaneamente, sendo S o espaço amostral, constituído pelos 12 elementos:

S = {K1, K2, K3, K4, K5, K6, R1, R2, R3, R4, R5, R6}

1. Escreva explicitamente os seguintes eventos: A={caras e m número par aparece}, B={um número primo aparece}, C={coroas e um número ímpar aparecem}.
2. Idem, o evento em que:

a) A ou B ocorrem;

b) B e C ocorrem;

c) Somente B ocorre.

3. Quais dos eventos A,B e C são mutuamente exclusivos



Resolução:

1. Para obter A, escolhemos os elementos de S constituídos de um K e um número par: A={K2, K4, K6};

Para obter B, escolhemos os pontos de S constituídos de números primos: B={K2,K3,K5,R2,R3,R5}

Para obter C, escolhemos os pontos de S constituídos de um R e um número ímpar: C={R1,R3,R5}.

2. (a) A ou B = AUB = {K2,K4,K6,K3,K5,R2,R3,R5}

(b) B e C = B Ç C = {R3,R5}

(c) Escolhemos os elementos de B que não estão em A ou C;

B Ç Ac Ç Cc = {K3,K5,R2}

3. A e C são mutuamente exclusivos, porque A Ç C = Æ


Conceito de probabilidade

Se em um fenômeno aleatório as possibilidades são igualmente prováveis, então a probabilidade de ocorrer um evento A é:

Por, exemplo, no lançamento de um dado, um número par pode ocorrer de 3 maneiras diferentes dentre 6 igualmente prováveis, portanto, P = 3/6= 1/2 = 50%

Dizemos que um espaço amostral S (finito) é equiprovável quando seus eventos elementares têm probabilidades iguais de ocorrência.

Num espaço amostral equiprovável S (finito), a probabilidade de ocorrência de um evento A é sempre:

Propriedades Importantes:

1. Se A e A’ são eventos complementares, então:

P( A ) + P( A' ) = 1

2. A probabilidade de um evento é sempre um número entre Æ (probabilidade de evento impossível) e 1 (probabilidade do evento certo).



Probabilidade Condicional

Antes da realização de um experimento, é necessário que já tenha alguma informação sobre o evento que se deseja observar. Nesse caso, o espaço amostral se modifica e o evento tem a sua probabilidade de ocorrência alterada.

Fórmula de Probabilidade Condicional

P(E1 e E2 e E3 e ...e En-1 e En) é igual a P(E1).P(E2/E1).P(E3/E1 e E2)...P(En/E1 e E2 e ...En-1).

Onde P(E2/E1) é a probabilidade de ocorrer E2, condicionada pelo fato de já ter ocorrido E1;

P(E3/E1 e E2) é a probabilidade ocorrer E3, condicionada pelo fato de já terem ocorrido E1 e E2;

P(Pn/E1 e E2 e ...En-1) é a probabilidade de ocorrer En, condicionada ao fato de já ter ocorrido E1 e E2...En-1.



Exemplo:

Uma urna tem 30 bolas, sendo 10 vermelhas e 20 azuis. Se ocorrer um sorteio de 2 bolas, uma de cada vez e sem reposição, qual será a probabilidade de a primeira ser vermelha e a segunda ser azul?

Resolução:

Seja o espaço amostral S=30 bolas, e considerarmos os seguintes eventos:

A: vermelha na primeira retirada e P(A) = 10/30

B: azul na segunda retirada e P(B) = 20/29

Assim:

P(A e B) = P(A).(B/A) = 10/30.20/29 = 20/87



Eventos independentes

Dizemos que E1 e E2 e ...En-1, En são eventos independentes quando a probabilidade de ocorrer um deles não depende do fato de os outros terem ou não terem ocorrido.

Fórmula da probabilidade dos eventos independentes:

P(E1 e E2 e E3 e ...e En-1 e En) = P(E1).P(E2).p(E3)...P(En)



Exemplo:

Uma urna tem 30 bolas, sendo 10 vermelhas e 20 azuis. Se sortearmos 2 bolas, 1 de cada vez e repondo a sorteada na urna, qual será a probabilidade de a primeira ser vermelha e a segunda ser azul?

Resolução:

Como os eventos são independentes, a probabilidade de sair vermelha na primeira retirada e azul na segunda retirada é igual ao produto das probabilidades de cada condição, ou seja, P(A e B) = P(A).P(B). Ora, a probabilidade de sair vermelha na primeira retirada é 10/30 e a de sair azul na segunda retirada 20/30. Daí, usando a regra do produto, temos: 10/30.20/30=2/9.

Observe que na segunda retirada forma consideradas todas as bolas, pois houve reposição. Assim, P(B/A) =P(B), porque o fato de sair bola vermelha na primeira retirada não influenciou a segunda retirada, já que ela foi reposta na urna.



Probabilidade de ocorrer a união de eventos

Fórmula da probabilidade de ocorrer a união de eventos:

P(E1 ou E2) = P(E1) + P(E2) - P(E1 e E2)

De fato, se existirem elementos comuns a E1 e E2, estes eventos estarão computados no cálculo de P(E1) e P(E2). Para que sejam considerados uma vez só, subtraímos P(E1 e E2).

Fórmula de probabilidade de ocorrer a união de eventos mutuamente exclusivos:

P(E1 ou E2 ou E3 ou ... ou En) = P(E1) + P(E2) + ... + P(En)



Exemplo: Se dois dados, azul e branco, forem lançados, qual a probabilidade de sair 5 no azul e 3 no branco?

Considerando os eventos:

A: Tirar 5 no dado azul e P(A) = 1/6

B: Tirar 3 no dado branco e P(B) = 1/6

Sendo S o espaço amostral de todos os possíveis resultados, temos:

n(S) = 6.6 = 36 possibilidades. Daí, temos:P(A ou B) = 1/6 + 1/6 – 1/36 = 11/36



Exemplo: Se retirarmos aleatoriamente uma carta de baralho com 52 cartas, qual a probabilidade de ser um 8 ou um Rei?

Sendo S o espaço amostral de todos os resultados possíveis, temos: n(S) = 52 cartas. Considere os eventos:

A: sair 8 e P(A) = 4/52

B: sair um rei e P(B) = 4/52

Assim, P(A ou B) = 4/52 + 4/52 – 0 = 8/52 = 2/13. Note que P(A e B) = 0, pois uma carta não pode ser 8 e rei ao mesmo tempo. Quando isso ocorre dizemos que os eventos A e B são mutuamente exclusivos.