Análise Combinatória e Contagem: Técnicas Discretas e Princípio dos Pombos

Análise combinatória e contagem

Abra o seu armário pela manhã. Se você tem 3 camisetas e 2 calças, quantas combinações diferentes de roupas você consegue vestir? Qualquer pessoa responde rapidamente: 3 vezes 2, totalizando 6 combinações. Sem perceber, você acabou de aplicar a regra do produto da análise combinatória, o mesmo princípio que define quantos séculos um computador levaria para quebrar a sua senha mestre por força bruta.

A análise combinatória é a arte e a ciência de contar coisas sem precisar listar uma por uma. No desenvolvimento de software, a contagem eficiente não serve para resolver enigmas de passatempo: ela determina a complexidade de algoritmos, calcula o consumo de memória de estruturas de dados, mede a força de chaves criptográficas e prova limites intransponíveis da computação (como a impossibilidade de criar um compressor de arquivos que diminua o tamanho de qualquer dado).

Esta aula ensina os princípios de contagem essenciais para a computação. Começaremos com as regras da soma e do produto aplicadas à arquitetura de software (seções 1 e 2), avançaremos para a diferença formal entre permutações e combinações implementadas em Go (seções 3 a 5), exploraremos o Princípio da Casa dos Pombos e o paradoxo do aniversário (seções 6 e 7), e fecharemos com a armadilha do compressor perfeito, exercícios resolvidos e glossário.

1. As regras fundamentais: soma e produto

Toda a análise combinatória complexa é construída sobre duas regras elementares que correspondem diretamente aos blocos de decisão de um programa.

A regra da soma (escolha disjunta OU)

Se uma tarefa pode ser realizada de n₁ maneiras e uma segunda tarefa alternativa pode ser realizada de n₂ maneiras, e as duas tarefas não podem ser feitas juntas (são eventos mutuamente exclusivos), então há n₁ + n₂ maneiras de realizar uma OU outra.

No software: Se o seu gateway de pagamentos aceita 3 bancos diferentes via Pix OU 2 operadoras de cartão de crédito, o cliente tem exatamente 3 + 2 = 5 opções distintas para finalizar o checkout.

Quando os conjuntos não são disjuntos (ou seja, possuem interseção), aplicamos o Princípio da Inclusão-Exclusão: |A ∪ B| = |A| + |B| - |A ∩ B| Subtraímos a interseção para não contar duas vezes os usuários que possuem Pix e cartão habilitados ao mesmo tempo.

A regra do produto (escolha sequencial E)

Se um procedimento é formado por duas etapas sucessivas e independentes, onde a primeira etapa tem n₁ resultados possíveis e a segunda etapa tem n₂ resultados possíveis para cada resultado da primeira, então o procedimento completo tem n₁ · n₂ resultados possíveis.

O diagrama acima compara os dois comportamentos. No painel superior, a regra da soma atua sobre caminhos alternativos que convergem para uma escolha única entre Pix ou Cartão. No painel inferior, a regra do produto opera em pipeline: o usuário precisa fornecer uma senha com 26 letras possíveis E em seguida digitar um código de segundo fator (MFA) de 6 dígitos decimais (10⁶ possibilidades). O espaço total de combinações que um invasor precisa percorrer é a multiplicação das etapas: 26 · 10⁶ hipóteses.

2. A força de senhas e a notação exponencial

A regra do produto explica por que o tamanho de uma senha é infinitamente mais importante do que a complexidade de símbolos raros que os formulários costumam exigir.

Suponha que uma senha tenha comprimento L e use um conjunto de caracteres de tamanho C (o alfabeto):

• Apenas dígitos decimais (0 a 9): C = 10.
• Letras minúsculas e maiúsculas (a-z, A-Z): C = 52.
• Alfanumérico com símbolos comuns: C = 94.

O número total de senhas possíveis de tamanho L é calculado pela regra do produto repetida L vezes: Total = Cᴸ

Se você cria um PIN de 4 dígitos (C = 10, L = 4), existem 10⁴ = 10.000 combinações. Uma GPU moderna testa isso em menos de 1 milissegundo.

Se você cria uma senha de 8 caracteres alfanuméricos com símbolos (C = 94, L = 8), existem 94⁸ ≈ 6,09 · 10¹⁵ combinações.

Agora veja o poder do expoente: se você mantiver apenas letras minúsculas fáceis de digitar (C = 26), mas aumentar o comprimento para 16 caracteres (formando uma frase com quatro palavras comuns): 26¹⁶ ≈ 4,36 · 10²² combinações.

Essa senha simples com palavras em minúsculas é 7 milhões de vezes mais difícil de ser quebrada por força bruta do que a senha curta cheia de arrobas e exclamações. A análise combinatória prova que o expoente L (o comprimento) domina a base C.

3. Permutações: quando a ordem importa

Uma permutação de um conjunto de objetos distintos é um arranjo ordenado desses objetos. Se a ordem em que os elementos aparecem altera o significado do resultado, estamos diante de uma permutação.

Se você tem n objetos distintos e quer organizar todos os n em uma fila, a regra do produto dita que o primeiro lugar tem n opções, o segundo tem n - 1, o terceiro tem n - 2, até o último que só tem 1 opção: P(n) = n · (n - 1) · (n - 2) · … · 1 = n! (lê-se n fatorial).

Se você tem n objetos disponíveis, mas quer escolher e ordenar apenas k deles (onde k ≤ n), o número de permutações é dado por: P(n, k) = n! / (n - k)!

Exemplo no software: Se você tem 10 nós em um cluster de mensageria e precisa definir uma rota sequencial de réplica mestre, secundária e terciária (k = 3), a ordem dos servidores importa completamente (o mestre processa escritas; os outros apenas leem). P(10, 3) = 10! / (10 - 3)! = 10! / 7! = 10 · 9 · 8 = 720 configurações de réplica possíveis.

4. Combinações: quando a ordem não importa

Uma combinação é uma seleção de k elementos escolhidos a partir de um conjunto de n objetos, onde a ordem da escolha é irrelevante.

Se você vai selecionar 3 desenvolvedores em uma equipe de 10 pessoas para compor um comitê de plantão de incidentes, escolher {Alice, Bob, Carlos} é rigorosamente o mesmo comitê que {Carlos, Alice, Bob}. A ordem não cria um time novo.

O diagrama acima coloca essa distinção em evidência com um conjunto de três microserviços {A, B, C}. No grupo da esquerda (permutação), montar a rota A → B é diferente de montar a rota B → A; cada par direcionado conta como uma opção única, gerando 6 rotas. No grupo da direita (combinação), agrupar A e B em um cluster redundante não tem direção; a ordem é descartada, dividindo o total pelo número de formas de embaralhar o par (2!), resultando em apenas 3 combinações.

A fórmula de combinações simples, denotada por C(n, k) ou pelo coeficiente binomial, divide a permutação por k! para eliminar todas as duplicatas causadas pela ordem: C(n, k) = n! / [k! · (n - k)!]

No exemplo do comitê de 3 plantonistas entre 10 desenvolvedores: C(10, 3) = 10! / [3! · 7!] = (10 · 9 · 8) / (3 · 2 · 1) = 720 / 6 = 120 comitês distintos.

5. Implementando contagem sem overflow em Go

Calcular combinações no computador exige cuidado extremo. O valor do fatorial cresce em um ritmo assustador:

• 10! = 3.628.800
• 20! = 2.432.902.008.176.640.000
• 21! ultrapassa 2⁶⁴ e estoura a capacidade de um inteiro uint64 em Go.

Se você tentar calcular C(30, 3) fazendo fatorial(30) / (fatorial(3) * fatorial(27)), o programa sofrerá overflow no fatorial(30) logo na primeira multiplicação, mesmo que o resultado final da combinação seja apenas 4.060 (um número minúsculo que cabe com folga em qualquer inteiro).

A boa prática consiste em simplificar os termos antes de multiplicar e alternar multiplicações e divisões:

package main

import "fmt"

// Combinacao calcula C(n, k) sem estourar inteiros desnecessariamente.
func Combinacao(n, k int) uint64 {
	// Propriedade de simetria do Triangulo de Pascal: C(n, k) == C(n, n-k)
	if k < 0 || k > n {
		return 0
	}
	if k > n/2 {
		k = n - k
	}

	var resultado uint64 = 1
	for i := 1; i <= k; i++ {
		// Multiplica e divide a cada passo para manter o numero baixo
		resultado = resultado * uint64(n-i+1)
		resultado = resultado / uint64(i)
	}

	return resultado
}

func main() {
	n, k := 30, 3
	fmt.Printf("C(%d, %d) = %d\n", n, k, Combinacao(n, k)) // Saida: 4060
}

A propriedade matemática garante que a divisão intermediária resultado / i sempre será um número inteiro exato a cada passo, porque o produto de i inteiros consecutivos é obrigatoriamente divisível por i!.

6. O Princípio da Casa dos Pombos

Formulado pelo matemático Peter Gustav Lejeune Dirichlet em 1834, o Princípio da Casa dos Pombos (Pigeonhole Principle) afirma uma obviedade desarmante: Se você tem n pombos e k casas de pombos, e o número de pombos for maior que o número de casas (n > k), então pelo menos uma casa precisa conter dois ou mais pombos.

Se você tem 5 pombos e apenas 4 gaiolas, é fisicamente impossível colocar no máximo um pombo em cada gaiola. Pelo menos uma delas terá superlotação.

A versão generalizada estende essa regra: se n itens forem distribuídos em k caixas, pelo menos uma caixa conterá no mínimo ⌈n / k⌉ itens (onde ⌈x⌉ é o teto, o arredondamento para cima).

O diagrama ilustra o impacto inevitável desse princípio em estruturas de dados reais. Cinco chaves de entrada (n = 5) são distribuídas em quatro posições de uma tabela hash (k = 4). Mesmo que a função de espalhamento seja a mais perfeita já criada por cientistas da computação, a quinta chave não tem onde se acomodar sem dividir espaço com alguém. A colisão na gaveta 2 não é uma falha de engenharia: é uma lei matemática inegociável.

7. O paradoxo do aniversário e colisões de hash

Muitos desenvolvedores acreditam intuitivamente que, para ter 50% de chance de colisão em uma tabela hash ou sistema de tokens, é necessário preencher metade do espaço disponível. A análise combinatória prova o contrário com o chamado paradoxo do aniversário.

Quantas pessoas aleatórias precisam estar reunidas em uma sala para que a probabilidade de pelo menos duas fazerem aniversário no mesmo dia do ano passe de 50%?

Como o ano tem 365 dias, a intuição leiga sugere algo em torno de 180 pessoas. No entanto, o cálculo combinatório revela que bastam apenas 23 pessoas.

A explicação reside no fato de que não estamos comparando as outras pessoas com você; estamos comparando todos os pares possíveis entre os participantes da sala. O número de pares possíveis entre n pessoas é uma combinação C(n, 2) = n(n - 1) / 2. Para n = 23: C(23, 2) = (23 · 22) / 2 = 253 pares de comparação.

Calculando a probabilidade de ninguém fazer aniversário no mesmo dia: P(sem colisão) = (365/365) · (364/365) · (363/365) · … · ((365 - 22)/365) ≈ 0,4927 (49,27%). Logo, a probabilidade de haver pelo menos uma colisão é 1 - 0,4927 = 50,73%.

Em segurança da informação, esse resultado dita que um identificador aleatório de N bits (como um token ou hash) começa a sofrer colisões não quando atingimos 2ᴺ registros, mas quando atingimos aproximadamente a raiz quadrada desse espaço: Quantidade crítica ≈ √(2ᴺ) = 2^(N/2)

Se você gera tokens curtos de 32 bits (onde 2³² ≈ 4,29 bilhões de valores possíveis), você não terá segurança para 4 bilhões de usuários: com apenas √(2³²) = 2¹⁶ = 65.536 tokens gerados, a chance de dois usuários receberem o mesmo token passa de 50%. Por essa razão, UUID v4 usa 122 bits de aleatoriedade pura, empurrando o limite crítico para 2⁶¹ registros (um número tão colossal que nenhuma aplicação no planeta atinge).

8. A prova matemática de que o compressor perfeito não existe

De tempos em tempos surge na Internet uma startup prometendo um algoritmo revolucionário de compressão capaz de reduzir o tamanho de qualquer arquivo sem nenhuma perda de dados (lossless compression), sugerindo que se você aplicar o compressor sucessivas vezes, um arquivo de 1 gigabyte encolheria até caber em 1 kilobyte.

O Princípio da Casa dos Pombos prova que esse produto é uma impossibilidade física.

Demonstração por contradição:

1. Suponha que exista um algoritmo capaz de reduzir o tamanho de absolutamente todo e qualquer arquivo sem perda.
2. Seja N um tamanho em bytes. O número total de arquivos possíveis de tamanho exatamente N bytes é 256ᴺ.
3. Se o algoritmo comprime todo arquivo de tamanho N, o resultado precisa ser um arquivo de tamanho menor ou igual a N - 1 bytes.
4. O número total de arquivos possíveis com tamanho até N - 1 bytes é a soma das potências de 256: Total de saídas = 1 + 256 + 256² + … + 256ᴺ⁻¹ = (256ᴺ - 1) / 255.
5. Repare que o número total de saídas possíveis é estritamente menor que o número de entradas (Total de saídas < 256ᴺ).

Pelo Princípio da Casa dos Pombos, se temos mais arquivos originais (pombos) do que arquivos compactados possíveis (casas), pelo menos dois arquivos originais diferentes obrigatoriamente produzirão exatamente o mesmo arquivo comprimido. Ao tentar descompactar esse arquivo resultante, o descompressor não saberá qual dos dois arquivos originais restaurar, tornando a recuperação sem perdas impossível.

Algoritmos reais de compressão (como Gzip, Zstandard ou Zip) só conseguem comprimir dados porque exploram redundâncias e padrões estatísticos. Para cada arquivo de texto que eles encolhem com sucesso, existe matematicamente outro arquivo com dados aleatórios que, ao passar pelo compressor, sai ligeiramente maior do que o original.

9. Erros comuns e boas práticas

1. Confundir permutação com combinação. Sempre pergunte a si mesmo: “se eu trocar a ordem de dois elementos da resposta, o resultado ainda é considerado a mesma coisa?”. Se for a mesma coisa, divida por k! (combinação); se a ordem alterar a função ou significado, use permutação.
2. Estouro silencioso em fatoriais. Nunca calcule fatoriais diretamente com tipos inteiros comuns sem verificar o valor de n. Em Go, use o algoritmo simplificado de combinação ou o pacote math/big para trabalhar com inteiros de precisão arbitrária (big.Int).
3. Ignorar o paradoxo do aniversário ao desenhar chaves primárias curtas. Se o seu sistema gera códigos de cupom de 6 caracteres decimais (1 milhão de códigos), colisões começarão a pipocar no banco de dados assim que cerca de 1.200 cupons forem emitidos (aproximadamente √(1.000.000)). Use saltos criptográficos longos ou garanta unicidade no schema com UNIQUE constraints.
4. Contar duas vezes por esquecer de subtrair a interseção. Em regras de filtros e relatórios de analytics, somar “usuários de mobile” com “usuários que compraram ontem” gera métricas infladas se você não aplicar o Princípio da Inclusão-Exclusão para expurgar quem fez as duas coisas.

10. Exercícios de fixação

Exercício 1: Geração de subconjuntos com recursão e backtracking em Go

Dado um slice com n elementos distintos, gere todas as 2ⁿ combinações possíveis de subconjuntos (o conjunto das partes estudado na aula 3), usando a árvore de decisão da regra do produto (onde cada elemento pode ser incluído ou ignorado).

Implementação em Go:

package main

import "fmt"

// GerarSubconjuntos cria todas as 2^n combinacoes possiveis.
func GerarSubconjuntos(itens []string) [][]string {
	var resultado [][]string
	var atual []string

	var backtrack func(indice int)
	backtrack = func(indice int) {
		// Caso base da inducao: avaliamos todos os elementos
		if indice == len(itens) {
			// Fazemos uma copia do slice atual para nao ser alterado depois
			copia := make([]string, len(atual))
			copy(copia, atual)
			resultado = append(resultado, copia)
			return
		}

		// Opcao 1 da regra do produto: NAO incluir o item atual
		backtrack(indice + 1)

		// Opcao 2 da regra do produto: INCLUIR o item atual
		atual = append(atual, itens[indice])
		backtrack(indice + 1)

		// Desfaz a escolha ao desempilhar a recursao (backtracking)
		atual = atual[:len(atual)-1]
	}

	backtrack(0)
	return resultado
}

func main() {
	elementos := []string{"auth", "cache", "log"}
	subconjuntos := GerarSubconjuntos(elementos)

	fmt.Printf("Total de combinacoes (2^%d = %d):\n", len(elementos), len(subconjuntos))
	for _, sub := range subconjuntos {
		fmt.Printf("  %v\n", sub)
	}
}

Exercício 2: Contagem de caminhos em uma grade (Grid Walking)

Um robô precisa caminhar em uma malha de coordenadas saindo de (0, 0) até (m, n). Ele só pode dar passos para a direita (R) ou para cima (U). Quantos caminhos diferentes o robô pode percorrer?

Resolução:

1. Para chegar em (m, n), o robô precisa dar obrigatoriamente m passos para a direita e n passos para cima, totalizando m + n passos no caminho.
2. Qualquer caminho válido é simplesmente uma sequência de m letras R e n letras U (por exemplo, RRURUU…).
3. Das m + n posições de passos totais, precisamos apenas escolher quais serão os m passos para a direita (os passos para cima ocuparão automaticamente as posições restantes).
4. Como a ordem de escolha das posições não cria caminhos repetidos, o resultado é a combinação simples: Total de caminhos = C(m + n, m) = (m + n)! / [m! · n!] Essa é a base combinatória usada em algoritmos de roteamento de pacotes em malhas de servidores e renderização gráfica.

11. Glossário

• Regra da soma: Princípio que estabelece que escolhas mutuamente exclusivas somam suas possibilidades.
• Regra do produto: Princípio que estabelece que etapas sequenciais independentes multiplicam suas possibilidades.
• Permutação: Agrupamento ordenado de elementos onde qualquer troca de posição gera um resultado diferente.
• Combinação: Agrupamento não-ordenado onde a disposição dos elementos não altera o conjunto resultante.
• Princípio da Casa dos Pombos: Teorema que garante que se n itens forem alocados em k posições com n > k, pelo menos uma posição conterá múltiplos itens.
• Paradoxo do aniversário: Fenômeno probabilístico decorrente do número quadrático de pares de comparação que acelera dramaticamente o surgimento de colisões em conjuntos aleatórios.
• Lossless compression: Compressão de dados sem perdas que permite reconstruir com exatidão o arquivo original.

12. Fontes e referências

• Rosen, Kenneth H. Discrete Mathematics and Its Applications, 8ª edição, McGraw-Hill, 2019 (Capítulo 6: Counting, e Capítulo 8: Advanced Counting Techniques).
• Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011 (Capítulo 7: Combinatorial Searching).
• Lehman, Eric; Leighton, F. Thomson; Meyer, Albert R. Mathematics for Computer Science, MIT OpenCourseWare, 2018 (Capítulo 14: Counting). Consulta em novembro de 2026.

Relacionados

• Lógica proposicional e de primeira ordem
• Indução matemática
• Teoria dos conjuntos, relações e funções
• Teoria dos números e aritmética modular
• Big O