Analise Combinatoria

Análise Combinatória

A Análise Combinatória é a área do conhecimento que lida com os problemas relacionados à contagem. Os problemas que envolvem são comuns no dia-a-dia, tanto na vida privada, profissional ou acadêmica. O pilar da Análise Combinatória é o conhecido princípio multiplicativo ou princípio fundamental da contagem.

Princípio Multiplicativo ou Princípio Fundamental da Contagem

O princípio multiplicativo tem o seguinte enunciado:

Se um evento A pode ocorrer de maneiras diferentes e se, para cada uma das m maneiras possíveis de ocorrências de A, um segundo evento B pode ocorrer de maneiras diferentes, então o número de maneiras de ocorrer o evento A seguido do evento B é .

Apesar do aspecto complicado do enunciado seu entendimento é simples. Para a compreensão, vamos utilizar exemplos.

Exemplo1: O professor Alexandre aplicará uma prova com 3 formatos diferentes: só questões objetivas (O), só questões discursivas (D) e questões mistas (M). A universidade disponibilizou folhas de papel de duas cores distintas (branca B e verde V). Qual é a quantidade de provas diferentes (formato de prova e cor da folha) poderá ser impressa?

Para responder essa pergunta, note que teremos vários casos: questões objetivas com folha verde, questões mistas com folha branca, questões discursivas com folha verde, etc. Para fazer a contagem de todas as possibilidades podemos fazer todas as combinações como nos casos acima. No entanto, além de enfadonho, é muito fácil se perder, contando a mais ou esquecendo alguma combinação. Uma maneira mais clara fazer essa contagem é montar uma árvore de possibilidade.

Para construir uma árvore de possibilidade devemos colocar cada um das possibilidades em uma coluna (no caso acima, os tipos de prova); de cada elemento da coluna anterior saem linhas para cada possibilidade (a cor da folha). Assim, após construir a árvore de possibilidades, podemos contar quantas são as possibilidades. No nosso caso, temos 6 possibilidades, que são, normalmente, escritas como pares ordenados (ou ternas, se forem 3, quádruplas, se forem 4, etc):

Se ao invés de duas cores de papeis tivéssemos três cores, quantas seriam as possibilidades? Vejamos a árvore de possibilidades:

Temos agora nove possibilidades. Representando em pares ordenados, temos:

E se tivéssemos 22 cores diferentes? Quantas seriam as possibilidades? Para o caso de 22 cores teríamos uma árvore de possibilidades muito grande!

Para contornarmos o problema do tamanho da árvore, devemos voltar à definição do princípio multiplicativo e aos exemplos anteriores. No primeiro exemplo, o primeiro evento (formato de prova) tem 3 maneiras e para cada maneira temos 2 cores distintas de folha de papel, então há 3*2 = 6 possibilidades. No segundo exemplo, o primeiro evento tem 3 maneiras e para cada maneira temos 3 cores resultando num total de 9 possibilidades. Será que é simplesmente o produto (multiplicação) entre eles? A resposta é SIM!.

Para o terceiro exemplo, onde tínhamos 3 formatos de prova e 22 cores teremos 3*22=66 possibilidades. Essa é a aplicação do princípio multiplicativo.

Suponha que temos 4 camisetas e 3 bermudas diferentes. De quantas maneiras podemos nos vestir sem repetir o par camiseta-bermuda?

Como podemos usar qualquer camiseta com qualquer bermuda, então temos 4*3 = 12 pares diferentes.

Outro problema: Quantos números de 3 algarismos podemos formar utilizando os algarismos 2, 3, 4, 5, 6?

Para resolver esse tipo de problema, utilizamos o princípio multiplicativo também. Escrevamos as 3 posições de cada dígito do número com um sublinhado:

_ _ _

Para cada posição devemos pensar: “quantas possibilidades eu tenho (números diferentes) para colocar na primeira posição?”. Neste caso, temos 5 possibilidades (os algarismos 2, 3, 4, 5 e 6). Então, na primeira posição, colocamos essa quantidade:

5 _ _

Continuando, perguntemos: “Quantas possibilidades tenho para a segunda posição?”. Agora, restam somente 4 números, pois um deles foi utilizado para a primeira posição. Assim temos:

5 4 _

E para a terceira posição, quantas são as possibilidades? Como já utilizamos dois números, ainda restam três. Assim:

5 4 3

O princípio multiplicativo diz que devemos MULTIPLICAR essas possibilidades:

5 *4 *3 = 60

(seria uma árvore com primeira coluna com 5 números, de cada número sairiam outros 4 números e desses sairiam outros 3...)

Portanto, podemos ter 60 números diferentes de 3 algarismos utilizando 2, 3, 4, 5 e 6.

E se a pergunta fosse um pouco diferente: “Quantos números ímpares de 3 algarismos podemos formar utilizando os algarismos 2, 3, 4, 5 e 6”?

Novamente temos 3 posições para serem preenchidas com uma quantidade de números:

¬_ _ _

Mas o exercício pede “número ímpar”. O que é um número ímpar? É um número inteiro terminado em 1, 3, 5, 7 ou 9. Então, nesse caso, o número deverá terminar com 3 ou 5 ( a lista de opções dada no exercício não inclui o 1, o 7 e o 9). Assim, para a última posição, temos apenas duas possibilidades:

_ _ 2

A primeira e a segunda posição não têm restrição. Assim, para a primeira posição, quantas são as possibilidades? Como temos 5 opções (2, 3, 4, 5 e 6) mas uma delas já foi utilizada (o 3 ou o 5), então restam quatro possibilidades para a primeira posição:

4 _ 2

E para a segunda posição? Já foram utilizados dois algarismos, restam três. Assim:

4