Estratégia geral
Uma questão avançada de combinatória geralmente não pede uma fórmula nova. Ela muda a forma de organizar a contagem. O segredo é reconhecer qual obstáculo está no caminho.
| Obstáculo | Como pensar | Técnica comum |
|---|---|---|
| elementos precisam ficar juntos | transforme o grupo em um bloco | blocos |
| elementos não podem ficar juntos | organize os outros e use os espaços | método dos espaços |
| há casos proibidos | conte tudo e retire o que não serve | complemento |
| casos se sobrepõem | corrija a contagem duplicada | inclusão-exclusão |
| o problema pede garantia | distribua objetos em caixas | princípio das gavetas |
Restrições clássicas
Restrições são condições que mudam a contagem. Em vez de tentar jogar fórmula direto, primeiro decida se a condição aproxima, separa, proíbe ou fixa elementos.
Elementos juntos: método do bloco
Quando dois ou mais elementos precisam ficar juntos, trate esse grupo como um único bloco. Depois, não esqueça de organizar os elementos dentro do bloco.
Elementos separados: método dos espaços
Quando certos elementos não podem ficar juntos, organize primeiro os outros elementos. Depois coloque os elementos restritos nos espaços livres.
Contar pelo complemento
Use complemento quando a condição direta é trabalhosa, mas o contrário dela é fácil. Expressões como “pelo menos um”, “não todos”, “nenhum” e “não pode” costumam acender esse alerta.
Princípio da inclusão-exclusão
Quando conjuntos se sobrepõem, somar diretamente conta a interseção mais de uma vez. Inclusão-exclusão corrige essa duplicação.
- 2 conjuntos n(A ∪ B)=n(A)+n(B)-n(A ∩ B)
- 3 conjuntos n(A ∪ B ∪ C)=n(A)+n(B)+n(C)-n(A∩B)-n(A∩C)-n(B∩C)+n(A∩B∩C)
Distribuição de objetos
Muitos problemas de combinatória perguntam como distribuir objetos em caixas, pessoas em grupos, bolas em urnas ou soluções inteiras de uma equação. A técnica depende de duas perguntas: os objetos são distinguíveis? As caixas são distinguíveis?
| Tipo | Exemplo | Ideia comum |
|---|---|---|
| objetos distintos em caixas distintas | 3 livros diferentes em 2 prateleiras | cada objeto escolhe uma caixa |
| objetos iguais em caixas distintas | 10 balas iguais para 3 crianças | combinação completa |
| caixas com mínimo obrigatório | cada criança recebe ao menos 1 bala | reserve o mínimo e distribua o resto |
Princípio das gavetas
O princípio das gavetas serve para provar que algo necessariamente acontece. Ele não conta quantas formas existem; ele garante uma conclusão mínima.
- Clássica se n objetos vão para k gavetas e n > k, alguma gaveta recebe pelo menos 2 objetos.
- Forte alguma gaveta recebe pelo menos ⌈n/k⌉ objetos.
Desarranjos
Desarranjo é uma permutação em que nenhum elemento fica na posição original. Aparece em cartas nos envelopes errados, presentes trocados e lugares proibidos para todos.
Recorrências em contagem
Quando a escolha atual cria um problema menor do mesmo tipo, uma recorrência pode ser mais limpa que uma fórmula fechada. Isso acontece em sequências, pavimentações e problemas com vizinhança proibida.
| Problema | Recorrência comum | Ideia |
|---|---|---|
| sequências binárias sem dois 1 juntos | an=an-1+an-2 | começa com 0 ou com 10 |
| pavimentar faixa com peças 1 e 2 | an=an-1+an-2 | última peça tem tamanho 1 ou 2 |
| problema com casos proibidos | total - proibidos | transforma restrição em complemento |
Como decidir a técnica
| Pergunta | Se sim | Se não |
|---|---|---|
| Há elementos que devem ficar juntos? | use bloco | passe para a próxima pergunta |
| Há elementos que devem ficar separados? | organize os demais e use espaços | conte direto |
| A frase tem “pelo menos um”? | pense em complemento | conte por casos |
| Os casos se sobrepõem? | use inclusão-exclusão | some os casos diretamente |
| São objetos iguais distribuídos em caixas? | pense em combinação completa | use produto, arranjo ou casos |
| O problema pede uma garantia mínima? | use gavetas | provavelmente é contagem normal |
| Ninguém pode ficar no lugar original? | use desarranjo | use permutação com restrições |