O que é Análise Combinatória?

A análise combinatória estuda quantas configurações finitas existem. Quase toda contagem começa por duas perguntas: a ordem importa? os objetos se repetem?

O que a combinatória conta

Cada problema de contagem pede o tamanho de um conjunto finito de configurações.

Com três peças distintas, cada peça entra ou não num subconjunto. São $2^3=8$ subconjuntos: o vazio, os três de um elemento, os três pares e o conjunto cheio.

As mesmas três peças em fila dão $3\times 2\times 1=6$ ordens. O produto $n\times(n-1)\times\cdots\times 1$ se escreve $n!$; aqui $3!=6$.

São conjuntos de configurações diferentes: num listamos subconjuntos, no outro listamos filas.

Por exemplo, três frutas distintas $\{A,B,C\}$. Ordens possíveis: $ABC$, $ACB$, $BAC$, $BCA$, $CAB$, $CBA$, ou seja $3!=6$. Subconjuntos de tamanho $2$: $\{A,B\}$, $\{A,C\}$, $\{B,C\}$, ou seja $3$ pares.

Ordem importa ou não?

Combinação: seleção de $r$ itens entre $n$, sem ordem. O trio (maçã, banana, cereja) é o mesmo que (cereja, maçã, banana). Palavras típicas da pergunta: comitê, equipe, jogo de loteria, subconjunto.

Permutação: arranjo de $r$ itens entre $n$, com ordem. (maçã, banana, cereja) e (banana, maçã, cereja) são distintos. Palavras típicas: fila, senha, ranking, rota, sequência.

O termo arranjo costuma ser sinônimo de permutação (ordem conta).

Cada seleção de $r$ peças distintas corresponde a $r!$ ordens dessas mesmas peças. Contar sequências e depois dividir por $r!$ é contar subconjuntos; contar subconjuntos e multiplicar por $r!$ é contar sequências:

Com repetição permitida e ordem relevante, cada uma das $r$ posições tem $n$ opções. O total é $n^r$: a permutação com repetição em que a ordem conta e as peças podem se repetir.

Senha de $3$ bits: cada posição escolhe $0$ ou $1$, logo $2^3=8$ sequências.

Exemplo: mesmos $3$ livros entre $5$

Cinco livros distintos; queremos $3$.

Escolher e ordenar (estante, ordem de leitura): primeira prateleira $5$ opções, segunda $4$, terceira $3$:

Escolher sem ordem (levar três na mochila): cada grupo de $3$ gera $3! = 6$ ordens distintas na estante, logo

grupos. Os $10$ são os subconjuntos; os $60$ são as sequências. Se a pergunta descreve um grupo sem posição, o objeto é o subconjunto.

Se os livros pudessem repetir (três escolhas com reposição e ordem), o produto seria $5^3=125$ — o mesmo $n^r$ da senha.

Exemplo: classificar o enunciado

Enunciado. Um motoqueiro tem $n=5$ entregas em pontos distintos, em qualquer ordem. Distâncias assimétricas: o trecho $A\to B$ e o trecho $B\to A$ podem ter tempos diferentes. Quantas rotas ele avalia se ignora o deslocamento até o primeiro ponto?