Make your own free website on Tripod.com






ANÁLISE COMBINATÓRIA
Resumo da teoria

 
01 - 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.
02 - 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!
03 - 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? 
04 - 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 . Ex: P6 = 6! = 6.5.4.3.2.1 = 720
Exemplo: Calcule o número de formas distintas de 5 pessoas ocuparem os lugares de um banco retangular de cinco lugares.
Solução: P5 = 5! = 5.4.3.2.1 = 120 
Resp: 5 pessoas poderão ocupar os 5 lugares do banco de 120 maneiras distintas.
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.
05 - 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 
Resp: 151200 anagramas.
Agora tente!
DESAFIO!
A) Determine o número de soluções inteiras e não negativas da equação linear
x + y + z + w = 5.
Resp: 56
Desafio!
B) Numa pastelaria são vendidos pastéis de carne, queijo e frango. De quantas formas uma pessoa pode escolher 5 pastéis?
Resp: 21
06 - 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. 
07 - 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:

Obs: 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 
Resp: 3003 maneiras distintas.

Agora que você viu o resumo da teoria, tente resolver os 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 - UECE) A quantidade de números inteiros positivos menores que 400 que podemos formar, utilizando somente os algarismos 1,2,3,4 e 5, de modo que não figurem algarismos repetidos, é:
a) 36 
b) 56 
*c) 61 
d) 85 
e) 65
03 - UNIFOR) Sobre uma circunferência são marcados 9 pontos, dois a dois distintos. Quantos triângulos podem ser construídos com vértices nos 9 pontos marcados?
Resp: 84
04 - 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
05 - As retas r e s são distintas e paralelas entre si. São dados 5 pontos distintos na reta r e 4 pontos distintos sobre a reta s. Quantos são os triângulos determinados pelos pontos dados?
Resp: 70
06 - Seja M um conjunto com 20 elementos. O número de subconjuntos de M que possuem exatamente 18 elementos é:
a) 360 
*b) 190 
c) 180 
d) 120 
e) 18
07 - Seis pessoas A,B,C,D,E,F ficam em pé uma ao lado da outra, para uma fotografia. Se A e B se recusam a ficar lado a lado e C e D insistem em aparecer uma ao lado da outra, o número de possibilidades distintas para as 6 pessoas se disporem é:
a) 120 b) 72 c) 144 d) 156 *e)192
08 - Quantas diagonais contém o hexaedro constituído por 6 faces triangulares obtido pela união de duas pirâmides triangulares?
Resp: 01
09 - PUC-SP) Dispõe-se de 6 jogadores de voleibol, entre os quais o jogador A. Quantas duplas diferentes podemos formar nas quais não apareça o jogador A?
a) 8 b) 5 *c) 10 d) 6 e) 16
10 - UFCE) Considere os números inteiros maiores que 64000 que possuem 5 algarismos, todos distintos, e que não contém os dígitos 3 e 8. A quantidade desses números é:
*a) 2160 
b) 1320 
c) 1440 
d) 2280 
e) 2400
11 - Provenientes das permutações dos algarismos 1,2,2,2,3,4, quantos números pares de 6 algarismos existem?
Resp: 80
12 - De quantos modos podemos dispor em linha e alternadamente, 5 rapazes e 6 moças?
Resp: 86400.
13 - Quantos são os números de 5 algarismos distintos, menores que 30.000, formados com os algarismos 1,2,3,4,5?
Resp: 48
14 - Formados e dispostos em ordem crescente todos os números que se obtêm permutando os algarismos 3,5,7,9, o número 7.953 ocupa a n-ésima posição. O valor de n é:
*a) 18 
b) 16 
c) 17 
d) 19 
e) 20
15 - Consideram-se 7 pontos num plano, dos quais 3 quaisquer não colineares; consideram-se, ainda, dois outros pontos fora do plano, tais que a reta por eles definida não contenha qualquer dos 7 anteriores, e seja reversa com qualquer reta definida pelos mesmos 7 pontos. Quantos tetraedros distintos podemos formar com vértices nos pontos considerados?
Resp: 91
16) Sabe-se que os telefones de uma cidade são números de seis dígitos, onde o primeiro nunca é zero. Supondo-se que os números dos telefones passem a ter sete dígitos, determine o aumento possível na quantidade de telefones dessa cidade.
Resp: 8.100.000
17) Dois grupos de excursionistas, um deles com 20 pessoas e o outro com 15, encontram-se em um certo local de um país distante. Se todas as pessoas de um grupo cumprimentarem todas as pessoas do outro grupo, qual o número total de cumprimentos?
Resp: 300
18) Uma prova compõe-se de 6 questões de múltipla escolha com 5 alternativas cada. De quantos modos um aluno pode preencher o quadro de respostas, escolhendo as alternativas ao acaso?
Resp:15625
19) Em uma cidade, as placas dos automóveis são formadas por duas das 26 letras do alfabeto, seguidas de 4 algarismos. Placas com letras iguais são proibidas, mas não há qualquer restrição quanto aos algarismos. Quantas placas diferentes são possíveis?
Resp: 6.500.000
20) Um salão tem 6 portas. De quantos modos distintos esse salão pode estar aberto?
Resp: 63 
Cuidado: não pense que são 64 modos! Lembre-se de retirar a opção de todas as portas fechadas!





25- Uma prova consta de 15 questões, das quais um aluno pode escolher 10 e resolvê-las.Mas de quantas formas diferentes ele pode escolher estas 10 questões?
Resp.3003
Resolução: como o problema não especifica uma ordem para as questões é so fazer. C10,5=3003
26-De quantos modos podemos dispor em fila 5 pessoas, entre as quais duas gêmeas indistinguíveis?
Resolução:
Temos 5 elementos para permutar.Considerando pela informção que temos é que os gêmeos são iguais,logo:
P5/2 ou seja. 5.4.3.2 , que vale 60
                          2


27- Quantos anagramas da palavra PIRADO:
a- começam com vogal
b- começam e terminam com vogal
Resolução
PIRADO tem 6 letras, 3 vogais ,então;

--  --  --   --   --   --, podem começar com i,a,d, logo temos 
3xP5
que vale 3.5.4.3.2.1=360
Logo temos 360 anagramas que começam por vogais
b-Para a 1ª casa temos 3 possibilidades e para a última 2, pois não pode começar e terminar com a mesma vogal.                                                    

===  ====   ======  ====   =====   == 
vogal                                                      vogal
então temos 3.P4 .2= 144 anagramas.

 28-Quantas palavras de 3 letras ,sem repetição podemos formar com as 9 primeiras letras do alfabeto?
Resolução:   9x8x7=504
29- Comn os algarismos 1,2,3,4,5,e 6 são formados nº s de 4 algarismos distintos. Dentre eles quantos são divisisíveis por 5?
R. ----   ----    -----     5   fixamos o 5 pois o número é divisivéis por 5 logo temos 5 números para  3 posições logo o cálculo é
A5,3 ou 5.4.3=60

30-Quantos nºs são compreendidos entre 2000 e 3000 formados por algarismos distintos,escolhidos entre 1,2,3,4,5,6,7,8,e 9?

R.Entre 2000 e 3000 são números formados por 4 algarismos e que obrigatóriamente começam por 2.
2   ===   ===   === , 8.7.6=336.

31- Considere o conjunto A={2,4,5,6}.
a-Calcule quantos números com algarismos diferentes podemos formar com esses elementos de A.
b-Dos  números obtidos quantos são múltiplos de 5?
 R. Temos números com 1,2,3,4 algarismos que são:
Com  1 algarismo = 4 números
Com 2 algarismos= 4.3=12 números
Com 3 algarismos= 4.3.2=24 números
Com 4 algarismos= 4.3.2.1=24 números
 Total= 64 números.
c- Mútiplos de 5,
 Com 1 algarismo temos 1,
Com 2 algarismos temos, ---  5,  3 números
Com 3 algarismos temos ---   ----   5 = 3.2=6 números
Com 4 algarismos temos ---   ----   ---- 5  =3.2.1=6 números.
Total= 16 números.
32- Cinco homens e uma mulher pretendem tilizar um banco de 5 lugares.De quantos modos diferentes podem sentar-se nunca ficando a mulher em pé?

R. A mulher está sempre sentada em qualquer das cinco posições,
m   m      m   m  m  ,vai sobrar então 4 lugares para 5 homens,logo temos ==   ===  ===   ===  5.4.3.2=120 lugares, mas a mulher ocupa 5 posições diferentes logo as possilidades da mulher são 5, portando o resultado final é= 5.120=600 modos.

33- Numa sala de aula temos 5 rapazes e 6 moças.Quantos grupos podemos formar de 2 rapazes e 3 moças?

R-C5,2..C6,3= 10.20=200 grupos

34-Quantos números pares podemos obter permutando os algarismos do nº 83137683?

R. Sé devemos considerar os números que terminam em 6 ou 8 para a posição final.
== === == == == == == 6,as demais posições deverão ser preenchidas pelos algarismos 8313783,logo temos uma permutação com repetição.
P72,3=7!/2!.3!= 420.
 Os que terminam em 8 são da forma:

== == == == == == == 8 = P73= 840
logo o total será 420 +840= 1260 números pares.

35- Diga quantas soluções naturais tem a equação x+y+z=7

R- Seja x=1,y=2 e z=4 ,logo temos x+y+z=7 e representaremos da seguinte forma.
1=1
2=11
4=1111 
então nossa equação fica desta forma 1+ 11+ 1111=7, 
agora contamos os seus elementos.
E temos P92,7= 9!/2!.7!= 36 soluções.

36-Quantos nºs de 4 algarismos podemos formar com os algarismos 0,1,2,3,4,5,6,7,8,9?
R. Em primeiro lugar o número para ter quatro dígitos,não poderá começar por zero.
Então as possibilidades são 9.10.10.10.= 9000.

37-Quantos números de 4 algarismos distintos podem ser formados com os números 0,1,2,3,4,5,6,7,8,9.
R. 9.9.8.7= 4.536

38-Em nosso sistema de numeração .Quantos números de 3 algarismos existem?
a) distintos.
b) de 3 algarismos.
 a)- De 0 a 9 temos 10 números, logo temos: 9.9.8= 648.
 b)- 9.10.10=900.

39- No sistema de numeração decimal :
23-Determine o numero de soluções inteiras e não negativas da equação linear:
x+y+z+w=5
Resp.56

Resoluçao- Primeiramente devemos escrever a soma de uma forma que nos convém para resolver o exercício,por exemplo  1+1+1+2=5,então temos neste caso x=1,y=1, z=1 e w=2, agora separamos o número da seguinte forma: 1 + 1 +1+ 11, agora contamos quantos  1 temos e quantos sinais de mais e fazemos esta permutação com repetição, então temos:
P85,3=       8 !/5!.3!= 8.7.6.5.!  =  56
                                  5!.3!

  



24- Numa pastelaria são vendidos pastéis de carne,queijo e frango.De quantas maneiras uma pesoa pode escolher 5 pastéis?
Resp-21




a- Quantos são os números pares?
b- Quantos são os números impares?
c- Quantos são os divisivéis por 5.
 R.Obs. os números serão em todos os casos de 3 algarismos,e distintos.
a- os números pares são, 0,2,4,6,8
==  == 0        9.8=72

==   ==2        8.7=56

==   ==4        8.7=56

==   ==6        8.7=56
                 total= 240
Alguns erros comuns em problemas de probabilidades: 


Querer achar que todos os espaços amostrais são finitos
V. precisa ter em vista que existem três tipos possíveis de espaços amostrais e precisa ver, em cada problema concreto, qual o tipo adequado.
Incidentalmente, os tais três tipos de espaços amostrais são:

· conjuntos discretos finitos 
· conjuntos discretos infinitos ( enumeráveis )
exemplos :
Experimento = atiro sucessivamente uma moeda e vou contando até sair cara
Espaço amostral = { 1,2,3,4,... } = inteiros positivos
Experimento = contamos os números de chamadas telefônicas que chegam, num minuto, numa dada central
Espaço amostral = { 0,1,2,3,4,... } 
· conjuntos contínuos ( um intervalo, um pedaço de superfície, etc )
exemplo :
Experimento = meço a altura dos habitantes de uma cidade
Espaço amostral = intervalo [ 0 , 3 ] ( em metros ) ( podia ser [ 0 , 5] e etc )
Experimento = meço a duração de baterias da marca XYZ
Espaço amostral = intervalo [ 0 , infinito ) ( em horas )

Uma das razões de ser importante identificar o tipo de espaço é que nos casos de espaços discretos a determinação do "tamanho" do espaço amostral e do conjunto de eventos favoráveis é feita via contagem, mas no caso contínuo essa determinação é feita por medida ( de comprimento, de área, de volume, etc ). 

exemplo
Sorteamos um número do intervalo [ 0 , 8 ] . Qual a probabilidade de que o resultado esteja no subintervalo [ 4 , 6 ] ?

Obviamente, estamos num caso de espaço amostral contínuo. Infelizmente, uma grande quantidade de pessoas insiste em querer resolver o problema como se o mesmo fosse um de espaço amostral finito. Esses acabam obtendo o valor 1 para a probabilidade, em vez do correto 2 / 8 = 1 / 4. 
Erro na determinação do conjunto dos eventos favoráveis 

exemplo
De um baralho, foram escolhidas 3 cartas ao acaso. Qual a probabilidade de não sair nenhum ás ?

Solução errada :
número total de possibilidades = C ( 52 , 3 ) e como há 48 possibilidades de a primeira carta não ser ás, 47 de a segunda não ser ás e 46 de a terceira igualmente não ser ás, segue que a probabilidade é:
	48 . 47 . 46 

C ( 52 , 3 )


razão do erro :
o conjunto dos eventos favoráveis não é o dos arranjos A ( 48 , 3 ), mas sim o das combinações C ( 48 , 3 ), de modo que a probabilidade é:
	C ( 48 , 3 ) 

C ( 52 , 3 )


 

Em problemas de probabilidades,
o que fazer quando a solução complica ? 


No caso de problemas de probabilidades envolvendo espaços amostrais finitos, é bastante comum que as pessoas acabem "se enrolando" na enumeração do espaço ou dos eventos favoráveis. Com efeito, normalmente essas enumerações envolvem raciocínios combinatórios e esses tendem a ter sutilezas. Ora, como as questões de vestibular são fáceis, a dica básica é: 

se o caminho escolhido começa a parecer dificultoso ou a produzir muita complicação, como muitos tipos de casos, pense em um outro modo de resolver o problema 
Exemplo 1
Jogando com um par de dados honestos, quantos lances são necessários para que tenhamos uma chance favorável ( ou seja, de no mínimo 50% ) de obtermos, ao menos uma vez, um duplo-seis?
DICA:
Se tentarmos enumerar os modos de em n lances obtermos, ao menos uma vez, o duplo-seis provavelmente vamos nos complicar. Em vez da fazer isso, observe que é muito fácil enumerar os modos de nunca obter o duplo-seis.
Resposta do problema original : 25 lances 
Exemplo 2
Em um programa de TV, o participante sorteado disputa um valioso prêmio. Para tal, ele tem de escolher uma dentre 3 portas, cada uma das quais esconde um prêmio. Sabe-se que uma das portas tem prêmio valioso e as outras duas tem prêmios baratos. Quando o participante anuncia sua decisão, o apresentador abre uma outra porta, sempre com prêmio barato, e diz ao participante que ele tem a opção de ficar com a porta que escolheu ou trocar para a outra porta não aberta.
Pergunta-se: o participante tem mais chance de ganhar o prêmio valioso se trocar de porta ou se ficar com sua escolha original ?
DICA:
A sutileza do problema está na dificuldade de avaliarmos o grau de dependência entre a primeira escolha e a segunda ( observe que o apresentador só pode abrir a primeira porta depois de o participante anunciar sua primeira escolha ). 
Há, contudo, um modo bem simples de evitarmos essa dificuldade: basta observarmos que a soma das probabilidades dos possíveis eventos é um e calcular as parcelas fáceis em:
( prob do partic escolher a porta certa na primeira escolha ) + ( prob do partic escolher a porta certa na segunda escolha ) + ( prob de que o apresentador abra a porta do prêmio valioso ) = 1
Conclusão ? Vale a pena trocar de porta, pois que 2/3 > 1/3 . 
outra DICA:
Muitas pessoas acham que o participante deve escolher qualquer porta e esperar para o apresentador abrir a sua e então escolher, com 50% de chance, entre as duas não abertas. Já dissemos que o apresentador abre a primeira porta só depois do participante ter feita a primeira escolha, de modo que o valor 50% acima está errado. Para conseguir ver isso com clareza, usemos o seguinte artifício:
Suponha que houvessem 1 000 portas e que o apresentador abrisse 998 delas, todas com prêmios baratos, será que ainda seria de 50% a chance na segunda escolha ? 


 



Permutação Simples: É um caso particular de arranjo simples. É o tipo de agrupamento ordenado onde entram todos os elementos.






Combinação Simples: é o tipo de agrupamento em que um grupo difere do outro apenas pela natureza dos elementos componentes.