Análise Combinatória - Ciência da Computação

Análise combinatória é o ramo da matemática que estuda métodos de contagem, enumeração e organização de objetos discretos. Seu foco principal é determinar quantas configurações distintas podem ser formadas sob determinadas regras, sem que seja necessário listar explicitamente todos os casos.

Esse campo aparece sempre que precisamos contar possibilidades, distribuir objetos, escolher subconjuntos, ordenar elementos ou estudar estruturas discretas. Em vez de depender apenas de tentativa e erro, a análise combinatória fornece princípios gerais que transformam problemas aparentemente complicados em fórmulas ou procedimentos sistemáticos.

A área tem papel central em probabilidade, estatística, teoria dos grafos, algoritmos, criptografia, teoria da computação e otimização. Em ciência da computação, ela é especialmente importante porque muitos problemas envolvem busca em espaços finitos, análise de complexidade, geração de arranjos, árvores de decisão e contagem de casos possíveis.

Ao longo deste capítulo, os tópicos serão organizados a partir dos princípios fundamentais de contagem, passando por permutações, combinações, funções geradoras, inclusão-exclusão e técnicas de enumeração. A intenção é construir uma base útil tanto para raciocínio matemático quanto para aplicações algorítmicas.

O princípio fundamental da contagem, também chamado princípio multiplicativo, afirma que se um processo é composto por $n$ etapas sucessivas e independentes, e se a etapa $i$ pode ser realizada de $m_i$ maneiras, então o total de resultados possíveis é dado por

$$ m_1\cdot m_2\cdot...\cdot m_n=\prod_i^n m_i $$

A ideia central é simples: cada escolha feita em uma etapa pode ser combinada com cada escolha possível das etapas seguintes. Assim, a contagem total cresce pelo produto, e não pela soma.

Esse princípio é a base de grande parte da análise combinatória. Sempre que um problema puder ser decomposto em decisões sucessivas, com número conhecido de opções em cada decisão, podemos transformar a contagem total em uma multiplicação.

A palavra independentes deve ser entendida com cuidado. Ela não significa necessariamente independência probabilística, mas sim que, em cada etapa, sabemos contar quantas opções permanecem válidas depois das escolhas anteriores. Às vezes esse número permanece constante; em outras, diminui ou muda conforme o histórico do processo.

Um modo prático de modelar esse tipo de problema é fazer quatro perguntas:

quais são as etapas do processo;
quantas opções existem em cada etapa;
se escolhas anteriores alteram as opções seguintes;
se estamos somando casos distintos ou multiplicando decisões sucessivas.

Exemplo: para distribuir 3 medalhas, ouro, prata e bronze, entre 4 competidores, temos:

Ouro: 4 possibilidades
Prata: 4-1=3 possibilidades
Bronze: 4-2=3-1=2 possibilidades

Isso acontece porque quem recebe o ouro não pode receber a prata, e quem já recebeu ouro ou prata também não pode receber o bronze. Portanto, as escolhas vão reduzindo o conjunto disponível de candidatos. O total é

$$ D=4\cdot3\cdot2=24\; \text{possibilidades} $$

Esse exemplo é um caso típico em que as escolhas anteriores afetam as posteriores. Por isso, embora o problema seja multiplicativo, os fatores não são todos iguais.

Quando as quantidades disponíveis seguem uma sequência natural decrescente, aparece naturalmente o conceito de fatorial:

$$ m!=m(m-1)(m-2)...1 $$

O fatorial surge em contagens nas quais escolhemos e ordenamos todos os elementos de um conjunto ou uma parte deles, sem repetição. Ele é um dos blocos mais importantes das fórmulas combinatórias.

Por exemplo, se queremos ordenar 5 objetos distintos em fila, temos 5 escolhas para a primeira posição, 4 para a segunda, 3 para a terceira, 2 para a quarta e 1 para a última. Logo, o total é

$$ 5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120 $$

Outro exemplo simples: quantas senhas de 4 dígitos podem ser formadas se cada posição pode conter qualquer algarismo de 0 a 9 e a repetição é permitida? Como cada uma das 4 posições tem 10 possibilidades, temos

$$ 10\cdot 10\cdot 10\cdot 10=10^4=10000 $$

Se, por outro lado, exigirmos que os dígitos sejam distintos, a contagem muda para

$$ 10\cdot 9\cdot 8\cdot 7=5040 $$

Esse contraste mostra uma das ideias mais importantes da combinatória: pequenas mudanças nas restrições alteram significativamente a contagem final.

Podemos usar o mesmo raciocínio em um problema misto. Suponha que um código tenha 1 letra seguida de 3 dígitos. Se a letra pode ser qualquer uma das 26 do alfabeto e cada dígito pode ser qualquer valor de 0 a 9, então o total de códigos é

$$ 26\cdot 10\cdot 10\cdot 10=26000 $$

Esse tipo de modelagem aparece em placas, identificadores, nomes de usuário temporários e chaves de teste.

Também é útil distinguir quando devemos multiplicar e quando devemos somar. Multiplicamos quando as possibilidades correspondem a etapas sucessivas de um mesmo processo. Somamos quando temos casos mutuamente exclusivos. Por exemplo, se uma pessoa pode escolher um livro entre 5 opções ou um filme entre 3 opções, o total de escolhas é

$$ 5+3=8 $$

e não $5\cdot 3$, porque ela fará apenas uma escolha, e não duas escolhas sucessivas.

Outro exemplo: se um menu oferece 4 entradas e 3 sobremesas, e a pessoa deve escolher uma entrada e uma sobremesa, então o total é

$$ 4\cdot 3=12 $$

Mas se ela puder escolher apenas uma entrada ou uma sobremesa, então o total é

$$ 4+3=7 $$

Essa distinção entre soma e produto é uma das fontes mais comuns de erro em problemas combinatórios.

Uma forma útil de visualizar o princípio multiplicativo é por meio de uma árvore de possibilidades. Se uma decisão inicial tem 3 opções e cada uma delas leva a 2 opções finais, então a árvore terá $3\cdot 2=6$ folhas. Contar folhas de uma árvore de decisão é, em essência, aplicar o princípio fundamental da contagem.

Problemas de distribuição aparecem em contextos variados: colocar pessoas em filas, atribuir tarefas a máquinas, distribuir cartas, montar horários, formar códigos e percorrer árvores de decisão. Em algoritmos, o princípio multiplicativo é usado para estimar o tamanho de espaços de busca e a quantidade de combinações que um procedimento pode precisar examinar.

Em programação, esse princípio ajuda a raciocinar sobre força bruta e explosão combinatória. Se um problema exige testar todas as configurações possíveis e cada uma de $n$ posições admite $k$ valores, então o espaço total tem tamanho $k^n$. Mesmo para valores moderados de $k$ e $n$, isso cresce muito rapidamente, o que explica por que muitos problemas combinatórios se tornam computacionalmente difíceis.

Por exemplo, um vetor binário de tamanho $n$ possui exatamente

$$ 2^n $$

configurações possíveis, pois cada posição pode valer 0 ou 1. Para $n=10$, isso dá $2^{10}=1024$ possibilidades; para $n=20$, temos $2^{20}=1\,048\,576$; para $n=50$, o número ultrapassa um quatrilhão. Esse crescimento explica por que muitos algoritmos de busca exaustiva deixam de ser viáveis rapidamente.

Nem sempre, porém, o princípio multiplicativo pode ser aplicado de forma ingênua. Se um problema impõe uma restrição global, como “a senha deve ter exatamente duas letras iguais” ou “a sequência não pode conter dois símbolos consecutivos idênticos”, então as escolhas deixam de ser completamente independentes e o modelo precisa ser refinado com casos, recorrência, inclusão-exclusão ou enumeração recursiva.

Uma visão mais abstrata do princípio fundamental da contagem é pensar em funções. Se o primeiro passo corresponde a escolher um elemento de um conjunto $A_1$, o segundo de $A_2$, e assim por diante, então cada resultado possível do processo pode ser visto como uma tupla

$$ (a_1,a_2,\ldots,a_n)\in A_1\times A_2\times\cdots\times A_n $$

Portanto, o número de resultados possíveis é exatamente o tamanho do produto cartesiano desses conjuntos, o que justifica formalmente a regra multiplicativa.

Exemplo: se $A=\{a,b\}$ e $B=\{1,2,3\}$, então

$$ A\times B=\{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\} $$

e, portanto, $|A\times B|=2\cdot 3=6$.

Antes de falar em permutação, é importante distinguir três ideias próximas, mas diferentes: arranjo, permutação e combinação. No arranjo simples, escolhemos $p$ elementos dentre $n$ elementos distintos, sem repetição e levando a ordem em conta. A quantidade de arranjos simples é

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

Exemplo: se temos 5 pessoas e queremos escolher presidente, vice-presidente e secretário, então a ordem importa, porque trocar os cargos produz outro resultado. O número de possibilidades é

$$ A_{5,3}=\frac{5!}{2!}=5\cdot 4\cdot 3=60 $$

Uma permutação simples ocorre quando tomamos todos os $n$ elementos e apenas os reordenamos. Portanto, é um caso particular de arranjo em que $p=n$:

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

Exemplo: de quantas maneiras podemos ordenar 4 livros distintos em uma prateleira? Basta calcular

$$ P_4=4!=24 $$

A interpretação é direta: há 4 escolhas para a primeira posição, 3 para a segunda, 2 para a terceira e 1 para a última.

Permutações aparecem sempre que todos os elementos participam e apenas sua ordem muda. Isso acontece em ordenações, rankings, escalonamentos, geração de sequências e enumeração exaustiva de estados em algoritmos.

Quando existem repetições entre os elementos, permutações diferentes podem se tornar indistinguíveis. Nesse caso, usamos a fórmula de permutação com repetição. Se temos $n$ elementos, dos quais $k_1$ são iguais de um tipo, $k_2$ são iguais de outro tipo, e assim por diante, então

$$ P_n^{k_1,k_2,\ldots,k_r}=\frac{n!}{k_1!k_2!\cdots k_r!} $$

Exemplo: na palavra ARARA, temos 5 letras, com 3 letras A e 2 letras R. O número de rearranjos distintos é

$$ \frac{5!}{3!2!}=10 $$

Nesse caso, dividimos por $3!$ e $2!$ porque permutar entre si letras iguais não produz uma nova palavra.

Em ciência da computação, permutações aparecem em problemas como ordenação de tarefas, busca de caminhos Hamiltonianos, enumeração de testes, geração de senhas e análise de heurísticas para problemas do tipo caixeiro-viajante. O crescimento fatorial de $n!$ explica por que muitos desses problemas se tornam rapidamente inviáveis por força bruta.

Se temos um conjunto com $n$ elementos e escolhemos $p$ deles sem repetição e sem levar a ordem em conta, estamos diante de uma combinação. Nesse caso, grupos com os mesmos elementos em ordens diferentes contam apenas uma vez.

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

Essa fórmula pode ser entendida a partir dos arranjos. Se primeiro contarmos todas as maneiras de escolher e ordenar $p$ elementos dentre $n$, obtemos $A_{n,p}$. Mas cada grupo de $p$ elementos foi contado $p!$ vezes, uma para cada ordenação possível. Por isso dividimos por $p!$.

Em outras palavras, combinação responde a perguntas do tipo “quais elementos foram escolhidos?”, enquanto arranjo responde a perguntas do tipo “quais elementos foram escolhidos e em que ordem?”. Essa distinção é fundamental em combinatória.

Exemplo: de quantas maneiras podemos escolher 3 alunos dentre 8 para formar uma comissão?

$$ C_{8,3}=\frac{8!}{3!5!}=\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}=56 $$

Aqui a ordem não importa: escolher Ana, Bruno e Carla é o mesmo grupo que escolher Carla, Ana e Bruno.

É útil comparar combinação com arranjo usando o mesmo exemplo. Se os 3 alunos fossem escolhidos para ocupar os cargos de presidente, vice e secretário, então a ordem importaria e o problema seria de arranjo. Se são apenas membros de uma comissão sem cargos distintos, então usamos combinação.

Outro exemplo clássico: quantas mãos de 5 cartas podem ser formadas a partir de um baralho de 52 cartas? Como a ordem em que as cartas são recebidas não altera a mão, temos

$$ C_{52,5}=\frac{52!}{5!47!}=2\,598\,960 $$

O valor é grande porque o número de subconjuntos possíveis cresce muito rapidamente, mesmo quando $p$ é pequeno em relação a $n$.

Também é útil observar alguns casos particulares:

$C_{n,0}=1$, pois existe exatamente uma maneira de escolher nenhum elemento;
$C_{n,1}=n$, pois escolher 1 elemento dentre $n$ equivale a indicar qual deles foi escolhido;
$C_{n,n}=1$, pois existe apenas o subconjunto formado por todos os elementos.

Além disso, vale a simetria

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

porque escolher $p$ elementos para formar um grupo equivale a escolher os $n-p$ elementos que ficarão de fora.

Exemplo: escolher 2 pessoas dentre 10 para uma tarefa é equivalente, do ponto de vista da contagem, a escolher as 8 pessoas que não participarão. Por isso,

$$ C_{10,2}=C_{10,8}=45 $$

Combinações também estão diretamente ligadas à expansão do binômio:

$$ (x+y)^n=\sum_{p=0}^{n} C_{n,p}x^{n-p}y^p $$

Os coeficientes binomiais surgem porque cada termo da expansão corresponde à escolha das posições em que o fator $y$ aparece entre os $n$ fatores do produto.

Combinações aparecem em amostragem, seleção de atributos, escolha de subconjuntos, análise de possibilidades em algoritmos e problemas de busca em que apenas o conjunto escolhido importa, e não sua ordem interna.

Em aprendizado de máquina e ciência de dados, por exemplo, combinações aparecem na escolha de subconjuntos de variáveis, em validação cruzada, em testes de hipótese e em algoritmos que exploram subconjuntos candidatos. Em algoritmos de força bruta, o número de subconjuntos de tamanho $p$ de um conjunto com $n$ elementos é justamente $C_{n,p}$, e o número total de subconjuntos é

$$ \sum_{p=0}^{n} C_{n,p}=2^n $$

Esse fato conecta combinações diretamente com explosão combinatória e análise de custo em busca exaustiva.

Funções geradoras são ferramentas algébricas usadas para codificar sequências numéricas em séries formais. Em combinatória, elas permitem transformar problemas de contagem em manipulação de polinômios ou séries de potências. Em vez de contar objetos diretamente, representamos possibilidades por coeficientes.

A ideia central é a seguinte: se uma sequência é dada por

$$ a_0,a_1,a_2,\ldots $$

podemos associá-la à série formal

$$ G(x)=a_0+a_1x+a_2x^2+\cdots $$

Nessa representação, o coeficiente de $x^n$ guarda a informação sobre o termo $a_n$ da sequência. Em muitos problemas, $a_n$ conta quantos objetos de tamanho $n$, peso $n$ ou soma $n$ existem.

Um polinômio tem a forma

$$ p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0 $$

e uma série de potências é uma expressão do tipo

$$ a_0+a_1x+a_2x^2+\cdots $$

Em combinatória, quase sempre tratamos essas expressões formalmente. O interesse principal não é a convergência analítica da série, mas a interpretação de seus coeficientes.

Em uma função geradora ordinária, o coeficiente de $x^k$ costuma representar a quantidade de objetos de tamanho, peso ou soma igual a $k$. Por exemplo, a série geométrica

$$ 1+x+x^2+x^3+\cdots=\frac{1}{1-x},\qquad |x|<1 $$

pode ser interpretada como codificando a possibilidade de escolher qualquer quantidade não negativa de uma certa unidade.

Por exemplo, se queremos contar quantas formas existem de pagar um valor usando moedas de 1 unidade, então cada potência de $x$ representa um valor e cada coeficiente representa quantas maneiras esse valor pode ser obtido. Quando há mais de um tipo de escolha, multiplicamos funções geradoras.

Considere um exemplo simples: suponha que uma variável $y$ possa assumir apenas os valores 0, 1 ou 2. Então a função geradora associada é

$$ 1+x+x^2 $$

porque há uma forma de obter soma 0, uma forma de obter soma 1 e uma forma de obter soma 2. Se tivermos duas variáveis independentes com esse mesmo conjunto de valores, então a função geradora total é

$$ (1+x+x^2)^2 $$

Expandindo, obtemos

$$ (1+x+x^2)^2=1+2x+3x^2+2x^3+x^4 $$

O coeficiente de $x^2$ é 3, o que significa que existem 3 maneiras de somar 2 usando duas variáveis com valores em $\{0,1,2\}$:

$$ (0,2),\;(1,1),\;(2,0) $$

Exemplo: quantas são as soluções inteiras da equação abaixo, sabendo que $x_1$ e $x_2$ pertencem ao conjunto $\{1,2,3\}$ e $x_3$ pertence ao conjunto $\{2,3,5\}$?

$$ x_1+x_2+x_3=6 $$

Associamos a cada variável um polinômio cujos expoentes representam os valores permitidos:

$$ p_1(x)=x+x^2+x^3,\qquad p_2(x)=x+x^2+x^3,\qquad p_3(x)=x^2+x^3+x^5 $$

A função geradora do problema é o produto

$$ F(x)=p_1(x)p_2(x)p_3(x) $$

Expandindo, obtemos

$$ F(x)=x^4+3x^5+5x^6+6x^7+5x^8+4x^9+2x^{10}+x^{11} $$

O coeficiente de $x^6$ é 5, portanto existem 5 soluções possíveis.

A razão pela qual isso funciona é que, ao multiplicar os polinômios, cada termo do produto escolhe exatamente um valor permitido para cada variável, e a soma dos expoentes registra a soma final. O coeficiente conta quantas maneiras diferentes essa soma pode ser obtida.

Podemos inclusive verificar esse tipo de contagem por enumeração direta. Um código simples em Python para o exemplo acima seria:

valores1 = [1, 2, 3]
valores2 = [1, 2, 3]
valores3 = [2, 3, 5]

total = 0
for x1 in valores1:
    for x2 in valores2:
        for x3 in valores3:
            if x1 + x2 + x3 == 6:
                total += 1

print(total)  # 5

Esse código não usa diretamente a função geradora, mas conta exatamente o mesmo objeto combinatório. A vantagem da função geradora é que ela organiza a contagem de forma simbólica e escalável, permitindo manipular restrições de maneira mais elegante.

Funções geradoras ordinárias são especialmente úteis em partições, recorrências e contagem com restrições. Já funções geradoras exponenciais aparecem com mais frequência quando estamos contando objetos rotulados, isto é, objetos cujas posições ou identidades importam explicitamente.

A diferença principal é a seguinte:

na função geradora ordinária, escrevemos uma sequência como $\sum a_nx^n$;
na função geradora exponencial, escrevemos a sequência como $\sum a_n\frac{x^n}{n!}$.

O fator $n!$ no denominador torna a função geradora exponencial especialmente adequada quando estamos contando estruturas rotuladas, porque ele compensa o número de ordenações possíveis dos rótulos.

Exemplo clássico: a função geradora exponencial do número de subconjuntos de um conjunto rotulado pode ser relacionada à expansão de

$$ e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!} $$

e, mais geralmente, muitas famílias de estruturas combinatórias rotuladas admitem descrições elegantes por meio de exponenciais, produtos e composições de séries.

Em ciência da computação, funções geradoras aparecem na análise assintótica de algoritmos, no estudo de recorrências, em contagem de estruturas discretas e em métodos simbólicos para enumeração automática. Elas também se conectam com análise de complexidade e combinatória analítica.

Por exemplo, se um algoritmo satisfaz uma recorrência cujo número de objetos de tamanho $n$ depende de objetos menores, a função geradora frequentemente transforma a recorrência em uma equação algébrica ou diferencial mais simples de manipular. Isso acontece em análise de árvores, strings, partições, caminhos em grafos e estruturas recursivas em geral.

O princípio de inclusão e exclusão corrige contagens em que diferentes conjuntos têm interseções. Quando somamos diretamente os tamanhos de dois conjuntos, elementos em comum são contados duas vezes. Por isso, precisamos subtrair a interseção:

$$ n(\mathcal{A}\cup\mathcal{B})=n(\mathcal{A})+n(\mathcal{B})-n(\mathcal{A}\cap\mathcal{B}) $$

Exemplo: em uma turma, 18 alunos estudam programação, 12 estudam matemática discreta e 5 estudam ambos. Quantos estudam ao menos uma das duas disciplinas?

$$ n(\mathcal{A}\cup\mathcal{B})=18+12-5=25 $$

Sem subtrair a interseção, os 5 alunos que pertencem aos dois conjuntos seriam contados duas vezes.

Com três conjuntos, o padrão continua, mas alternamos sinais:

$$ \begin{aligned} n(\mathcal{A}\cup\mathcal{B}\cup\mathcal{C}) ={}&n(\mathcal{A})+n(\mathcal{B})+n(\mathcal{C})\\ &-n(\mathcal{A}\cap\mathcal{B})-n(\mathcal{A}\cap\mathcal{C})-n(\mathcal{B}\cap\mathcal{C})\\ &+n(\mathcal{A}\cap\mathcal{B}\cap\mathcal{C}) \end{aligned} $$

As interseções duplas são subtraídas porque causam sobrecontagem; a interseção tripla é somada de volta porque foi subtraída em excesso.

Esse princípio é importante em probabilidade, em contagem de casos proibidos, em fórmulas para permutações com restrições e em análise de consultas sobre conjuntos sobrepostos. Em computação, ele aparece em bancos de dados, análise de logs, estatísticas de usuários com múltiplas categorias, cobertura de testes e contagem de elementos presentes em múltiplas estruturas.

Particionar um conjunto significa dividi-lo em blocos ou grupos segundo certas regras. Em muitos problemas, a dificuldade principal está em decidir se os grupos são distintos ou indistinguíveis e se a ordem entre eles importa.

A notação

$$ \binom{n}{k} $$

lê-se “$n$ escolhe $k$” e representa o número de maneiras de escolher $k$ elementos dentre $n$ sem levar a ordem em conta. Essa mesma notação aparece no binômio de Newton:

$$ (x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k $$

Os coeficientes binomiais aparecem aí porque, ao expandir o produto, precisamos escolher em quais das $n$ posições entra o termo $y$; isso equivale exatamente a escolher $k$ posições dentre $n$.

Exemplo: de quantas maneiras podemos repartir 6 pessoas em 3 grupos distintos de 2 pessoas cada?

Se os grupos são identificados como $G_1$, $G_2$ e $G_3$, podemos escolher sucessivamente:

$$ \binom{6}{2}\binom{4}{2}\binom{2}{2}=15\cdot 6\cdot 1=90 $$

Se os grupos não fossem distintos, ainda precisaríamos dividir por $3!$, pois trocar os rótulos dos grupos não criaria uma nova partição.

Em geral, quando há repetição de tamanhos ou grupos indistinguíveis, aparecem divisões por fatoriais para eliminar sobrecontagens. Uma forma genérica de escrever esse tipo de contagem é

$$ \frac{\binom{n}{k}\binom{n-k}{k}\cdots}{r!} $$

onde $r!$ corrige a indistinguibilidade entre grupos de mesmo papel.

Em grafos, árvores e redes, a enumeração também depende de como as escolhas são estruturadas. Informalmente, um grafo é um conjunto de pontos, chamados vértices, ligados por conexões, chamadas arestas. Uma árvore é um tipo especial de grafo sem ciclos, isto é, sem caminhos fechados. Uma rede pode ser vista como um grafo usado para modelar infraestrutura ou fluxo, como estradas, computadores conectados, links de comunicação ou dependências entre tarefas.

Essas estruturas aparecem em quase toda a ciência da computação: grafos modelam redes sociais, sistemas de recomendação, compiladores, mapas e dependências; árvores aparecem em estruturas de dados, parsing, indexação e busca; redes aparecem em telecomunicações, distribuição, roteamento e escalonamento.

Do ponto de vista combinatório, podemos querer contar caminhos, árvores geradoras, maneiras de particionar vértices, formas de distribuir carga na rede ou quantas estruturas distintas um algoritmo precisa explorar.

Na imagem acima, podemos considerar que cada letra representa uma cidade e as linhas são conexões entre elas. Se há 4 maneiras de ir de A até B e 3 maneiras de ir de B até C, então o número total de maneiras de ir de A até C passando por B é

$$ P=4\cdot 3=12 $$

Esse tipo de raciocínio aparece naturalmente em redes de comunicação, roteamento, grafos de estados e árvores de decisão. Se um pacote pode seguir 4 enlaces no primeiro salto e, a partir do nó intermediário escolhido, 3 enlaces válidos no segundo salto, então o total de trajetórias com esse formato também é 12.

Outro exemplo de computação: em uma árvore de decisão binária com profundidade 5, cada nível oferece 2 escolhas. O número máximo de folhas é

$$ 2^5=32 $$

Essa conta aparece em análise de busca, jogos, poda alfa-beta, circuitos lógicos e classificação por árvores.

Também podemos pensar em grafos de estados. Se um algoritmo visita estados de uma máquina ou de um jogo e cada estado possui até 3 transições válidas durante 4 etapas, o número máximo de sequências possíveis é limitado por

$$ 3^4=81 $$

Esse tipo de estimativa combinatória ajuda a prever custo de busca, profundidade explorável e necessidade de heurísticas.

Para ver exemplo de código desta seção, veja [4].

Recursão é uma estratégia natural para enumerar objetos combinatórios. A ideia é quebrar o problema em escolhas menores do mesmo tipo: em cada etapa, decidimos incluir ou não incluir um elemento, fixar uma posição, expandir um ramo de busca ou avançar para o próximo estado.

Do ponto de vista matemático, a recursão aparece quando definimos um objeto em termos de versões menores dele mesmo. Em enumeração, isso significa construir uma solução parcial e depois decidir como estendê-la. Em muitos problemas, a estrutura natural é uma árvore de decisão: cada nó representa um estado parcial e cada aresta representa uma escolha possível.

Um exemplo simples é a enumeração de subsequências não vazias do conjunto ordenado $I=\{1,2,3,4\}$. Antes de listar os casos, vale explicar a ordem lexicográfica. Dizemos que uma lista está em ordem lexicográfica quando ela segue uma convenção parecida com a ordem de dicionário: primeiro comparamos o primeiro elemento, depois o segundo, e assim por diante. Assim, por exemplo,

$$ (1,2,4) < (1,3) $$

porque ambos começam com 1, mas 2 vem antes de 3. Do mesmo modo,

$$ (2,3) < (2,4) $$

porque os primeiros elementos coincidem e 3 vem antes de 4.

Usando essa convenção, podemos enumerar as subsequências não vazias de $I$ da seguinte forma:

Como $I$ tem 4 elementos, o número total de subconjuntos é $2^4=16$. Excluindo o conjunto vazio, restam 15 subsequências não vazias, exatamente como na listagem acima.

Uma forma de pensar recursivamente nesse problema é: para cada elemento, ou ele entra na subsequência ou não entra. Essa bifurcação produz uma árvore binária de decisões. Se o conjunto tiver $n$ elementos, a árvore completa terá até $2^n$ folhas, o que explica por que a enumeração cresce tão rapidamente.

Podemos também formular a recorrência para o número de subconjuntos de um conjunto com $n$ elementos. Se chamarmos esse número de $T(n)$, então

$$ T(n)=2T(n-1),\qquad T(0)=1 $$

pois, ao introduzir um novo elemento, cada subconjunto anterior dá origem a dois: um que contém o novo elemento e outro que não o contém. A solução dessa recorrência é

$$ T(n)=2^n $$

Esse é um exemplo simples, mas importante, de como combinatória e recorrências aparecem juntas.

Em um algoritmo recursivo, cada chamada escolhe o próximo elemento possível e continua a enumeração a partir desse ponto, evitando repetições ao nunca voltar para posições anteriores. Um código simples em Python para gerar subconjuntos em ordem lexicográfica é:

itens = [1, 2, 3, 4]

def enumera(inicio, atual):
    if atual:
        print(atual)
    for i in range(inicio, len(itens)):
        atual.append(itens[i])
        enumera(i + 1, atual)
        atual.pop()

enumera(0, [])

Nesse programa, a variável inicio impede que o algoritmo retorne a posições anteriores do vetor, o que elimina repetições. A lista atual guarda a solução parcial em construção.

Esse tipo de abordagem está diretamente ligado a backtracking. Em vez de construir todas as soluções de uma vez, o algoritmo percorre uma árvore de decisões, expandindo um ramo por vez. Quando percebe que um ramo não pode levar a uma solução válida, ele recua e tenta outra possibilidade.

Um exemplo clássico é a geração de permutações sem repetição. Se queremos gerar todas as permutações de $\{1,2,3\}$, escolhemos um elemento para a primeira posição, depois um para a segunda entre os restantes, e assim sucessivamente. O número total de folhas da árvore de busca é

$$ 3!=6 $$

Em problemas maiores, porém, a árvore cresce de forma muito agressiva, e por isso o custo computacional costuma ser o fator limitante.

Em ciência da computação, enumeração recursiva aparece em geração de subconjuntos, permutações, combinações, caminhos em grafos, solução de sudoku, problemas de satisfação de restrições, parsing e busca em espaços discretos. A principal dificuldade costuma ser o crescimento explosivo do número de casos, o que torna poda, memoização e critérios de viabilidade extremamente importantes.

Nessa classe de problemas, cada posição da sequência aceita apenas certos tipos de símbolos. A contagem depende de quais posições aceitam letras, números ou outros caracteres, e também de saber se repetições são permitidas.

Exemplo: quantas placas podem ser formadas com 3 letras seguidas de 4 dígitos, admitindo repetição em todas as posições?

$$ 26\cdot 26\cdot 26\cdot 10\cdot 10\cdot 10\cdot 10=17\,576\,000 $$

Aqui cada posição de letra tem 26 possibilidades e cada posição de dígito tem 10 possibilidades. Como as escolhas são independentes, usamos o princípio multiplicativo.

Se exigirmos que as letras não se repitam entre si e que os dígitos também não se repitam, então a contagem muda para

$$ 26\cdot 25\cdot 24\cdot 10\cdot 9\cdot 8\cdot 7 $$

Esse tipo de restrição é muito comum em geração de identificadores, códigos promocionais, tokens, senhas, chaves temporárias e testes de software. Em algoritmos, problemas com restrições por posição aparecem em busca com poda, geração de cadeias válidas e verificação de linguagens formais.

Considere, por exemplo, uma senha com o formato

$$ \text{letra maiúscula} + \text{letra minúscula} + \text{dígito} + \text{dígito} + \text{símbolo} $$

Se admitirmos 26 letras maiúsculas, 26 letras minúsculas, 10 dígitos e 8 símbolos especiais permitidos, então o número total de senhas é

$$ 26\cdot 26\cdot 10\cdot 10\cdot 8=540\,800 $$

Um código simples em Python para gerar uma senha aleatória com esse formato seria:

import random
import string

simbolos = "!@#$%&*?"

senha = (
    random.choice(string.ascii_uppercase) +
    random.choice(string.ascii_lowercase) +
    random.choice(string.digits) +
    random.choice(string.digits) +
    random.choice(simbolos)
)

print(senha)

Outro caso comum é a geração de tokens. Suponha um token alfanumérico de 6 posições usando letras maiúsculas e dígitos. O alfabeto disponível tem

$$ 26+10=36 $$

símbolos, de modo que o número total de tokens possíveis é

$$ 36^6=2\,176\,782\,336 $$

Esse tipo de contagem é importante para estimar colisão, adivinhação por força bruta e tamanho do espaço de busca. Um gerador simples seria:

import random
import string

alfabeto = string.ascii_uppercase + string.digits
token = "".join(random.choice(alfabeto) for _ in range(6))

print(token)

Também podemos impor restrições adicionais. Suponha uma chave curta de 4 caracteres em que:

o primeiro caractere deve ser uma letra;
o segundo deve ser um dígito;
o terceiro deve ser diferente do segundo, mas também dígito;
o último deve ser uma letra diferente da primeira.

Nesse caso, a contagem fica

$$ 26\cdot 10\cdot 9\cdot 25 $$

porque a primeira letra tem 26 escolhas, o primeiro dígito tem 10, o segundo dígito tem 9 por não poder repetir o anterior, e a última letra tem 25 por não poder repetir a primeira.

Esse tipo de regra aparece em chaves temporárias, códigos de ativação, identificadores legíveis por humanos e sequências com validação sintática. A implementação também precisa respeitar a dependência entre posições:

import random
import string

primeira = random.choice(string.ascii_uppercase)
d1 = random.choice(string.digits)
d2 = random.choice([d for d in string.digits if d != d1])
ultima = random.choice([c for c in string.ascii_uppercase if c != primeira])

chave = primeira + d1 + d2 + ultima
print(chave)

Em todos esses exemplos, o ponto principal é identificar, para cada posição, quantas escolhas continuam válidas dado o histórico das escolhas anteriores. Em muitos casos, toda a dificuldade do problema está nessa dependência entre posições. Em segurança da informação, por exemplo, essa contagem ajuda a estimar entropia, resistência a ataques por tentativa e o impacto de restrições mal escolhidas no espaço de senhas ou chaves disponíveis.

Glossário

Arranjo simples: Escolha ordenada de $p$ elementos dentre $n$, sem repetição.
Backtracking: Técnica de busca recursiva que explora possibilidades e recua quando um ramo deixa de ser viável.
Combinação: Escolha de elementos em que a ordem não importa.
Explosão combinatória: Crescimento muito rápido do número de casos possíveis em um problema discreto.
Fatorial: Produto dos inteiros positivos de 1 até $n$, denotado por $n!$.
Força bruta: Estratégia que testa exaustivamente todas as possibilidades de solução.
Função geradora: Série formal ou polinômio cujos coeficientes codificam uma sequência de interesse combinatório.
Função geradora exponencial: Função geradora especialmente útil para contar estruturas rotuladas.
Função geradora ordinária: Função geradora em que o coeficiente de $x^n$ representa a quantidade de objetos de tamanho ou soma igual a $n$.
Lexicográfica: Ordem de enumeração análoga à ordem de dicionário.
Partição: Divisão de um conjunto em subconjuntos segundo certas regras.
Permutação: Reordenação de todos os elementos de um conjunto.
Permutação com repetição: Contagem de rearranjos quando alguns elementos são indistinguíveis.
Produto cartesiano: Conjunto de todas as tuplas obtidas escolhendo um elemento de cada conjunto dado.
Princípio de inclusão e exclusão: Regra de contagem que corrige sobrecontagens causadas por interseções entre conjuntos.
Princípio multiplicativo: Regra segundo a qual o número total de possibilidades em etapas sucessivas é o produto das possibilidades de cada etapa.
Subconjunto: Conjunto formado apenas por elementos de outro conjunto.

Referências:

Funções geradoras e problemas de contagem - IME UFRGS
Princípio da inclusão-exclusão
Resumo de análise combinatória
Algoritmos de enumeração

“Nosso planeta sobreviveu a tudo, em seu tempo. Certamente sobreviverá a nós.”

2 - Análise Combinatória