Matemática: Análise Combinatória

Mostrando postagens com marcador Análise Combinatória. Mostrar todas as postagens

Arranjos simples

Vimos que permutação simples de n elementos é qualquer agrupamento ordenado desses n elementos. Agora, tendo n elementos, vamos estudar os agrupamentos ordenados de 1, 2, 3, ..., p elementos com p e n naturais e p ≤ n.

Exemplo:

Consideremos as letras a, b, c e d. Quais e quantos agrupamentos ordenados diferentes de 2 letras distintas é possível formar com elas?

Resolução:

Na primeira posição temos 4 possibilidades (pois temos 4 elementos disponíveis). Na segunda posição, 3 possibilidades (pois temos 3 elementos disponíveis). Pelo princípio fundamental da contagem, há, no total, 4 . 3 = 12 possibilidades.

Os 12 agrupamentos ordenados diferentes são: ab, ba, ca, da, ac, bc, cb, db, ad, bd, cd e dc.

Esses agrupamentos são chamados arranjos simples. Arranjamos 4 elementos 2 a 2, e o número desses arranjos foi 12. Escrevemos então:

(arranjo de 4 elementos tomados 2 a 2 é igual a 12)

Fórmula do número total de arranjos simples

Arranjos simples de n elementos tomados p a p (p ≤ n) são os agrupamentos ordenados diferentes que se podem formar com p dos n elementos dados.

Exemplo:
Luciana tem 5 livros de romance e decidiu lê-los, todos, antes que chegue as férias escolares. Porém, ela enfrenta um dilema: por qual livro começar a ler? Para solucionar seu impasse, resolveu escolher 3 dentre os 5 e levar para escola com a esperança de que sua professora faça a indicação final. De quantas maneiras ela poderá escolher esses livros?

Resolução:

Portanto, ela poderá fazer essa escolha de 60 maneiras diferentes.

Importante: Você pode usar tanto a fórmula de arranjo como o princípio fundamental da contagem para resolver problemas.

Permutações

Permutar é sinônimo de trocar. Intuitivamente, nos problemas de contagem, devemos associar a permutação à noção de embaralhar, isto é, trocar objetos de posição.

Permutações Simples

Para determinarmos o número de agrupamentos de uma permutação simples utilizamos a seguinte expressão:

P = n!

Exemplo:

Quantos são os anagramas (diferentes disposições das letras de uma palavra) da palavra A N E L?
Resolução:

4 . 3 . 2 . 1

Considerando as quatro letras: A, N, E e L, há 4 possibilidades para a primeira posição, 3 possibilidades para a segunda, 2 possibilidades para a terceira e 1 possibilidade para a quarta posição. Pelo princípio fundamental da contagem, temos 4! = 4 . 3 . 2 . 1 = 24 anagramas.

Permutações com repetição

Exemplo:

Quantos são os anagramas da palavra BATATA?

Resolução:

Se os "As" fossem diferentes e os "Ts" também, teríamos as letras B, A1 , A2, A3, T1 , T2, e o total de anagramas seria 6!. Mas as permutações entre os 3 As não produzirão novo anagrama. Então precisamos dividir 6! por 3!. O mesmo ocorre com os dois "Ts": precisamos dividir também 6! por 2!. Portanto, o número de anagramas da palavra BATATA é:

Generalizando temos:

Exemplo 1:

Quantos são os anagramas da palavra ARARA?

Resolução:

Exemplo 2:

Quantos anagramas da palavra CAMARADA começam com A?

Resolução:

Princípio da multiplicação

(ou princípio fundamental da contagem)

Definição:
Se um evento é composto de duas etapas sucessivas e independentes de tal maneira que o número de possibilidades na 1ª etapa é m e para cada possibilidade da 1ª etapa o número de possibilidades na 2ª etapa é n, então o número total de possibilidades de o evento ocorrer é dado pelo produto:

m x n.

Vamos aos exemplos:

Exemplo 1

Uma pessoa quer viajar de Recife a Porto Alegre passando por São Paulo. Sabendo que há 5 roteiros diferentes para chegar a São Paulo partindo de Recife e 4 roteiros diferentes para chegar a Porto Alegre partindo de São Paulo, de quantas maneiras possíveis essa pessoa poderá viajar de Recife a Porto Alegre?

Esquematizando:

Note que há 5 possibilidades para viajar de Recife a São Paulo e 4 possibilidades para viajar de São Paulo a Porto Alegre. Desse modo, o total de possibilidades para viajar de Recife a Porto Alegre é:

5 . 4 = 20

Esse é o Princípio Fundamental da Contagem na prática! Agora ficou simples, né?

Exemplo 2

Em um restaurante há 2 tipos de salada, 2 tipos de pratos quentes e 3 tipos de sobremesa. Quais e quantas possibilidades temos para fazer uma refeição com 1 salada, 1 prato quente e 1 sobremesa?

Esquematizando (diagrama de árvore):

Portanto, o número total de possibilidades é 2 . 2 . 3 = 12.

Exercícios Resolvidos:

01- Com os algarismos 0, 1, 2, 3, 4, 5, 6 e 7, quantos números de 3 algarismos podemos formar?

Resolução:

8 . 8 . 7

Existem 8 algarismos de 0 a 7. Há 7 possibilidades para a centena (0 não é permitido), 8 para a dezena e 8 para a unidade. Portanto, podemos formar 8 . 8 . 7 = 448 números.

02- Com os algarismos 0, 1, 2, 3, 4, 5, 6 e 7, quantos números de 3 algarismos distintos podemos formar?

Resolução:

7 . 7 . 6

Com 3 algarismos distintos, há 7 possibilidades para a centena, 7 para a dezena e 6 para a unidade. Portanto, podemos formar 7 . 7 . 6 = 294 números.

03- Qual é o total de números de três dígitos distintos?

Resolução:

Temos 10 dígitos: 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. O primeiro dígito pode ser escolhido de 9 maneiras, pois ele não pode ser igual a 0. O segundo dígito pode ser escolhido de 9 maneiras, pois não pode ser igual ao primeiro dígito. O terceiro dígito pode ser escolhido de 8 maneiras, pois não pode ser igual nem ao primeiro nem ao segundo dígito. Assim, temos: 9 . 9 . 8 = 648 números com algarismos distintos.

Fatorial de um número natural

Dado um número natural n, definimos o fatorial de n (indicado por n!) por meio das relações:

0! = 1

1! = 1

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

Assim, temos, por exemplo:

2! = 2 . 1 = 2

3! = 3 . 2 . 1 = 6

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

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

01- De quantas maneiras distintas podemos organizar uma fila indiana com apenas 3 pessoas?

a) 1

b) 3

c) 4

d) 5

e) 6

02- De quantas maneiras distintas podemos organizar uma fila indiana com apenas 4 pessoas?

a) 4

b) 12

c) 16

d) 24

e) 36

03- Quantos são os anagramas da palavra AMOR?

a) 4

b) 12

c) 16

d) 24

e) 36

04- Quantos são os anagramas da palavra AMOR que terminam com vogal?

a) 4

b) 12

c) 16

d) 24

e) 36

05- Determine o número de anagramas que podem ser formados com as letras do nome ALEMANHA

a) 4040

b) 4820

c) 5040

d) 6720

e) 40320

06- Quantos são os anagramas da palavra AMORA?

a) 60

b) 72

c) 96

d) 120

e) 144

07- Quantos são os anagramas da palavra AMORA que começam por A?

a) 24

b) 72

c) 96

d) 120

e) 144

08- Quantos são os anagramas da palavra AMORA que terminam com vogal?

a) 24

b) 36

c) 72

d) 112

e) 120

09- O número de anagramas da palavra NÚMERO, em que nem vogal, nem consoantes fiquem juntas é:

a) 12

b) 36

c) 48

d) 60

e) 72

10- Em um torneio de futsal um time obteve 8 vitórias, 5 empates e 2 derrotas, nas 15 partidas disputadas. De quantas maneiras distintas esses resultados podem ter ocorrido?

a) 67.568

b) 270.270

c) 135.135

d) 16.216.200

e) 32.432.400

11- Em uma prova composta de 10 questões envolvendo V ou F, de quantas maneiras distintas teremos 6 respostas V e 4 respostas F?

a) 210

b) 5040

c) 720

d) 420

e) 151200

12- O número de anagramas da palavra FUVEST que terminam por vogal é:

a) 24

b) 48

c) 96

d) 120

e) 240

13- O número de anagramas da palavra FUVEST que começam e terminam por vogal é:

a) 24

b) 48

c) 96

d) 120

e) 144

14- Dentre as permutações das letras da palavra TRIÂNGULO, o número das que começam por vogal é:

a) 4 . 9 !

b) 4 . 8 !

c) 8 !/4 !

d) 9 !

e) 8 !

15- Quantos números de cinco algarismos podemos escrever apenas com os dígitos 1, 1, 2, 2 e 3 respeitadas as repetições apresentadas?

a) 12

b) 30

c) 6

d) 24

e) 18

Respostas:

01) E 02) D 03) D 04) B 05) D

06) A 07) A 08) B 09) E 10) C

11) A 12) E 13) B 14) B 15) B

01- Quantos anagramas da palavra PALCO podemos formar de maneira que as letras A e L apareçam sempre juntas?

a) 48 b) 24 c) 96

d) 120 e) 36

02- O número de anagramas de 6 letras que podemos formar com as letras da palavra PEDRAS, começando e terminando com uma letra que represente consoante, é:

a) 72 b) 480 c) 192

d) 432 e) 288

03- Sobre uma mesa são colocadas em linha 6 moedas. O número total de modos possíveis pelos quais podemos obter 2 caras e 4 coroas voltadas para cima é:

a) 360 b) 48 c) 30

d) 120 e) 15

04- Quantos anagramas da palavra SUCESSO começam por S e terminam com O?

a) 7! b) 5! c) 30

d) 60 e) 90

05- O número de maneiras diferentes de colocar em uma linha de um tabuleiro de xadrez (8 posições) as peças brancas (2 torres, 2 cavalos, 2 bispos, a rainha e o rei) é:

a) 8! b) 504 c) 5040

d) 8 e) 4

06- Oito políticos foram convidados a participar de uma mesa em uma convenção. Os lugares eram contíguos e dispostos em linha, de um mesmo lado da mesa. Sabendo que o político A não suporta o político B, não podendo sentar juntos, de quantas maneiras a mesa poderá ser composta?

a) 56 b) 5040 c) 30240

d) 35280 e) 40320

07- O número de anagramas da palavra ALUNO que tem as vogais em ordem alfabética é:

a) 20 b) 30 c) 60

d) 80 e) 100

08- (Unitau 95) - O número de anagramas da palavra BIOCIÊNCIAS que terminam com as letras AS, nesta ordem é:

a) 9! b) 11! c) 9!/(3! 2!)

d) 11!/2! e) 11!/3!

09- (Fuvest 93) - A figura a seguir representa parte do mapa de uma cidade onde estão assinalados as casas de João(A), de Maria(B), a escola(C) e um possível caminho que João percorre para, passando pela casa de Maria, chegar à escola. Qual o número total de caminhos distintos que João poderá percorrer, caminhando somente para o Norte ou Leste, para ir de sua casa à escola, passando pela casa de Maria?

a) 90 b) 150 c) 45

d) 60 e) 210

10- (Fatec 95) - Seis pessoas, entre elas João e Pedro, vão ao cinema. Existem seis lugares vagos, alinhados e consecutivos. O número de maneiras distintas como as seis podem sentar-se sem que João e Pedro fiquem juntos é

a) 720 b) 600 c) 480

d) 240 e) 120

11- (Mackenzie 96) - Os anagramas distintos da palavra MACKENZIE que têm a forma E.......E são em número de:

a) 9! B) 8! c) 2.7!

d) 9! -7! e) 7!

12- (Ufsc 96) - Calcule o número de anagramas da palavra CLARA em que as letras AR aparecem juntas e nesta ordem.

a) 6 B)12 c) 18

d) 24 e) 36

13- (Uff 97) - Com as letras da palavra PROVA podem ser escritos x anagramas que começam por vogal e y anagramas que começam e terminam por consoante. Os valores de x e y são, respectivamente:

a) 48 e 36 b) 48 e 72 c) 72 e 36

d) 24 e 36 e) 72 e 24

14- (Unesp 98) Quatro amigos vão ocupar as poltronas a, b, c, d de um ônibus dispostas na mesma fila horizontal, mas em lados diferentes em relação ao corredor, conforme a ilustração.

Dois deles desejam sentar-se juntos, seja do mesmo lado do corredor, seja em lados diferentes. Nessas condições, de quantas maneiras distintas os quatro podem ocupar as poltronas referidas, considerando-Se distintas as posições em que pelo menos dois dos amigos ocupem poltronas diferentes?

a) 24 b) 18 c) 16

d) 12 e) 6

15- (Ufrs 97) - Um trem de passageiros é constituído de uma locomotiva e 6 vagões distintos, sendo um deles restaurante. Sabendo-se que a locomotiva deve ir à frente, e que o vagão restaurante não pode ser colocado imediatamente após a locomotiva, o número de modos diferentes de montar a composição é:

a) 120 b) 230 c) 500

d) 600 e) 720

16- (Ita 98) - O número de anagramas da palavra VESTIBULANDO, que não apresentam as cinco vogais juntas, é:

a) 12! b) (8!) (5!) c) 12! - (8!) (5!)

d) 12! - 8! e) 12! - (7!) (5!)

17- (Puccamp 98) - O número de anagramas da palavra EXPLODIR, nos quais as vogais aparecem juntas, é:

a) 360 b) 720 c) 1.440

d) 2.160 e) 4.320

18- (Ufmg 2000) - Um clube resolve fazer uma Semana de Cinema. Para isso, os organizadores escolhem sete filmes, que serão exibidos um por dia. Porém, ao elaborar a programação, eles decidem que três desses filmes, que são de ficção científica, devem ser exibidos em dias consecutivos. Nesse caso, o número de maneiras DIFERENTES de se fazer a programação dessa semana é:

a) 144 b) 576 c) 720

d) 1040 e) n.d.a.

19- Um jogo é formado por 20 pontos, conforme a figura abaixo:

Qual o número total de possibilidade para "caminhar" de A a C, sabendo-se que só pode haver movimento na horizontal (da esquerda para a direita) ou na vertical (de cima para baixo), um espaço entre dois pontos de cada vez?

a) 35 b) 27 c) 42

d) 45 e) 22

20- Com base na figura do exercício anterior, qual a probabilidade de "caminhar" de A a C, passando por B, seguindo as regras do item a?

a) 19/35 b) 17/33 c) 19/33

d) 18/35 e) 17/35

21- (Unesp 2002) Quatro amigos, Pedro, Luísa, João e Rita, vão ao cinema, sentando-se em lugares consecutivos na mesma fila. O número de maneiras que os quatro podem ficar dispostos de forma que Pedro e Luísa fiquem sempre juntos e João e Rita fiquem sempre juntos é:

a) 2 b) 4 c) 8

d) 16 e) 24

Respostas:

Podemos considerar a permutação simples como um caso particular de arranjo, onde os elementos formarão agrupamentos que se diferenciarão somente pela ordem.

Tanto arranjo quanto Combinação são formas que a matemática, na análise combinatória, usa para agrupar elementos. Sendo que:

• Nos casos de arranjo a ordem dos seus elementos faz a diferença.

Exemplo:

Os números de três algarismos formados pelos elementos {1, 2 e 3} são: 312, 321, 132, 123, 213, 231. Esse agrupamento é um arranjo. Pois, por exemplo, os números 312 e 321 são diferentes. E é considerado simples, pois os elementos não se repetem.

• Nos casos de combinações a ordem dos seus elementos não faz a diferença. Pois, uma combinação simples pode ser definida como sendo um agrupamento dos elementos de um conjunto em subconjuntos. Dessa forma, subconjuntos com os mesmos elementos representam o mesmo subconjunto (exemplo: {A, E} = {E, A}) e devem ser considerados única vez na contagem.

Exemplo:

Quantos subconjuntos de 2 elementos podemos formar com os elementos do conjunto das vogais V = {A, E, I, O, U}?

Resolução:

{A, E}, {A, I}, {A, O},{A, U},

{E, I}, {E, O}, {E, U},

{I, O}, {I, U}.

{O, U}

Resposta: 10 subconjuntos.

Para determinarmos o número de agrupamentos de uma permutação simples utilizamos a seguinte expressão:

P = n!

Por exemplo: 4! = 4*3*2*1 = 24

Exemplo 1

Quantos anagramas podemos formar com a palavra GATO?

Resolução:

Podemos variar as letras de lugar e formar vários anagramas, formulando um caso de permutação simples. Logo, teremos: P = 4! = 24

Resposta: 24 anagramas.

Exemplo 2
De quantas maneiras distintas podemos colocar em fila indiana seis homens e seis mulheres:

a) em qualquer ordem

Resolução:

Podemos organizar as 12 pessoas de forma distinta, portanto utilizamos

12! = 12*11*10*9*8*7*6*5*4*3*2*1 = 479.001.600 possibilidades

b) iniciando com homem e terminando com mulher

Resolução:

Teremos 6 possibilidades na primeira posição (um dos homens a ocupará) e 6 possibilidades na última posição (uma das mulheres a ocupará). As 10 posições intermediárias serão ocupadas por uma permutação de 10!

Logo:

6 * 10! * 6 = 130.636.800 possibilidades

E AGORA?

AGORA É HORA
DE TREINAR!

O que ocorre quando permutamos elementos quando entre eles existem elementos repetidos?

Simples, alguns anagramas serão contados mais de uma vez.

Exemplo 1:

Quantos são os anagramas da palavra AMAR?

Vamos analisar... Se, eventualmente alguém ignorar o fato de a letra A aparecer duas vezes, essa pessoa realizará um cálculo de permutação simples, Isto é:

4! = 4*3*2*1 = 24

É evidente que o número de anagramas da palavra AMAR é um número inferior a 24, pois sempre que permutarmos as letras A de lugar encontraremos o mesmo anagrama (óbvio!). Na verdade os anagramas da palavra AMAR são em número de 12. Veja:

AMAR, AMRA, ARAM, ARMA,

AARM, AAMR, MAAR, MARA,

MRAA, RMAA, RAMA e RAAM.

Mas... Como fazer o cálculo sem precisar discriminar todas as possibilidade?

Fácil! Segue a "receita do bolo":

1- Calculamos a permutação simples (como se não houvesse elementos repetidos).

2- Dividimos o resultado pelo fatorial de das repetições.

3- Efetuamos as simplificações necessárias e "oalá" encontramos nossa resposta!

Observe:

Vamos voltar na pergunta anterior. Quantos são os anagramas da palavra AMAR?

Resolução: