Análise combinatória

Análise combinatória é o estudo de maneiras de contar possibilidades sem precisar escrever cada uma delas. A tarefa começa antes das fórmulas: precisamos decidir o que caracteriza um resultado diferente. Escolher duas pessoas para uma comissão não é o mesmo que designar uma presidência e uma vice-presidência. As pessoas podem ser as mesmas, mas os papéis tornam a ordem relevante.

Conte por etapas bem definidas

Se há três camisetas e duas calças, e qualquer camiseta pode ser combinada com qualquer calça, há $3\cdot2=6$ conjuntos. Cada escolha da primeira etapa admite duas continuações. Esse é o princípio multiplicativo: quando cada etapa tem um número fixo de possibilidades para cada caminho anterior, multiplicamos esses números.

Não é necessário que as escolhas sejam independentes no sentido probabilístico. Para formar uma senha de três algarismos distintos, por exemplo, a segunda escolha depende da primeira, mas sempre restam nove opções. Admitindo zero na primeira posição, o total é $10\cdot9\cdot8=720$. Se cada ramo permitir um número diferente de continuações, separe os casos ou use uma árvore e some suas folhas.

O princípio aditivo vale para alternativas que não se sobrepõem. Se um trajeto pode ser feito por quatro linhas diretas de ônibus ou por duas linhas diretas de trem, e cada linha representa uma opção distinta, há seis escolhas. Somar casos que compartilham resultados causa dupla contagem.

A ordem decide o modelo

Entre oito estudantes, escolher presidente e vice dá $8\cdot7=56$ resultados: Ana presidente e Bruno vice difere de Bruno presidente e Ana vice. Isso é um arranjo de dois elementos distintos, com funções diferentes.

Se os mesmos oito estudantes concorrem a duas vagas equivalentes de representantes, cada dupla foi contada duas vezes nessa conta. Logo, há $56/2=28$ comissões. A divisão não é um truque arbitrário: elimina as duas ordens que descrevem o mesmo conjunto. Para grupos de três, cada conjunto aparece $3!=6$ vezes entre as seleções ordenadas.

Fatorial, arranjo e combinação

Para inteiro positivo $n$, o fatorial é $n!=n(n-1)\cdots1$, e convencionamos $0!=1$. Organizar todos os $n$ elementos distintos em uma fila dá $n!$ permutações. Selecionar e ordenar $k$ entre eles, sem repetição, dá $A_{n,k}=n!/(n-k)!$.

Quando a ordem interna não importa, dividimos por $k!$: $\binom nk=n!/[k!(n-k)!]$, com $0\le k\le n$. Escolher quatro pessoas entre sete dá $\binom74=35$. Também poderíamos escolher as três pessoas que ficam de fora: $\binom73=35$. Essa simetria oferece uma conferência e pode reduzir a conta.

Antes de expandir fatoriais grandes, cancele fatores comuns. Em $\binom{10}3$, basta calcular $10\cdot9\cdot8/(3\cdot2\cdot1)=120$. Usar todos os fatoriais integralmente aumenta o trabalho e as oportunidades de erro.

Repetições mudam o que é distinguível

Uma senha de quatro posições com dez algarismos disponíveis em cada posição admite $10^4$ resultados se repetições forem permitidas e zero puder iniciar a senha. Um número natural de quatro algarismos, porém, não começa por zero: nesse caso são $9\cdot10^3$ possibilidades.

Para reorganizar as letras de ARARA, as cinco posições não recebem cinco objetos distinguíveis: há três letras A iguais e duas R iguais. O total é $5!/(3!2!)=10$ anagramas distintos. Trocar dois A entre si não altera a palavra. Essa divisão exige que as repetições sejam realmente indistinguíveis para o resultado contado.

Resolva uma restrição com dois caminhos

Uma comissão de três pessoas será formada entre cinco estudantes da manhã e quatro da tarde. Exige-se pelo menos uma pessoa da tarde. Todos os grupos são permitidos exceto os três escolhidos apenas entre os cinco da manhã. Pelo complementar, o total é $\binom93-\binom53=84-10=74$.

Para conferir, separe por quantidade de pessoas da tarde: uma dá $\binom41\binom52=40$; duas dão $\binom42\binom51=30$; três dão $\binom43=4$. Somando, obtemos novamente 74. Os casos são disjuntos e cobrem exatamente a exigência. Não multiplique o total de comissões por três: as vagas não têm nomes e a ordem não cria grupos novos.

Na probabilidade, essas contagens podem compor numerador e denominador. Ambos precisam descrever resultados com a mesma convenção de ordem, além de respeitar a equiprobabilidade do sorteio.