Análise combinatória Princípio fundamental da contagem
Conceito Imagine a seguinte situação: Você vai a uma loja de sorvetes e lá existem 3 sabores (morango, uva, limão). Também há duas opções para se servir (casquinha ou potinho). E duas coberturas (chocolate e morango). Quantas são as possibilidades de escolha que você tem sendo que deve escolher apenas um sabor, uma opção para se servir e uma calda?
Ok ... Foi tranquilo de fazer com poucas opções, através de um desenho. Mas e se aumentarmos o número de opções? Só para o sabor uva, teríamos:
Só para o sabor uva, teríamos:
Conforme o número de opções aumenta, também aumenta a complexidade do desenho (conhecido como diagrama da árvore). Mas como poderíamos solucionar esse tipo de problemas sem a necessidade de ficar desenhando? Utilizando a análise combinatória. Análise combinatória visa desenvolver métodos que permitam contar o número de elementos de um conjunto, sendo estes elementos agrupamentos formados sob certas condições.
sabor local calda 3 2 2 Para o primeiro problema problema, poderíamos fazer:
sabor local calda 7 2 3 Para o segundo problema, poderíamos fazer: doces 4
Princípio fundamental da contagem Utilizamos o princípio fundamental da contagem para resolver ambos os casos. O Princípio Fundamental da Contagem (Princípio Multiplicativo) , é um método para determinar o número total de maneiras que um evento complexo pode ocorrer quando esse evento é composto por várias etapas independentes. A ideia principal é multiplicar o número de possibilidades de cada etapa para encontrar o número total de combinações possíveis.
Exemplo 01: Uma moeda é lançada 3 vezes. Qual o número de sequências possíveis de cara e coroa? 1º lançamento 2º lançamento 3º lançamento
Faces da moeda
Exemplo 02: Quatro atletas participam de uma prova. Quantos resultados existem para o 1º, 2º e 3º lugares? 1 2 3
Exemplo 02: Quatro atletas participam de uma prova. Quantos resultados existem para o 1º, 2º e 3º lugares? 1 2 3 4 possibilidades para o primeiro lugar
Exemplo 02: Quatro atletas participam de uma prova. Quantos resultados existem para o 1º, 2º e 3º lugares? 1 2 3 4 possibilidades para o primeiro lugar 3 possibilidades para o segundo lugar
Exemplo 02: Quatro atletas participam de uma prova. Quantos resultados existem para o 1º, 2º e 3º lugares? 1 2 3 3 possibilidades para o segundo lugar 2 possibilidades para o terceiro lugar
Exemplo 02: Quatro atletas participam de uma prova. Quantos resultados existem para o 1º, 2º e 3º lugares? 1 2 3 2 possibilidades para o terceiro lugar
Exemplo 02: Quatro atletas participam de uma prova. Quantos resultados existem para o 1º, 2º e 3º lugares? 1 2 3
Exemplo 03: De quantas formas podemos responder a 12 perguntas de um questionário, cujas respostas para cada pergunta são: sim ou não? Pergunta 1 Sim Não Pergunta 2 Sim Não (...) Para cada pergunta, duas possibilidades de resposta (sim ou não)
Observação: Algumas vezes, o conjunto cujos elementos queremos contar consta de sequências de tamanhos diferentes (isto é, o número de elementos das sequências consideradas é diferente), o que impede o uso do princípio fundamental da contagem. Entretanto, usando o diagrama de árvore, podemos saber facilmente quantas são as sequências.
Exemplo 04: Uma pessoa lança uma moeda sucessivamente até que ocorram duas caras consecutivas, ou quatro lançamentos sejam feitos, o que primeiro ocorrer. Quais as sequências de resultados possíveis?