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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Quantos movimentos resolvem a Torre de Hanói? A resposta sai de uma relação de recorrência, que escreve o problema em função dele mesmo com um disco a menos. Montamos recorrências e as resolvemos por substituição, pela equação característica e pelo Teorema Mestre, usado no merge sort.
Somar o tamanho de dois conjuntos conta a interseção duas vezes. O Princípio da Inclusão-Exclusão corrige a conta, para dois, três ou qualquer número de conjuntos. Veremos também infinitos de tamanhos diferentes, desarranjos e o Crivo de Eratóstenes.
De quantas maneiras se escolhe uma senha válida? Qual o caminho mais curto entre duas cidades? São perguntas de matemática discreta. Este roteiro apresenta as quatro séries do site sobre o tema: conjuntos, indução e recorrência, combinatória e grafos, com 28 artigos.
