28
Prof.: Rodrigo Carvalho ANÁLISE COMBINATÓRIA

Análise+c

Embed Size (px)

Citation preview

Prof.: Rodrigo Carvalho

ANÁLISE COMBINATÓRIA

Prof.: Rodrigo Carvalho

A análise combinatória é a parte da matemática que estuda a quantidade de possibilidades de ocorrência de um acontecimento, sem que haja a necessidade de descrever todas as possibilidades de ocorrência.

Para explicarmos esse estudo podemos fazer uma análise da situação descrita a seguir.

Trata-se de um ramo matemático com parte teórica relativamente curta, sendo sua maior dificuldade a interpretação dos problemas propostos envolvendo diferentes situações de contagem.

Prof.: Rodrigo Carvalho

Consideremos a figura abaixo, em que temos parte da planta de um bairro. Uma pessoa deve caminhar de sua casa à escola onde estuda, usando um dos caminhos mais curtos, isto é , ela só poderá caminhar “da esquerda para a direita”ou “de baixo para cima”. Quantos são os possíveis caminhos diferentes para esse percurso?

Prof.: Rodrigo Carvalho

Para resolvermos esse problema, a primeira idéia que temos é a de tentarmos descrever todos os caminhos possíveis, o que facilmente descartamos dada a grande quantidade de possibilidades.

Esse e muitos outros problemas serão resolvidos através de regras de contagem, que não exigem a descrição das possibilidades, isto é, descobrimos quantas são sem necessariamente sabermos quais.

Prof.: Rodrigo Carvalho

PRINCÍPIO FUNDAMENTAL DA CONTAGEM (PFC)

Exemplo: Uma pessoa possui dois pares de sapatos, três calças e duas camisas. De quantas maneiras distintas essa pessoa pode se vestir usando um par de sapatos, uma calça e uma camisa?

Prof.: Rodrigo Carvalho

A regra que utilizamos para resolver uma situação como a proposta é a do Princípio Fundamental da Contagem (PFC), que pode ser enunciada genericamente do seguinte modo:

Se um acontecimento pode ser analisado em etapas sucessivas e independentes de modo que:

Então n1 · n2 · n3 · ...· nk é o número de possibilidades de ocorrência do acontecimento.

- n1 é o número de possibilidades na 1a etapa;- n2 é o número de possibilidades na 2a etapa; ......................................................................- nk é o número de possibilidades na k-ésima etapa.

Prof.: Rodrigo Carvalho

No exemplo inicial, teríamos:

Par de sapatos Calça Camisa

2 3 2 x 12 = x

Logo, existem 12 maneiras distintas para essa pessoa se arrumar utilizando uma peça de cada tipo.

Prof.: Rodrigo Carvalho

Outros exemplos:

Ex1: Uma sala possui dez portas. De quantas maneiras distintas uma pessoa pode:

a) Entrar e sair dessa sala?

b) Entrar na sala e sair por uma porta diferente da que entramos?

Ex2: Numa competição de ciclismo, há 7 atletas. Sabendo que não pode haver empate, de quantas maneiras distintas podemos ter os três primeiros colocados?

Prof.: Rodrigo Carvalho

Ex3: No crachá de identificação dos funcionários de uma empresa, cada funcionário é representado por uma sequência constituída por 2 vogais e 3 algarismos distintos, nesta ordem. Quantos funcionários podem ser registrados dessa forma?

Ex4: Num jogo de cara ou coroa, uma moeda é lançada sucessivamente 3 vezes. Quantas são as possíveis sequências para esse evento?

Prof.: Rodrigo Carvalho

Ex5: Para ir de uma cidade A para uma cidade B, há 3 caminhos possíveis, e da cidade B para a C, 5 vias possíveis. Determine:

a) O número de possibilidades de irmos da cidade A até a cidade C, passando por B.

b) O número de possibilidades de irmos da cidade A até a cidade C, voltando à A, passando por B na ida e na volta.

c) O número de possibilidades de irmos da cidade A até a cidade C, voltando à A, passando por B na ida e na volta, sem usar na volta as mesmas vias da ida.

Prof.: Rodrigo Carvalho

*OBS: Princípio da preferência

Se uma situação de contagem trouxer alguma restrição(uma condição especial), a primeira etapa deverá sempre satisfazer tal restrição. Se houver mais de uma restrição, daremos preferência para iniciar a contagem do ponto em que a restrição for maior.

Ex1: Usando apenas os algarismos 1, 2, 6, 7 e 8, quantos números pares de três algarismos distintos podemos representar?

Ex2: Duas moças e três rapazes vão formar uma fila.De quantas maneiras a fila pode ser formada, se no meio da fila deve sempre ficar uma moça?

Prof.: Rodrigo Carvalho

FATORIAL (!)

É frequente nos problemas em análise combinatória, encontrarmos produtos com todos os fatores partindo de um número positivo n até 1, a exemplo de 5.4.3.2.1 . Para abreviarmos tais multiplicações, usaremos o FATORIAL.

Definição: Sendo n um número natural, definimos como fatorial de n, representado por n!, o produto de todos os naturais, desde n até 1.

n! = n . (n-1) . (n-2) . ... . 3 . 2 . 1

Prof.: Rodrigo Carvalho

Exemplos:

2! = 2 . 1 = 23! = 3 . 2 . 1 = 6

4! = 4 . 3 . 2 . 1 = 24

5! = 5 . 4 . 3 . 2 . 1 = 120

6! = 6. 5 . 4 . 3 . 2 . 1 = 720

Observação: Ao desenvolvermos um fatorial, colocando os fatores em ordem decrescente, podemos interromper o desenvolvimento de acordo com nossa conveniência, indicando apenas o último fator com a notação de fatorial.

*OBS: 1! = 1 0! = 1

Prof.: Rodrigo Carvalho

ARRANJOS SIMPLES (An,p)

São agrupamentos que diferem uns dos outros pela NATUREZA ou pela ORDEM dos elementos que os compõem.

Exemplo: Os números formados por dois algarismos distintos escolhidos entre 1, 2 e 3 são: 12, 13, 21, 23, 31 e 32.

Os seis resultados possíveis são diferentes por usarem algarismos diferentes(natureza) ou por usarem os mesmos algarismos em outra posição(ordem).

Prof.: Rodrigo Carvalho

Seja An,p o número de arranjos que podem ser feitos com n elementos, agrupando-os p a p.

A fórmula para o cálculo do número desses arranjos é dada por:

An,p = n!

(n - p)!com 0 < p < n, sendo n,p N.

Prof.: Rodrigo Carvalho

COMBINAÇÕES SIMPLES (Cn,p)

São agrupamentos que diferem uns dos outros apenas pela NATUREZA dos elementos que os compõem.

Exemplo: Os subconjuntos com dois elementos escolhidos do conjunto {1 , 2 , 3} são:

{1 , 2}, {1 , 3} e {2 , 3}.

Os três resultados possíveis são diferentes apenas pela natureza diferente de seus elementos.

Prof.: Rodrigo Carvalho

Seja Cn,p o número de combinações que podem ser feitas com n elementos, agrupando-os p a p. A fórmula para o cálculo do número dessas combinações é dada por:

Cn,p = n!

(n - p)!.p!com 0 < p < n, sendo n,p N.

Prof.: Rodrigo Carvalho

*Observações:

I. An,p Cn,p = p!

II.

III.

Cn,n = 1

Cn,0 = 1

IV. Cn,1 = n

Prof.: Rodrigo Carvalho

PERMUTAÇÕES(Pn)

São agrupamentos que diferem uns dos outros apenas pela ORDEM dos elementos que os compõem.

Exemplo: Os números formados por três algarismos distintos escolhidos entre 1, 2 e 3 são: 123, 132, 213, 231, 312 e 321.

Os seis resultados possíveis são diferentes apenas pela ordem diferente de seus elementos.

Prof.: Rodrigo Carvalho

Seja Pn o número de permutações que podem ser feitas com n elementos.

A fórmula para o cálculo do número dessas permutações é dada por:

Pn = n!

com n N.

É importante perceber que a permutação é um caso particular de arranjo, ou seja, é um arranjo no qual n = p.

Prof.: Rodrigo Carvalho

(2009)

Prof.: Rodrigo Carvalho

Exercícios:

1. Para ocupar os cargos de presidente e vice-presidente do grêmio de um colégio, candidataram-se dez alunos. De quantos modos distintos pode ser feita essa escolha?

2. (UFPB) Um sorveteiro vende sorvetes de três bolas, que devem ser escolhidas entre os sabores de coco, manga, graviola, cajá, acerola, maracujá e pitanga. Quantos sorvetes com 3 sabores distintos podem ser feitos por esse sorveteiro?

Prof.: Rodrigo Carvalho

3. Sobre uma circunferência são marcados cinco pontos distintos. Quantas retas distintas podemos determinar com esses pontos?

4. De quantas maneiras distintas podemos arrumar sete amigos em uma fila?

5. Quantos são os anagramas da palavra VESTIBULAR que começam com a letra R?

Prof.: Rodrigo Carvalho

6. (Unifor-CE) O número natural n que satisfaz a equação 3 + An,2 = P4 + Cn,2 é tal que:

a) 2n = 16b) n – 1 = 5c) n = 7d) n = -6e) 3n = 18

Prof.: Rodrigo Carvalho

7. De quantas maneiras distintas podemos arrumar 6 amigos numa fila, de formas que Ana e Bruno sempre fiquem juntos?

8. Determine a quantidade de anagramas da palavra RADIOLA que:

a) começam com R e terminam com I;

b) tenham R e I nas extremidades;

c) tenham as vogais sempre juntas;

d) tenham a sílaba DI;

e) Possuam as vogais sempre separadas.

Prof.: Rodrigo Carvalho

9. Numa empresa de tecnologia há 6 brasileiros e 4 japoneses. Quantas comissões com 5 pessoas podem ser formadas, de maneira que sejam 3 brasileiros e 2 japoneses?

10. Uma pizzaria possui 11 sabores de pizza. Sabendo que as pizzas possuem, no máximo, 3 sabores, quantos tipos de pizzas diferentes podem ser feitos nessa pizzaria?

11. Um edifício possui 26 condôminos aptos a assumirem um cargo admnistrativo. Pretende-se eleger um síndico, um sub-síndico e três secretários. Quantas comissões distintas podem ser formadas?

Prof.: Rodrigo Carvalho

Prof.: Rodrigo Carvalho