ANÁLISE COMBINATÓRIA

Método de Mensuração da Quantidade de Opções Disponíveis

PRINCÍPIOS DE CONTAGEM: Complemento, Substituição ou Incerteza

1) PRINCÍPIO MULTIPLICATIVO: possibilidades que existem num evento com etapas independentes que sejam COMPLEMENTARES

- POSSIBILIDADES = # Eventos x # Etapas

- Conectivo "E" associa as etapas

Exemplo 1: Quais as possibilidades de vestir 1 sapato, 1 calça e 1 blusa quando há 2 sapatos, 3 calças e 4 blusas no guarda-roupa? Há 24 oções = 2 x 3 x 4.

Exemplo 2: Se 4 professores tem que escolher o dia de aplicação de suas provas entre 5 dias disponíveis, podendo estas provas serem marcadas num mesmo dia. Quantas maneiras há de organização deste calendário? Como podem ser marcadas no mesmo dia, cada professor tem 5 dias como opção, logo as possibilidades serão 5 x 5 x 5 x 5 = 625. Se não pudessem marcar no mesmo dia, ass opções iriam sendo eliminadas à medida que cada um marcasse a sua, logo seriam 5 x 4 x 3 x 2 = 120.

2) PRINCÍPIO ADITIVO: possibilidades que existem num evento com etapas alternativas que sejam SUBSTITUTIVAS

- POSSIBILIDADES = # Eventos + # Etapas

- Conectivo "OU" associa as etapas

Exemplo 1: Quais as possibilidades de se vestir entre 3 tênis e 2 sapatos que há num guarda-roupa? Há 5 oções = 3 + 2, dado que não podem ser vestidos 2 pares ao mesmo tempo.

Exemplo 2: Numa estante há 4 dicionários de inglês, 3 de espanhol e 2 de francês. Qual a possibilidade de escolha de 2 dicionários de idiomas diferentes? Há 3 escolhas a serem feitas que são alternativas, havendo escolhas independentes dentro de cada uma destas opções. Opção Inglês com Espanhol = 4 x 3 = 12. Opção Inglês com Francês = 4 x 2 = 8. Opção Espanhol com Francês = 3 x 2 = 6. São três alternativas a se combinarem, logo o total de possibilidades será 12 + 8 + 6 = 26.

Exemplo 3: Uma senha é formada aleatoriamente pelo sequenciamento de 4 letras escolhidas entre as opções A, E, O, B, C e D, sem repetições. Qual a probabilidade de que a senha tenha 2 vogais e 2 consoantes intercaladas? O total de possibilidades é 6 letras para a 1ª escolha, e 5 letras restantes para a 2ª escolha, e 4 letras restantes para a 3ª escolha, e 3 letras restantes para a 4ª escolha. Logo, é igual a 6 x 5 x 4 x 3 = 360. Há duas combinações possíveis de intercalação entre vogais e consoantes: V-C-V-C ou C-V-C-V. Para cada uma, sendo 3 vogais e 3 consoantes, as possibilidades são de 3 vogais para a 1ª escolha, e 3 consoantes para a 2ª escolha, e 2 vogais restantes para a 3ª escolha, e 2 consoantes restantes para a 4ª escolha. Logo, é igual a 3 x 3 x 2 x 2 = 36. O mesmmo se repete para a segunda opção. Como as possibilidades são V-C-V-C ou C-V-C-V, serão equivalentes a 36 + 36 = 72. Logo, a probabilidade desta combinação é de 72 opções em 360 escolhas possíveis: 72 / 360 = 20%.

3) PRINCÍPIO "CASA DOS POMBOS": possibilidades ou entre escolhas imprevisíveis, sem opções racionais (Escolhas Não São Racionais) ou entre escolhas em que não é possível dar uma certeza. HÁ SEMPRE INCERTEZA

- Só podem ser definidas a partir de um raciocínio de "PELO MENOS"

Exemplo 1: Se há um grupo de 21 pessoas, então se pode afirmar que pelo menos 3 nasceram no mesmo dia da semana. São 7 dias, logo 21 / 7 = 3. 

Exemplo 2: Se há um grupo de 22 pessoas, então se pode afirmar que pelo menos 4 nasceram no mesmo dia da semana. Serão 22 / 7 = 3 com resto 1 (3 + Resto = 4). O mesmo seria caso o grupo tivesse 23 pessoas, pois 23 / 7 = 3 com resto 2 (3 + Resto = 4).

* Para casos com "Dias do Mês" em Situações"Casa dos Pombos", sempre se devem usar 31 dias

FATORIAL: n! = n x (n - 1) x (n - 2) x (n - 3) x .... x 2 x 1

PRINCÍPIOS DE PERMUTAÇÃO: quando há Trocas de Lugar

- Situações que Obrigatoriamente sempre utilizam FATORIAL da # Elementos... com variações...

4) PERMUTAÇÃO SIMPLES: Não Há Elementos Repetidos e Não Há Elementos Iguais

- POSSIBILIDADES = Fatorial de # Elementos

P = n!

Exemplo 1: Há 5 pessoas que tem licença de conduzir a serem distribuídas de formas diferentes num carro de 5 lugares. Quantas possibilidades há para isso? Há 5! = 5 x 4 x 3 x 2 x 1 = 120 possibilidades diferentes.

Exemplo 2: Havendo 8 algarismos diferentes, sendo 4 pares e 4 ímpares, quantos números podem ser construídos com os pares em posições pares e os ímpares em posições ímpares? São 2 grupos de números independenpentes dentro dos quais há opções em que variam 4 elementos. Logo, dentro de cada grupo há 4! possibilidaes. Estes 2 grupos são complementres, logo para uni-los dá para usar o princípio de contagem, neste caso sendo multiplicativo. Assim, o Total de Possibilidades é igual a 4! x 4! = 24 x 24 = 576

Exemplo 3: Um grupo de 3 casais vão ao cinema e querem se sentar juntos por casal. Quantas possibilidades de de combinação há para a ocupação dos 6 lugares? Primeiro: cada casal se torna um único grupo de elementos que funcionam como um elemento individual, logo há 3! possibilidades. Só que cada casal pode mudar de posição dentro do seu subgrupo, logo, complementarmente, cada casal (cada subgrupo) representa um 2! independente a mais dentro da solução. Assim, as possibilidades são 3! x 2! x 2! x 2! = 6 x 2 x 2 x 2 = 48

5) PERMUTAÇÃO SIMPLES COM RESTRIÇÃO FIXA: restrições Sem Mudança de Posição

- POSSIBILIDADES = Fatorial de ( # Elementos menos # Restrições )

P = (n - r)!

* Restrições = Elementos Fixos entre as Possibilidades

Exemplo: Quantas opções diferentes de números existem que se iniciam com 1 seguido por um 2 que utilizem todos os algarismos possíveis sem repetições? Total de Algarismos = 10 (0 a 9). A restrição é a existência de 2 fixos (1 e 2). Logo, há 8 algarismos podendo variar de posição. O Total de Possibilidades então é igual a 8! = 40.320

6) PERMUTAÇÃO SIMPLES COM RESTRIÇÃO VARIÁVEL: restrições Com Mudança de Posição

- POSSIBILIDADES = Fatorial de ( # Elementos menos # Restrições ) x Fatorial de (# Restrições)

P = (n - r)! x r!

Exemplo: Quantas opções diferentes de números existem que se iniciando com 1 e 2, independente das posições destes, que utilizem todos os algarismos possíveis sem repetições? Total de Algarismos = 10 (0 a 9). A restrição é a existência de 2 fixos (1 e 2). Logo, há 8 algarismos podendo variar de posição. O Total de Possibilidades então é igual a (10 - 2)! x 2! = 8! x 2 = 40.320 x 2 = 80.640

7) PERMUTAÇÃO SIMPLES COM RESTRIÇÃO E ELEMENTOS JUNTOS NA MESMA ORDEM: quando alguns elementos de restrição precisam ser mantidos agrupados na mesma ordem

- POSSIBILIDADES = Fatorial de ( # Elementos menos # Elementos Agrupados mais 1)

P = (n - r + 1)!

Exemplo: Há 8 elementos distintos a serem ordenados, sendo que 3 deles tem que ser mantidos juntos na mesma ordem, independente da posição. A quantidade de possibilidades neste caso é (8 - 3 + 1)! = 6! = 720

8) PERMUTAÇÃO SIMPLES COM RESTRIÇÃO E ELEMENTOS JUNTOS EM QUALQUER ORDEM: quando alguns elementos de restrição precisam ser mantidos agrupados mas sem respeitar uma ordem

- POSSIBILIDADES = Fatorial de ( # Elementos menos # Elementos Agrupados mais 1) x Fatorial de (# Elementos Agrupados)

P = (n - r + 1)! x r!

Exemplo: Há 8 elementos distintos a serem ordenados, sendo que 3 deles tem que ser mantidos juntos na mesma ordem, mas variando de posição dentro do grupo. A quantidade de possibilidades neste caso é (8 - 3 + 1)! x 3! = 6! x 3! = 720 x 6 = 4.320

9) PERMUTAÇÃO SIMPLES COM REPETIÇÃO (não há agrupamento dos elementos)

- POSSIBILIDADES = Fatorial de ( # Elementos ) / Multiplicação dos Fatoriais de (# Elementos Repetidos)

P = n! / r! x r! x...

Exemplo 1: Quantas possibilidades de anagramas de três letras há para se fazer com as letras A e B, sendo que se pode repetir A. No total são 3 elementos. É possível e repetição de 2 elementos. Logo o número de possibilidades será 3! / 2! = (3 x 2!) / 2! = 3

Exemplo 2: Quantas possibilidades de anagramas de quatro letras há para se fazer com as letras A e B, sendo que se pode repetir cada letra 2 vezes. No total são 4 elementos. É possível e repetição de 2 elementos 2 vezes. Logo o número de possibilidades será 4! / (2! x 2!) = (4 x 3 x 2!) / (2! x 2!) = (4 x 3) / 2 = 2 x 3 = 6

Exemplo 3: Quantas possibilidades de anagramas há para se fazer com as letras A, B, C D usando todas as letras e podendo repetir A 2 vezes e repetir B 3 vezes. No total são 2 + 3 + 1 + 1 = 7 elementos, com a repetição de 1 elemento 2 vezes e de 1 elemento 3 vezes. Logo o número de possibilidades será 7! / (3! x 2!) = (7 x 6 x 5 x 4 x 3!) / (3! x 2!) = (7 x 6 x 5 x 4) / 2 = 7 x 6 x 5 x 2 = 420

10) PERMUTAÇÃO CIRCULAR SIMPLES (ordenamento circular sempre tem pelo menos 1 elemento fixo, de resto é sem repetição). É UMA PERMUTAÇÃO SIMPLES COM 1 REPETIÇÃO FIXA

- POSSIBILIDADES = Fatorial de ( # Elementos menos 1 )

P = (n - 1)!

Exemplo: Qual o número máximo de possibilidades que há para que 8 pessoas sentem em volta de uma mesa circular? As possibilidades são (8 - 1)! = 7! = 5.040

11) PERMUTAÇÃO CIRCULAR COM REPETIÇÃO FIXA (a fixação de alguns elementos transforma-a numa PERMUTAÇÃO SIMPLES dos elementos restantes). "QUEBRA-SE O CÍRCULO"

- POSSIBILIDADES = Fatorial de ( # Elementos menos 1 )

P = (n - r)!

Exemplo 1: Numa família de 5 pessoas, as posições do pai e da mãe numa mesa circular são sempre as mesmas. Quantas possibilidades diferentes há para o posicionamento da família na mesa a partir desta certeza? A solução circular para 5 elementos sendo 2 fixos é a mesma que para 3 elementos independentes. Logo, será (5 - 2)! = 3! = 6 

Exemplo 2: Há 4 meninos e 4 meninas para se sentsrem numa mesa circular, e todo menino tem que estar sentado entre 2 meninas. Quantas possibilidades de ordenamento na mesa existem? São 2 grupos independenpentes dentro dos quais há opções em que variam 4 elementos. Porém, sendo uma dsposição circular, há que se considerar 1 dos elementos dentro de 1 dos dois grupos como sendo fixo. Logo, dentro de um grupo há 3! possibilidades e dentro do outro 4! possibilidades. A partir disto, o "círculo está quebrado" e a solução é por uma permutação simples de grupos complementres, logo para uni-los dá para usar o princípio de contagem, neste caso sendo multiplicativo. Assim, o Total de Possibilidades é igual a 3! x 4! = 6 x 24 = 144

12) PERMUTAÇÃO COM ELEMENTOS ORDENADOS: quando alguns elementos da distribuição precisam estar numa ordem específica

- POSSIBILIDADES = Fatorial de ( # Elementos ) / Fatorial de (# Elementos Ordenados)

P = n! / r!

Exemplo: Quantas permutações do anagrama EXPLODIR podem ser feitas com as vogais estando em ordem alfabética? O total de elementos é o total de letras, logo são 8. O total de elementos a serem ordenados (neste caso em ordem alfabética) é o total de vogais, logo são 3. Assim, as possibilidades são 8! / 3! = 8 x 7 x 6 x 5 x 4 x 3! / 3! = 8 x 7 x 6 x 5 x 4 = 6.720

ARRANJOS & COMBINAÇÕES

13) PERMUTAÇÕES CAÓTICAS (DESARRANJO): situações nas quais os elementos nunca podem retornar para a sua posição original

- POSSIBILIDADES = Fatorial de ( # Elementos ) x Disponibilidade em Desarranjo

P = n! x ( 1/2! - 1/3! + 1/4! - 1/5! + 1/6! - 1/7! + ....) - atenção para a alternância de sinais de "-" e de "+", e a sequência só parará quando o divisor foi igual a "n"

Exemplo: Quantas possibilidades há de formar anagramas juntando ABCD sem que as letras fiquem em suas posições originais? O total de elementos são 4 letras, logo as possibilidades serão: 4! x ( 1/2! - 1/3! + 1/4!) = 24 x ( 1/2 - 1/6 + 1/24 ) = 24 x (0,5 - 0,167 + 0,047) = 24 x 0,375 = 9 .... ou de outra forma: 4!/2! - 4!/3! + 4!/4! = (4 x 3 x 2!)/2! - (4 x 3!)/3! + 1 = 4 x 3 - 4 + 1 = 12 - 4 + 1 = 9

ARRANJOS

- Arranjo dentro de um Conjunto Finito de Elementos (População) é um Subconjunto COM Ordenação Relevante (Amostra), havendo definição de Funções Diferentes

1) ARRANJO SIMPLES

- POSSIBILIDADES = Fatorial de ( # Elementos da População ) / Fatorial de ( # Elementos da População menos Fatorial de # Elementos da Amostra )

A = n! / (n - k)!

Exemplo 1: Numa sala de aula com 8 alunos, 2 serão sorteados para ganhar 2 livros, 1 de português e 1 de matemática. Quantas possibilidades de arranjo há para a distribuição deste sorteio? A população é de 8 alunos e a amostra são os 2 que serão premiados. Logo, as possibilidades de arranjo serão 8! / (8 - 2)! = 8! / 6! = (8 x 7 x 6!) / 6! = 8 x 7 = 56

Exemplo 2: Numa empresa com 20 funcionários, 2 serão escolhidos para formar uma comissão, 1 como gerente e 1 como especialista. Quantos modos diferentes há de se fazer esta escolha? Serão 20! / (20 - 2)! possibilidades. Logo será (20 x 19 x 18!) / 18! = 20 x 19 = 380

COMBINAÇÕES

- Combinações são possibiliddades dentro de um Conjunto Finito de Elementos (População) é um Subconjunto SEM Ordenação Relevante (Amostra)

Diferença entre Arranjo e Combinação: o arranjo é um agrupamento ordenado de elementos de um conjunto, enquanto a combinação é um agrupamento não ordenado de elementos de um conjunto

Exemplo1: Num órgão público, 7 servidores serão escolhidos para um projeto, 1 como coordenador, 1 como subcoordenador e os demais como agentes operacionais. É arranjo ou combinação? É arranjo! Porque há a definição de funções diferentes. Arranjo com 7 elementos e 2 escolhas diferenciadas: 7! / 5! = 7 x 6 = 42.

Exemplo 2: Um bar possui 7 portas. De quantas formas é possível entrar por uma porta e sair por outra porta diferente? É arranjo ou combinação? É arranjo! Porque a ordem das portas importa: 1 Entrada e 1 Saída. Arranjo com 7 elementos possíveis e 2 escolhas diferentes: 7! / 5! = 7 x 6 = 42

2) COMBINAÇÃO SIMPLES: é uma forma de arranjo na qual a ordem dos elementos da amostra não afeta o resultado

- POSSIBILIDADES = Fatorial de ( # Elementos da População ) / ( Fatorial de ( # Elementos da População menos Fatorial de # Elementos da Amostra ) x Fatorial de # Elementos da Amostra )

C = n! / ((n - k)! x k!

Exemplo 1: Numa sala de aula com 8 alunos, 2 serão sorteados para ganhar 2 livros. Quantas possibilidades de arranjo há para a distribuição deste sorteio? A população é de 8 alunos e a amostra são os 2 que serão premiados. Logo, as possibilidades de arranjo serão 8! / ((8 - 2)! x 2!) = 8! / (6! x 2!) = (8 x 7 x 6!) / (6! x 2!) = (8 x 7) / 2 = 4 x 7 = 28

Exemplo 2: Numa empresa com 20 funcionários, 2 serão escolhidos para formar uma comissão. Quantos modos diferentes há de se fazer esta escolha? Serão 20! / ((20 - 2)! x 2!) possibilidades. Logo será (20 x 19 x 18!) / (18! x 2!) = (20 x 19) / 2 = 10 x 19 = 190

3) COMBINAÇÃO COMPLETA (Combinação Com Repetição): A SOLUÇÃO ENVOLVE TRANSFORMAR A COMBINAÇÃO COMPLETA EM UMA COMBINAÇÃO SIMPLES

- POSSIBILIDADES = Fatorial de ( # Elementos da População + # Elementos da Amostra menos 1 ) / Fatorial de # Elementos da Amostra

C = (n + k -1)! / k!

Exemplo 1: Quantas possibilidades há de se escolher 3 potes de sorvete entre 5 marcas diferentes e se podendo repetir a marca escolhida? Equivale a se fazer 3 escolhas num universo de 7 possibilidades, sendo estas 7 possibilidades as 5 marcas diferentes + 3 escolhas menos 1. Assim equivale a uma Combinação Simples de 3 escolhas em 7 possibilidades, cujo resultado é 7! / ((7 -3)! x 3!) = 7! / (4! x 3!) = (7 x 6 x 5 x 4!) / (4! x 3!) = (7 x 6 x 5) / (3 x 2) = 7 x 5 = 35

Exemplo 2: Numa loja com 8 sabores de sorvete, de quantas maneiras diferentes se pode escolher uma casquinha de 2 bolas, não necessariamente de sabores diferentes e sem importar a ordem com que sejam colocadas na casquinha? A possibilidade é uma combinação de 2 escolhas num universo de 8 + 2 - 1 = 9 possibilidades. Logo, será 9! / 7! x 2! = (9 x 8) / 2 = 9 x 4 = 36

CASOS ESPECIAIS

4) SOLUÇÕES QUE UMA EQUAÇÃO POSSUI (Combinação de Soluções Inteiras de Equação): é um Caso Especial de Combinação Completa

- POSSIBILIDADES = Fatorial de ( Resultado da Equação + # Elementos de Adição menos 1 ) / Fatorial de ( # Elementos de Adição menos 1 )

C = (R + e -1)! / (e - 1)!

Exemplo 1: Quantas soluções possíveis há para "x + y + z = 10"? O resultado é 10 e há 3 elementos de adição na equação. Logo, é uma C (10 + 3 - 1; 3 - 1) = C (12; 2) = 12! / (10! - 2!) = (12 x 11) / 2 = 6 x 11 = 66 soluções possíveis

Exemplo 2: Quantas soluções possíveis há para a distribuição de 7 kg de feijão entre 4 famílias? O resultado é o total distribuído, que é 7, e os elementos de adição na equação são a quatidade de famílias a receber a distribuição, que é 7. Logo, é uma C (7 + 4 - 1; 4 - 1) = C (10; 3) = 10! / (7! x 3!) = (10 x 9 x 8) / (3 x 2) = 5 x 3 x 8 = 120 soluções possíveis

Exemplo 3: Quantas soluções possíveis há para a distribuição de 9 balas idênticas entre 3 pessoas, desde que cada pessoa receba pelo menos 2? Logo, até a distribuição de 6 balas, sendo 2 para cada uma, não há combinação possível. As combinações de de distribuição só vão existir para as 3 últimas balas a serem distribuídas para as 3 pessoas Assim, o resultado a ser distribuído é 3, e os elementos de adição na equação são a quatidade de pessoas, que é 3. Logo, é uma C (3 + 3 - 1; 3 - 1) = C (5; 2) = 5! / (5! - 3!) x 3! = 5! / (3! x 2!) = (5 x 4) / 2 = 5 x 2 = 10 soluções possíveis

5) PARTIÇÃO NÃO ORDENADA

- POSSIBILIDADES = ( Multiplicação das Combinações envolvendo # Elementos do Universo e a # Elementos por Grupo ) / Fatorial de # Grupos

C = ( C (n; k) x C (n - k; k) x (C (n - 2k; k) x .... ) / g!

Exemplo: Quantas possibilidades há para se dividir 6 alunos em 3 duplas para a realização de um trabalho? A primeira combinação simples possível é a escolha de 2 alunos entre os 6. A segunda combinação simples possível é a escolha de outros 2 alunos entre os 4 restantes. A última combinação é composta pelos 2 restantes. São 3 grupos. Assim, as possibilidades são iguais a (C (6; 2) x C (4; 2) x C (2; 2)) / 3! = ((6! / (4! x 2!)) x (4! / (2! x 2!)) x (2! / (0! x 2!))) / 3! = ((6 x 5)/2 x (4 x 3)/2 x (2/2)) / (3 x 2) = ((3 x 5) x (2 x 3) x 1) / 3 x 2 = 3 x 5 = 15

6) PARTIÇÃO ORDENADA: é uma distribuição em quantidades diferentes por grupos

- POSSIBILIDADES = ( Multiplicação das Combinações envolvendo # Elementos do Universo e a # Elementos por Grupo )

C = ( C (n; k) x C (n - k; k) x (C (n - 2k; k) x .... )

Exemplo: Num grupo de 10 profissionais, há que se escolher 1 gerente e 2 coordenadores, com os 7 sendo especialistas. Quantas formas há para esta partição? A primeira combinação simples possível é a escolha de 1 gerente entre os 10 profissionais. A segunda combinação simples possível é a escolha de 2 coordenadores entre os 9 profissionais restantes. De resto, serão 7 especialistas entre os 7 profissionais restantes. Assim, as possibilidades são: (C (10; 1) x C (9; 2) x C (7; 7)) = (10! / (9! x 1!)) x (9! / (7! x 2!)) x (7!/7!) = 10 x ((9 x 8) / 2) x 1 = 10 x 9 x 4 = 360

* C (n; 0) + C (n; 1) + C (n; 2) + C (n; 3) + ... C (n; n) = 2^n