Bancada de combinatória

A parte difícil da combinatória raramente é a aritmética — é classificar corretamente o problema. Duas perguntas de sim/não fazem quase todo o trabalho: a ordem importa (organizar vs. escolher) e o mesmo item pode ser escolhido mais de uma vez (com ou sem repetição)? Essas duas respostas por si só classificam todo problema em um dos quatro modelos básicos — permutações, combinações, permutações com repetição e combinações com repetição ('estrelas e barras') — por isso um comitê, uma escalação, um código PIN e um bilhete de loteria precisam cada um de uma fórmula diferente, apesar de parecerem superficialmente semelhantes. A inclusão-exclusão e os desarranjos existem precisamente porque problemas reais costumam quebrar as suposições limpas desses quatro modelos, com conjuntos que se sobrepõem ou correspondências exatas proibidas de formas que as fórmulas básicas não conseguem tratar sozinhas.

O objetivo da combinatória é descobrir quantas disposições existem sem escrevê-las todas. Um PIN de 4 dígitos tem apenas 10⁴ = 10,000 possibilidades que ainda dá para imaginar como lista, mas um bilhete de loteria de 6 entre 49 tem C(49,6) = 13,983,816 — ninguém as conta à mão. As fórmulas aqui devolvem o total exato num único passo, transformando uma enumeração impossível num cálculo curto. Por isso a ferramenta mostra sempre a contagem, o seu número de dígitos e uma notação científica para os valores realmente enormes.

O modelo de desarranjo conta as disposições em que nada fica no seu próprio lugar — o caso do amigo secreto em que ninguém tira o próprio nome. Surpreendentemente, a fração de todas as permutações que são desarranjos converge quase de imediato para 1/e ≈ 0.3679: já com 6 pessoas está correta até três casas decimais. Assim, a probabilidade de um amigo secreto aleatório deixar todos sem o próprio nome é cerca de 37% e quase não muda se o grupo tiver 6 ou 600 membros. A constante e, nascida do cálculo e dos juros compostos, surge diretamente de um problema puramente combinatório.