Análise combinatória

Você precisa saber de quantas maneiras diferentes é possível escolher cinco cartas de um baralho de 32? Esse é exatamente o tipo de problema que a análise combinatória resolve. Existem dois princípios básicos de contagem — o aditivo e o multiplicativo. Todos os outros métodos são apenas extensões desses princípios.

Princípio aditivo

O princípio aditivo é muito simples: ele nos diz que, se temos conjuntos A, B sem nenhum elemento em comum, então o número de maneiras de escolher um elemento da união A ∪ B é igual a |A| + |B|, isto é, à soma dos números de elementos dos conjuntos.

Vamos começar com um exemplo fácil. Temos 6 bolinhas vermelhas e 8 bolinhas azuis, e colocamos todas em uma urna. Quantas possibilidades temos ao sortear uma bolinha? No início tínhamos o conjunto das bolinhas vermelhas, que chamamos de A, e o conjunto das bolinhas azuis, que chamamos de B. Esses conjuntos são disjuntos, ou seja, não têm nenhuma bolinha em comum. Queremos sortear uma bolinha, então temos ao todo |A| + |B| = 6 + 8 = 14 possibilidades. É só isso.

Princípio multiplicativo

Temos novamente dois conjuntos, M e H. O conjunto M contém três mulheres e o conjunto H, quatro homens. Agora perguntamos: quantos pares diferentes homem—mulher podemos formar com esses conjuntos? O que queremos é sempre pegar uma mulher e associar a ela um homem. Para contar todos os pares, fazemos assim: pegamos uma mulher, a Júlia, e vamos associando a ela todos os homens. Obtemos 4 pares diferentes, porque podemos associar a ela 4 homens diferentes. Fazemos o mesmo com as duas mulheres restantes, e cada uma delas também forma 4 pares. E pronto, temos ao todo 4 + 4 + 4 = 12 pares.

O que fizemos na verdade? Multiplicamos os números de elementos dos dois conjuntos. Tínhamos 3 mulheres e 4 homens, então o número total de pares é 3 · 4 = 12. Daí o nome princípio multiplicativo. Se temos dois conjuntos com os quais formamos pares, basta multiplicar o número de elementos de um conjunto pelo número de elementos do outro.

Você pode conferir que isso realmente vale. A seguir estão todos os pares que podemos formar com 3 mulheres e 4 homens. Cada linha representa as possibilidades para uma das mulheres e cada coluna, as possibilidades para um dos homens. Temos, portanto, três linhas e quatro colunas, ou seja, linhas · colunas possibilidades no total.

$$\begin{array}{rcl}& & (M_1,H_1),(M_1,H_2),(M_1,H_3),(M_1,H_4),\\ & & (M_2,H_1),(M_2,H_2),(M_2,H_3),(M_2,H_4),\\ & & (M_3,H_1),(M_3,H_2),(M_3,H_3),(M_3,H_4)\end{array}$$

Exercícios resolvidos

1. Quantos números de dois algarismos existem? Como é um número desses? Na primeira posição aparece um dos algarismos 1, …, 9, enquanto na segunda posição pode aparecer também o zero: 0, …, 9. No primeiro conjunto temos, então, 9 algarismos e no segundo, 10. Usamos o princípio multiplicativo e obtemos o resultado final: 9 · 10 = 90.

• Quantos números de três algarismos existem em que nenhum algarismo aparece duas vezes? Na primeira posição podem ficar novamente nove algarismos, pois o número não pode começar por zero. Na segunda posição podem ficar todos os algarismos, inclusive o zero, mas não o algarismo que aparece na primeira posição; por isso, dos dez algarismos possíveis, subtraímos um (por exemplo, se o nosso número de três algarismos começa por quatro, é claro que o quatro não pode aparecer de novo na segunda posição, pois estaria duas vezes no número todo). Na terceira posição podem ficar novamente todos os algarismos, exceto os que estão na primeira ou na segunda posição. O motivo é o mesmo. Se na primeira posição está o algarismo 4 e na segunda o 7, então na terceira posição podemos colocar um algarismo de {0, …, 9} ∖ {4, 7}. Do total de dez algarismos precisamos subtrair dois. Agora basta multiplicar: 9 · 9 · 8 = 648. Existem, portanto, 648 números assim.
• Lançamos um dado comum duas vezes seguidas. Quantos resultados diferentes podemos obter? No primeiro lançamento podem sair 6 resultados diferentes. No segundo também, então o número total de possibilidades é 6 · 6 = 36.
• Lançamos um dado duas vezes seguidas. Quantos resultados diferentes podemos obter se no primeiro lançamento saiu um número par? No primeiro lançamento saiu um número par, isto é, um dos números 2, 4, 6, o que dá 3 possibilidades. No segundo lançamento pode sair qualquer número, então temos ao todo 3 · 6 = 18 possibilidades.