Introdução à Análise Combinatória

Uma configuração é um elemento de um conjunto finito S: sequência, subconjunto ou tupla de escolhas. Contar é calcular |S|, em geral por uma bijeção com um produto, uma partição ou uma união já enumerável.

Soma, produto e inclusão-exclusão deste tópico — e permutações, combinações e distribuição nos seguintes — partem desse conjunto S.

As páginas se agrupam em quatro blocos. O primeiro decide se duas listas são o mesmo elemento de S: quando a ordem distingue, o objeto é um arranjo; quando não distingue, é uma seleção.

O segundo enumera por etapas. Alternativas que particionam S somam; escolhas sequenciais independentes multiplicam. A fatoração de n escreve cada divisor como tupla de expoentes, e |Dₙ| segue o mesmo produto.

O terceiro conclui existência sem listar: n objetos em m caixas forçam alguma caixa acima de um limiar.

O quarto calcula a união quando um elemento cai em mais de uma classe, e passa ao complemento quando o enunciado pede nenhum.

O que é Análise Combinatória? decide se a ordem distingue duas listas e aponta permutação ou combinação. As contas n₁+⋯+nₖ e n₁⋯nₖ estão em Princípios Fundamentais.

Classes disjuntas somam em Princípios Fundamentais. União com interseção não vazia e o complemento |U|−|A∪B| estão em Princípio da Inclusão-Exclusão.

Princípio da Casa dos Pombos garante alguma caixa com pelo menos ⌈n/m⌉ peças, sem apontar qual. Quantos elementos têm pelo menos uma propriedade, via o complemento de nenhum, está em Princípio da Inclusão-Exclusão.

O produto de k etapas independentes está em Princípios Fundamentais. O produto τ(n)=∏(eᵢ+1), pela bijeção entre divisor e expoentes aᵢ ∈ {0,…,eᵢ}, está em Contagem de Divisores.