Uma jornada pela Combinatória: dos Princípios Aditivo e Multiplicativo ao Binômio
de Newton, passando por permutações, arranjos e combinações — com e sem repetição.
O roteiro completo para dominar a arte de contar possibilidades.
Os artigos são listados abaixo, na ordem em que foram escritos.
Quantas senhas de 8 caracteres existem? De quantas formas 10 pessoas se sentam ao redor de uma mesa? A combinatória responde sem enumerar caso a caso. Este é o roteiro da série: dos princípios de contagem a permutações, arranjos, combinações e Binômio de Newton.
Com 4 livros de matemática e 3 de português, há 7 formas de escolher um livro e 12 de escolher um de cada. A primeira conta é uma soma e a segunda, um produto: são os princípios aditivo e multiplicativo, aplicados aqui a senhas, bandeiras, gabaritos e contagem de divisores.
Quantos anagramas tem a palavra VIRUS? De quantas formas 5 amigos se sentam em volta de uma mesa? São 120 e 24, pela permutação simples e pela circular. Veremos também restrições de adjacência, o problema do caixeiro-viajante e os desarranjos.
Numa corrida com 10 atletas, o pódio pode ser preenchido de 720 formas. Esse é um arranjo simples, a seleção ordenada de alguns elementos de um conjunto. Resolvemos problemas de rotas, placas de veículos e números com algarismos distintos, com Python e SQL.
De 10 amigos, 3 vão comprar as pipocas. Importa só quem vai, e não a ordem da escolha, e por isso são 120 grupos possíveis. Veremos a fórmula da combinação simples, sua simetria, o método do complemento e a divisão de um conjunto em grupos.
Quantos anagramas tem a palavra MAMBEMBE? Menos do que teria uma palavra de 8 letras distintas, porque trocar duas letras iguais não cria um anagrama novo. A fórmula desconta as repetições dividindo por fatoriais, e vale para sequências binárias e para caminhos mínimos em grades.
Uma senha de 4 dígitos aceita repetição, e por isso há 10.000 delas, dez opções em cada uma das quatro posições. O arranjo com repetição conta senhas, placas e cores RGB, e mostra quantos padrões cabem nos 32 bits de um float e nos registradores de uma calculadora HP-11C.
Numa sorveteria com 7 sabores, há 210 formas de pedir 4 bolas, podendo repetir sabor. Chegamos a esse número com o método das estrelas e barras, que mostra que escolher com repetição, distribuir bolas em caixas e resolver equações inteiras são o mesmo problema.
Um conjunto de 10 elementos tem 1.024 subconjuntos, e essa é a soma da linha 10 do Triângulo de Pascal. Veremos as identidades dos coeficientes binomiais: simetria, relação de Pascal (Stifel) e os teoremas das linhas, das colunas e das diagonais.
Qual é o coeficiente de um termo na expansão de um binômio elevado à décima potência? O Binômio de Newton responde em uma linha, com os coeficientes do Triângulo de Pascal. Veremos o teorema e sua prova por indução, a fórmula do termo geral e as identidades que saem de casos particulares.
