Análise combinatória

Do princípio de contagem às fórmulas

As fórmulas combinatórias condensam produtos obtidos pelo princípio fundamental da contagem. Elas não substituem a interpretação: apenas tornam recorrências mais rápidas de calcular.

Se há n elementos distintos, podemos perguntar:

• todos serão ordenados? permutação;
• apenas p serão escolhidos e a ordem importa? arranjo;
• apenas p serão escolhidos e a ordem não importa? combinação.

Fatorial

Para inteiro n≥1, o fatorial é o produto dos inteiros positivos de n até 1:

$$n!=n\cdot(n-1)\cdot(n-2)\cdots2\cdot1.$$

Por definição, 0!=1. Exemplos:

$$5!=5\cdot4\cdot3\cdot2\cdot1=120$$

e

$$\frac{8!}{6!}=\frac{8\cdot7\cdot6!}{6!}=56.$$

Não expanda fatoriais inteiros sem necessidade. Cancelar fatores comuns reduz trabalho e risco de erro.

Permutação simples

Uma permutação simples ordena todos os n elementos distintos:

$$P_n=n!.$$

Cinco pessoas podem ocupar uma fila de:

$$P_5=5!=120$$

maneiras. Cada posição preenchida reduz em uma unidade o número de escolhas seguintes.

Permutação com repetição

Quando alguns elementos são indistinguíveis, n! conta várias vezes o mesmo resultado. Se há n elementos, com repetições a,b,c,…, então:

$$P_n^{a,b,c,\ldots}=\frac{n!}{a!b!c!\cdots}.$$

Na palavra BANANA, há seis letras, com três A, dois N e um B:

$$\frac{6!}{3!2!}=\frac{720}{12}=60.$$

Dividimos por 3! porque permutar os três A entre si não cria palavra visualmente nova; o mesmo vale para os dois N.

Permutação circular

Em uma fila, deslocar todos os elementos cria outra ordem. Em uma roda sem posição marcada, rotações representam a mesma disposição. Fixamos um elemento como referência e ordenamos os demais:

$$P_c(n)=(n-1)!.$$

Seis pessoas ao redor de uma mesa redonda podem sentar-se de:

$$(6-1)!=5!=120$$

formas, quando apenas rotações são consideradas equivalentes. Reflexões não devem ser divididas automaticamente: uma ordem horária e sua inversa continuam diferentes, salvo se o enunciado declarar outra equivalência.

Arranjo simples

No arranjo, escolhemos p entre n elementos distintos e a ordem importa:

$$A_{n,p}=\frac{n!}{(n-p)!}.$$

Em um pódio com primeiro, segundo e terceiro lugares entre 10 participantes:

$$A_{10,3}=\frac{10!}{7!}=10\cdot9\cdot8=720.$$

Escolher Ana, Beto e Caio nessa ordem difere de escolher Beto, Ana e Caio, pois os cargos ou posições mudam.

Combinação simples

Na combinação, escolhemos p entre n elementos distintos e a ordem não importa:

$$C_{n,p}=\binom{n}{p}=\frac{n!}{p!(n-p)!}.$$

Para formar uma comissão de três pessoas entre dez:

$$C_{10,3}=\frac{10!}{3!7!}=\frac{10\cdot9\cdot8}{3\cdot2\cdot1}=120.$$

O fator p! elimina as ordens internas do mesmo grupo.

Para três elementos, existem 3!=6 ordens. Um arranjo conta cada uma; uma combinação reúne as seis como um único grupo.

Arranjo ou combinação?

Faça o teste da troca: inverta duas pessoas ou objetos escolhidos.

• Se o resultado muda, a ordem importa: arranjo.
• Se continua sendo o mesmo resultado, a ordem não importa: combinação.

Situação	Ordem importa?	Modelo
presidente, vice e secretário	sim	arranjo
comissão com três membros iguais em função	não	combinação
três primeiros colocados	sim	arranjo
três livros escolhidos para levar	não	combinação
sequência de questões selecionadas e ordenadas	sim	arranjo

Não decida pela palavra “escolher”. É possível escolher pessoas para cargos diferentes, caso em que a ordem funcional importa.

Relação entre arranjo e combinação

Escolher um grupo de p elementos e depois ordená-lo gera:

$$A_{n,p}=C_{n,p}\cdot p!.$$

Logo:

$$C_{n,p}=\frac{A_{n,p}}{p!}.$$

Essa relação explica a divisão da combinação por p!: todas as ordens do mesmo grupo foram contadas no arranjo.

Restrições por casos

Uma comissão de quatro pessoas será formada entre 7 mulheres e 5 homens, com pelo menos duas mulheres. Os casos possíveis são disjuntos:

1. duas mulheres e dois homens;
2. três mulheres e um homem;
3. quatro mulheres.

Portanto:

$$C_{7,2}C_{5,2}+C_{7,3}C_{5,1}+C_{7,4}.$$

Calculando:

$$21\cdot10+35\cdot5+35=420.$$

Multiplicamos as escolhas dentro de cada caso e somamos os casos alternativos. Esse padrão reutiliza simultaneamente os princípios multiplicativo e aditivo.

Restrições de posição

Em permutações com pessoas juntas, uma estratégia recorrente é tratar o grupo como bloco. Se sete pessoas formarão uma fila e Ana e Beto precisam ficar juntos:

• considere AB como um bloco: temos seis objetos para ordenar, totalizando 6!;
• dentro do bloco, Ana e Beto podem trocar de ordem: 2!.

Logo:

$$6!\cdot2!=1.440.$$

Se a condição for “não podem ficar juntos”, conte todas as filas e retire as que os mantêm unidos:

$$7!-6!\cdot2!=5.040-1.440=3.600.$$

Simetria das combinações

Escolher p elementos equivale a decidir quais n-p ficarão de fora:

$$C_{n,p}=C_{n,n-p}.$$

Assim, C(10,8)=C(10,2)=45. Use a menor quantidade no cálculo para simplificar os produtos.

Um roteiro de decisão

1. Defina um resultado completo e quando dois resultados são diferentes.
2. Verifique se todos os elementos serão usados.
3. Faça o teste da troca para decidir se a ordem importa.
4. Identifique elementos repetidos ou posições circulares.
5. Traduza restrições antes de escolher a fórmula.
6. Separe casos disjuntos ou use complemento quando necessário.
7. Simplifique os fatoriais antes de multiplicar.
8. Confira o resultado em um caso pequeno ou pelo princípio de contagem.

Como aparece em provas

São comuns problemas com anagramas, filas, mesas redondas, pódios, cargos, comissões, equipes, escolhas de questões, senhas sem repetição e agrupamentos sujeitos a condições. A principal dificuldade costuma estar em identificar o modelo, não em efetuar o fatorial.

Também podem aparecer fórmulas diferentes para a mesma ideia. A_{n,p}, P(n,p) e {}_nP_p podem indicar ordenações parciais; C_{n,p} e \binom{n}{p} indicam combinações. Leia a definição oferecida pela questão.

Erros frequentes

• aplicar combinação quando cargos ou posições distinguem os escolhidos;
• aplicar arranjo a uma comissão sem funções;
• usar n! quando apenas parte dos elementos será escolhida;
• esquecer de dividir pelas repetições em anagramas;
• dividir por 2 em toda disposição circular;
• confundir repetição de elementos com repetição de uma escolha permitida;
• somar casos que se sobrepõem;
• esquecer casos intermediários em “pelo menos”;
• expandir fatoriais enormes antes de cancelar;
• usar fórmula sem definir o que é um resultado distinto.

Síntese para revisão

Modelo	Elementos usados	Ordem importa?	Fórmula
permutação simples	todos	sim	n!
permutação com repetição	todos	sim, descontando iguais	n!/(a!b!…)
permutação circular	todos em círculo	sim, rotações equivalentes	(n-1)!
arranjo simples	parte	sim	n!/(n-p)!
combinação simples	parte	não	n!/[p!(n-p)!]

Próximos passos

• Retome o Princípio fundamental da contagem para modelar etapas e restrições.
• Use Expressões numéricas para simplificar produtos e quocientes.
• Continue em Probabilidade para aplicar contagens à construção de espaços amostrais.

Referências

• Base Nacional Comum Curricular — Ministério da Educação.
• OpenStax Contemporary Mathematics — Permutations.
• OpenStax Contemporary Mathematics — Combinations.
• OpenStax Algebra and Trigonometry — Counting Principles.