Apostila completa de Análise Combinatória

01

CAPÍTULO 1

Do ensaio aleatório à contagem sistemática

Contar não significa apenas produzir um número: é construir um procedimento que alcance todos os casos possíveis sem omissões nem repetições.

SÍNTESE DO CAPÍTULO

N=\sum_{\text{folhas}}1

Cada folha válida da árvore corresponde a um resultado.

Experimentos, listas e tabelas

Em situações pequenas, experimentar é uma ferramenta legítima. O avanço matemático ocorre quando os registros deixam de ser aleatórios e passam a seguir uma regra: ordem alfabética, escolha da primeira posição, tabela de dupla entrada ou código de símbolos.

Uma listagem é completa quando cada resultado possível aparece uma única vez. Para verificar isso, identifique uma característica que divida os resultados em grupos disjuntos e confira cada grupo separadamente.

Defina com precisão o que conta como resultado.
Escolha uma regra de geração dos casos.
Marque casos já usados para evitar duplicidade.
Justifique por que nenhum grupo ficou de fora.

Árvore de possibilidades

Uma árvore representa decisões sucessivas. Cada nível corresponde a uma etapa e cada ramo a uma escolha disponível naquele momento. Caminhos completos da raiz às folhas representam resultados.

A árvore é especialmente útil quando a quantidade de opções muda após uma escolha, como em códigos sem repetição ou caminhos que não permitem retornar imediatamente.

N=\sum_{\text{folhas}}1

Cada folha válida da árvore corresponde a um resultado.

D

VOCABULÁRIO

Definições essenciais

Espaço de possibilidades

Conjunto de todos os resultados admitidos pelas regras do problema.

Caso

Um resultado individual que satisfaz as condições estabelecidas.

Partição em casos

Divisão do conjunto de resultados em grupos disjuntos cuja união recupera todas as possibilidades.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Princípio da enumeração sistemática

Se um procedimento produz cada resultado válido exatamente uma vez, o número de passos finais do procedimento é o total procurado.

1

EXEMPLO RESOLVIDO

Trajes organizados

Uma pessoa dispõe de três camisetas, C1, C2 e C3, e duas calças, P1 e P2. Liste e conte os trajes.

Fixe C1 e combine com P1 e P2.
Repita o processo para C2 e C3.
Os pares são C1P1, C1P2, C2P1, C2P2, C3P1 e C3P2.

2

EXEMPLO RESOLVIDO

Sequências curtas sem repetição

Forme sequências de duas letras distintas usando A, B e C.

Escolha a primeira letra e abra um ramo para cada opção.
Em cada ramo, restam duas letras para a segunda posição.
Liste AB, AC, BA, BC, CA e CB.

Voltar ao início ↑

02

CAPÍTULO 2

Princípios aditivo e multiplicativo

Os dois princípios fundamentais condensam árvores e listas: somamos alternativas incompatíveis e multiplicamos escolhas feitas em etapas sucessivas.

SÍNTESE DO CAPÍTULO

|A\cup B|=|A|+|B|\quad\text{se }A\cap B=\varnothing

Soma para casos mutuamente exclusivos.

N=n_1n_2\cdots n_k

Total para k etapas com nᵢ escolhas em cada etapa.

Princípio aditivo

Se uma tarefa pode ser realizada por um procedimento A ou por um procedimento B e nenhum resultado pertence aos dois grupos, o total é a soma das quantidades. A condição de exclusividade é indispensável.

Quando os grupos se sobrepõem, somar diretamente conta a interseção duas vezes; esse problema será corrigido posteriormente pelo princípio da inclusão-exclusão.

|A\cup B|=|A|+|B|\quad\text{se }A\cap B=\varnothing

Soma para casos mutuamente exclusivos.

Princípio multiplicativo

Se uma construção tem etapas e cada escolha de uma etapa pode ser seguida pelas opções contadas na etapa seguinte, multiplicamos as quantidades ao longo do caminho.

Não é necessário que todas as etapas tenham o mesmo número de opções. Quando esse número depende do ramo anterior, calcule o produto em cada tipo de ramo e depois some os casos.

N=n_1n_2\cdots n_k

Total para k etapas com nᵢ escolhas em cada etapa.

D

VOCABULÁRIO

Definições essenciais

Etapa

Decisão parcial necessária para construir um resultado completo.

Casos mutuamente exclusivos

Casos que não podem ocorrer simultaneamente.

Regra do produto

Multiplicação das quantidades de escolhas sucessivas compatíveis.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Princípio Fundamental da Contagem

Se uma tarefa se decompõe em k etapas e a etapa i admite $n_{i}$ escolhas para cada realização anterior, então há $n_{1}$ $n_{2}$ ⋯nₖ resultados.

1

EXEMPLO RESOLVIDO

Identificador de acesso

Um identificador possui duas letras, escolhidas entre 26 com repetição, seguidas de três algarismos, escolhidos entre 10 com repetição. Quantos identificadores existem?

Há 26 escolhas para cada posição de letra.
Há 10 escolhas para cada posição numérica.
Multiplique 26·26·10·10·10.

2

EXEMPLO RESOLVIDO

Rotas alternativas

Uma cidade pode ser alcançada por 4 ônibus diretos ou por 3 voos diretos. Quantas opções diretas há?

A viagem escolhida é terrestre ou aérea.
Os dois grupos não se sobrepõem.
Aplique o princípio aditivo: 4+3.

Voltar ao início ↑

03

CAPÍTULO 3

Fatorial e permutações simples

Quando todos os objetos distintos são colocados em ordem, a diminuição sucessiva das escolhas produz o fatorial.

SÍNTESE DO CAPÍTULO

n!=n(n-1)(n-2)\cdots2\cdot1

Fatorial de um inteiro não negativo.

n!=n(n-1)!

Relação recursiva do fatorial.

P_n=n!

Número de permutações de n elementos distintos.

Fatorial como produto decrescente

Para ordenar n objetos distintos, há n escolhas para a primeira posição, n−1 para a segunda e assim por diante até uma escolha final. O produto é n!.

Define-se 0!=1 para preservar identidades e representar corretamente a única ordenação do conjunto vazio: não escolher objeto algum.

n!=n(n-1)(n-2)\cdots2\cdot1

Fatorial de um inteiro não negativo.

n!=n(n-1)!

Relação recursiva do fatorial.

Permutação linear

Uma permutação simples usa todos os n elementos distintos e considera diferentes duas disposições que diferem em alguma posição.

Restrições devem ser tratadas antes do cálculo: objetos juntos podem formar um bloco; posições proibidas podem ser contadas pelo complementar; uma posição fixa reduz o problema às demais posições.

P_n=n!

Número de permutações de n elementos distintos.

D

VOCABULÁRIO

Definições essenciais

Fatorial

Produto dos inteiros positivos de 1 até n, com 0!=1.

Permutação

Ordenação de todos os elementos disponíveis.

Bloco

Grupo de objetos temporariamente tratado como uma única unidade para atender a uma restrição de proximidade.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Contagem das ordenações

Um conjunto de n elementos distintos possui n! ordenações lineares.

1

EXEMPLO RESOLVIDO

Fila com posição fixa

Seis pessoas formam uma fila e Lara deve ocupar a primeira posição. Quantas filas são possíveis?

Fixe Lara no início.
Restam cinco pessoas distintas para cinco posições.
Calcule 5!.

2

EXEMPLO RESOLVIDO

Livros que permanecem juntos

Cinco livros distintos serão alinhados, e dois volumes de uma coleção devem ficar juntos. Quantas ordens são possíveis?

Trate os dois volumes como um bloco: ficam quatro unidades para ordenar.
As quatro unidades podem ser ordenadas de 4! maneiras.
Dentro do bloco, os dois volumes podem trocar de posição: multiplique por 2!.

Voltar ao início ↑

04

CAPÍTULO 4

Permutações com repetição e circulares

Quando objetos são indistinguíveis ou rotações representam a mesma configuração, é preciso remover contagens duplicadas.

SÍNTESE DO CAPÍTULO

P_n^{\alpha,\beta,\ldots}=\frac{n!}{\alpha!\,\beta!\cdots}

Permutação com grupos de elementos repetidos.

P_n^{\mathrm{circular}}=(n-1)!

Permutações circulares quando apenas rotações são equivalentes.

Elementos repetidos

Se n objetos incluem grupos de α, β, … objetos iguais, a permutação simples os trata como se fossem distinguíveis e conta a mesma palavra várias vezes.

Dividimos por α!, β!, … porque as trocas internas de objetos iguais não produzem uma nova disposição observável.

P_n^{\alpha,\beta,\ldots}=\frac{n!}{\alpha!\,\beta!\cdots}

Permutação com grupos de elementos repetidos.

Disposição circular

Em uma mesa redonda sem lugares numerados, girar todos os participantes não cria uma nova disposição. Fixar uma pessoa como referência elimina essa simetria de rotação.

Se reflexões também forem consideradas iguais, como em alguns colares, é necessário analisar ainda a simetria de espelhamento; a fórmula circular simples não basta automaticamente.

P_n^{\mathrm{circular}}=(n-1)!

Permutações circulares quando apenas rotações são equivalentes.

D

VOCABULÁRIO

Definições essenciais

Indistinguibilidade

Situação em que a troca de objetos iguais não altera o resultado.

Rotação equivalente

Disposição circular obtida apenas girando simultaneamente todos os elementos.

Simetria

Transformação que preserva a configuração considerada pelo problema.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Correção por simetria

Se cada configuração observável foi contada exatamente s vezes por um procedimento, dividir o total bruto por s produz a quantidade de configurações distintas.

1

EXEMPLO RESOLVIDO

Anagramas de BANANA

Quantos anagramas distintos podem ser formados com as letras de BANANA?

Há 6 letras no total.
A aparece 3 vezes e N aparece 2 vezes; B aparece uma vez.
Calcule 6!/(3!2!).

2

EXEMPLO RESOLVIDO

Reunião em mesa redonda

Sete pessoas sentam-se ao redor de uma mesa sem lugares marcados. Quantas disposições existem?

Escolha uma pessoa como referência fixa.
Ordene as seis restantes ao redor dela.
Calcule 6!.

Voltar ao início ↑

05

CAPÍTULO 5

Arranjos e seleções ordenadas

Quando apenas parte dos elementos é escolhida e cada posição tem função própria, trocar a ordem muda o resultado.

SÍNTESE DO CAPÍTULO

A_{n,p}=\frac{n!}{(n-p)!}

Arranjo simples de n elementos tomados p a p.

AR_{n,p}=n^p

Seleções ordenadas de comprimento p com repetição.

Arranjo simples

Um arranjo simples escolhe p elementos distintos entre n e os coloca em p posições ordenadas. Pelo princípio multiplicativo, as escolhas são n, n−1, …, n−p+1.

O mesmo modelo aparece em pódios, códigos sem repetição, cargos diferentes e sequências parciais.

A_{n,p}=\frac{n!}{(n-p)!}

Arranjo simples de n elementos tomados p a p.

Repetição permitida

Se cada uma das p posições pode receber qualquer um dos n símbolos e as repetições são permitidas, há n escolhas independentes em cada posição.

A diferença essencial é a reposição: sem reposição, as opções diminuem; com reposição, permanecem constantes.

AR_{n,p}=n^p

Seleções ordenadas de comprimento p com repetição.

D

VOCABULÁRIO

Definições essenciais

Arranjo simples

Escolha ordenada de p elementos distintos retirados de n disponíveis.

Reposição

Permissão para que um elemento volte a ficar disponível após ser escolhido.

Posições distintas

Lugares com funções ou ordens diferentes, como primeiro, segundo e terceiro.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Relação entre arranjo e combinação

Escolher p elementos sem ordem e depois ordená-los fornece Aₙ,ₚ=Cₙ,ₚ·p!.

1

EXEMPLO RESOLVIDO

Pódio de uma final

Entre 9 atletas, quantos pódios de ouro, prata e bronze são possíveis?

As três posições são diferentes.
Escolha 9 para o ouro, 8 para a prata e 7 para o bronze.
Multiplique 9·8·7.

2

EXEMPLO RESOLVIDO

PIN com repetição

Quantos códigos de quatro algarismos podem ser formados com 0 a 9, admitindo zero inicial e repetição?

Cada posição admite 10 algarismos.
As escolhas são independentes porque há repetição.
Calcule $10^{4}$ .

Voltar ao início ↑

06

CAPÍTULO 6

Combinações e coeficientes binomiais

Quando interessa apenas o grupo escolhido, e não a ordem de seus integrantes, contamos combinações.

SÍNTESE DO CAPÍTULO

\binom{n}{p}=\frac{n!}{p!(n-p)!}

Número de combinações de n elementos tomados p a p.

\binom{n}{p}=\binom{n}{n-p}

Simetria dos coeficientes binomiais.

\binom{n}{p}=\binom{n-1}{p}+\binom{n-1}{p-1}

Relação de Pascal.

Escolhas sem ordem

Cada grupo de p elementos é contado p! vezes por um arranjo, uma para cada ordenação interna. Dividir Aₙ,ₚ por p! produz o número de subconjuntos.

A pergunta prática é: trocar dois escolhidos de posição cria um resultado diferente? Se a resposta for não, a seleção é combinatória.

\binom{n}{p}=\frac{n!}{p!(n-p)!}

Número de combinações de n elementos tomados p a p.

Simetria e relação de Pascal

Escolher p elementos equivale a decidir quais n−p ficarão de fora, por isso $C(n,p)=C(n,n-p)$ .

Separando os grupos conforme contenham ou não um elemento específico, obtemos a relação de Pascal, base do triângulo de coeficientes binomiais.

\binom{n}{p}=\binom{n}{n-p}

Simetria dos coeficientes binomiais.

\binom{n}{p}=\binom{n-1}{p}+\binom{n-1}{p-1}

Relação de Pascal.

D

VOCABULÁRIO

Definições essenciais

Combinação

Subconjunto de tamanho p escolhido entre n elementos, sem considerar ordem.

Coeficiente binomial

Número $C(n,p)$ , que conta combinações e aparece na expansão de potências de binômios.

Complemento da escolha

Conjunto dos elementos não selecionados.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Relação de Pascal

Para $1\le p\le n-1, C(n,p)=C(n-1,p)+C(n-1,p-1)$ .

1

EXEMPLO RESOLVIDO

Equipe de projeto

Quantas equipes de 4 pessoas podem ser escolhidas entre 10 candidatos?

A ordem dos integrantes não altera a equipe.
Use $C(10{,}4)$ .
Calcule 10·9·8·7/(4·3·2·1).

2

EXEMPLO RESOLVIDO

Escolha com integrante obrigatório

Uma comissão de 5 será formada entre 12 pessoas, e Joana deve participar. Quantas comissões existem?

Fixe Joana como integrante.
Escolha as quatro vagas restantes entre as 11 pessoas.
Calcule $C(11{,}4)$ .

Voltar ao início ↑

07

CAPÍTULO 7

Restrições, blocos, lacunas e complementar

Problemas avançados diferem menos pelas fórmulas e mais pela forma de traduzir restrições antes de contar.

SÍNTESE DO CAPÍTULO

N(\text{válidos})=N(\text{universo})-N(\text{proibidos})

Estratégia do complementar.

\underbrace{\square\,X\,\square\,X\,\cdots\,X\,\square}_{m+1\text{ lacunas}}

m objetos ordenados criam m+1 lacunas.

Contagem pelo complementar

Expressões como pelo menos um, não todos e algum elemento especial frequentemente tornam o complementar mais simples. Conta-se o universo e subtraem-se os resultados proibidos.

O universo deve obedecer a todas as regras gerais do problema; o complementar altera apenas a condição que se quer impor.

N(\text{válidos})=N(\text{universo})-N(\text{proibidos})

Estratégia do complementar.

Método das lacunas

Para impedir que certos objetos fiquem juntos, ordene primeiro os objetos de outro tipo. Eles criam lacunas antes, entre e depois das posições ocupadas.

Escolher lacunas distintas impede adjacência. Se vários objetos puderem compartilhar uma lacuna, é preciso examinar a ordem interna e a possibilidade de repetição.

\underbrace{\square\,X\,\square\,X\,\cdots\,X\,\square}_{m+1\text{ lacunas}}

m objetos ordenados criam m+1 lacunas.

D

VOCABULÁRIO

Definições essenciais

Evento complementar

Conjunto de resultados do universo que não satisfazem a condição desejada.

Lacuna

Posição disponível antes, entre ou depois de objetos já organizados.

Restrição local

Regra que afeta posições vizinhas ou um subconjunto específico das escolhas.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Partição válido–proibido

Todo resultado do universo é válido ou proibido, nunca ambos; portanto $U=V\cup P$ com V∩P vazio.

1

EXEMPLO RESOLVIDO

Senha com ao menos um zero

Quantas sequências de 5 algarismos, com repetição e zero inicial permitido, possuem ao menos um zero?

O universo possui $10^{5}$ sequências.
Sem zero, cada posição admite 9 escolhas: $9^{5}$ .
Subtraia o complementar.

2

EXEMPLO RESOLVIDO

Vogais não adjacentes

Quantos anagramas de AMIGO têm as três vogais não adjacentes duas a duas?

Ordene as consoantes M e G: 2! maneiras.
Elas criam três lacunas: _M_G_.
Coloque A, I e O, uma em cada lacuna, em 3! ordens.

Voltar ao início ↑

08

CAPÍTULO 8

Inclusão-exclusão e contagens sobrepostas

Quando os casos não são mutuamente exclusivos, o princípio da inclusão-exclusão corrige as interseções contadas mais de uma vez.

SÍNTESE DO CAPÍTULO

|A\cup B|=|A|+|B|-|A\cap B|

Inclusão-exclusão para dois conjuntos.

|A\cup B\cup C|=\sum|A|-\sum|A\cap B|+|A\cap B\cap C|

Forma compacta para três conjuntos.

Dois e três conjuntos

Com três conjuntos, subtraímos as interseções duas a duas e depois devolvemos a interseção tripla, que foi removida em excesso.

|A\cup B|=|A|+|B|-|A\cap B|

Inclusão-exclusão para dois conjuntos.

|A\cup B\cup C|=\sum|A|-\sum|A\cap B|+|A\cap B\cap C|

Forma compacta para três conjuntos.

Divisibilidade e propriedades

A técnica é útil para contar inteiros divisíveis por vários números, estudantes que participam de atividades e objetos que possuem ao menos uma propriedade.

Sempre identifique claramente o universo e calcule interseções usando as condições simultâneas, como o mínimo múltiplo comum em problemas de divisibilidade.

Some os grupos individuais.
Subtraia as interseções de dois grupos.
Adicione interseções de três grupos.
Continue alternando os sinais se houver mais conjuntos.

D

VOCABULÁRIO

Definições essenciais

Interseção

Conjunto de resultados que satisfazem simultaneamente duas ou mais propriedades.

União

Conjunto de resultados que satisfazem ao menos uma das propriedades.

Sobrecontagem

Contagem de um mesmo resultado mais de uma vez.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Princípio da inclusão-exclusão

A cardinalidade de uma união é obtida alternando somas de conjuntos individuais e subtrações de suas interseções.

1

EXEMPLO RESOLVIDO

Clubes escolares

Em uma turma, 18 alunos participam do clube de xadrez, 14 do clube de ciências e 6 de ambos. Quantos participam de ao menos um?

Some 18+14.
Os 6 participantes de ambos foram contados duas vezes.
Subtraia a interseção.

2

EXEMPLO RESOLVIDO

Múltiplos em um intervalo

Quantos inteiros de 1 a 100 são divisíveis por 4 ou por 6?

Há $\left\lfloor \frac{100}{4} \right\rfloor=25$ múltiplos de 4.
Há $\left\lfloor \frac{100}{6} \right\rfloor=16$ múltiplos de 6.
A interseção reúne os múltiplos de $mmc(4{,}6)=12:$ são 8. Calcule 25+16−8.

Voltar ao início ↑

09

CAPÍTULO 9

Binômio de Newton e triângulo de Pascal

Os coeficientes binomiais registram quantas maneiras existem de escolher, em uma expansão, os fatores que fornecem determinada potência.

SÍNTESE DO CAPÍTULO

(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k

Binômio de Newton.

T_{k+1}=\binom{n}{k}a^{n-k}b^k

Termo de ordem k+1.

\sum_{k=0}^{n}\binom{n}{k}=2^n

Soma dos coeficientes da linha n.

Termo geral da expansão

Ao expandir (a+b)ⁿ, para produzir aⁿ⁻ᵏbᵏ escolhemos k dos n fatores para contribuir com b. Há $C(n,k)$ maneiras de fazer essa escolha.

O termo geral permite localizar coeficientes e termos independentes sem escrever toda a expansão.

(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k

Binômio de Newton.

T_{k+1}=\binom{n}{k}a^{n-k}b^k

Termo de ordem k+1.

Triângulo de Pascal e identidades

Cada linha do triângulo de Pascal reúne os coeficientes de uma potência do binômio. As bordas valem 1 e cada termo interno é a soma dos dois imediatamente acima.

A soma de uma linha é 2ⁿ porque, ao tomar $a=b=1 no$ binômio, obtemos (1+1)ⁿ.

\sum_{k=0}^{n}\binom{n}{k}=2^n

Soma dos coeficientes da linha n.

D

VOCABULÁRIO

Definições essenciais

Expansão binomial

Escrita de (a+b)ⁿ como soma de monômios.

Termo independente

Termo em que a variável aparece com expoente zero.

Linha de Pascal

Sequência $C(n,0)$ , $C(n,1)$ , …, $C(n,n)$ .

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Binômio de Newton

Para n inteiro não negativo, (a+b)ⁿ é a soma de $C(n,k)$ aⁿ⁻ᵏbᵏ para k de 0 a n.

1

EXEMPLO RESOLVIDO

Coeficiente específico

Determine o coeficiente de $x^{3}$ em $(2+x)^{5}$ .

Para obter $x^{3}$ , escolha $k=3$ .
O termo é $C(5{,}3)$ · $2^{2}$ · $x^{3}$ .
Calcule 10·4.

2

EXEMPLO RESOLVIDO

Termo independente

Encontre o termo independente de (x²+ $\frac{2}{x}$ )⁶.

O termo geral contém $(x^{2})^{6}$ ⁻ᵏ( $\frac{2}{x}$ )ᵏ, com potência $x^{12-3k}$ .
Exija $12-3k=0$ , então $k=4$ .
Calcule $C(6{,}4)$ · $2^{4}$ .

Voltar ao início ↑

10

CAPÍTULO 10

Distribuições, repetição e princípios avançados

Modelos de distribuição e recorrência mostram que uma mesma contagem pode ser resolvida por representações diferentes e comparada por identidades.

SÍNTESE DO CAPÍTULO

CR_{n,p}=\binom{n+p-1}{p}

Combinações de n tipos tomados p vezes com repetição.

x_1+\cdots+x_n=p,\ x_i\ge0\Rightarrow\binom{p+n-1}{n-1}

Soluções inteiras não negativas.

N>kn\Rightarrow\text{alguma caixa contém ao menos }k+1\text{ objetos}

Forma generalizada do princípio das gavetas.

Combinações com repetição

Distribuir p objetos idênticos entre n categorias equivale a escrever p estrelas separadas por n−1 barras. Cada arranjo das estrelas e barras determina uma solução inteira não negativa.

Se cada categoria deve receber ao menos uma unidade, entregue primeiro uma unidade a cada categoria e distribua apenas o restante.

CR_{n,p}=\binom{n+p-1}{p}

Combinações de n tipos tomados p vezes com repetição.

x_1+\cdots+x_n=p,\ x_i\ge0\Rightarrow\binom{p+n-1}{n-1}

Soluções inteiras não negativas.

Casa dos pombos e recorrências

Se mais de n objetos são distribuídos entre n caixas, ao menos uma caixa recebe dois ou mais objetos. Essa observação simples prova garantias sem enumerar todas as configurações.

Uma recorrência relaciona a contagem atual a casos menores. Separar pelo primeiro passo, pelo último símbolo ou pela presença de um elemento especial frequentemente produz uma relação recursiva.

N>kn\Rightarrow\text{alguma caixa contém ao menos }k+1\text{ objetos}

Forma generalizada do princípio das gavetas.

D

VOCABULÁRIO

Definições essenciais

Estrelas e barras

Representação de distribuições de objetos idênticos entre categorias distintas.

Princípio das gavetas

Garantia de colisão quando há mais objetos do que lugares disponíveis.

Recorrência

Relação que expressa uma contagem por valores de instâncias menores.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Princípio de Dirichlet

Ao distribuir N objetos entre n caixas, alguma caixa recebe pelo menos ⌈ $\frac{N}{n}$ ⌉ objetos.

1

EXEMPLO RESOLVIDO

Distribuição de fichas

De quantas maneiras 8 fichas idênticas podem ser distribuídas entre 3 caixas distintas, permitindo caixas vazias?

Modele $x_{1}+x_{2}+x_{3}=8$ com $x_{i}$ ≥0.
Use estrelas e barras: são 8 estrelas e 2 barras.
Escolha as posições das barras entre 10 símbolos.

2

EXEMPLO RESOLVIDO

Aniversários e garantia

Qual é o menor número de pessoas que garante que três nasceram no mesmo mês?

Há 12 meses, usados como caixas.
Com 24 pessoas, seria possível ter exatamente 2 em cada mês.
A pessoa seguinte força algum mês a ter pelo menos 3.

Voltar ao início ↑

11

CAPÍTULO 11

Caminhos em redes e recorrências

Rotas em malhas, decisões condicionadas e padrões que dependem de etapas anteriores podem ser contados por combinações ou por relações recorrentes.

SÍNTESE DO CAPÍTULO

N=\binom{d+s}{s}=\binom{d+s}{d}

Quantidade de caminhos mínimos sem bloqueios.

a_n=a_{n-1}+a_{n-2}

Recorrência típica de escolhas sem adjacência.

Caminhos mínimos em uma malha

Em uma malha retangular, um caminho mínimo que usa apenas movimentos para a direita e para cima é determinado pelas posições ocupadas por um dos tipos de movimento.

Se são necessários d movimentos à direita e s para cima, todo caminho tem d+s passos; escolher as posições dos s passos verticais determina o percurso completo.

N=\binom{d+s}{s}=\binom{d+s}{d}

Quantidade de caminhos mínimos sem bloqueios.

Recorrências e estados

Quando a escolha atual depende da anterior, separe os resultados pelo último passo ou por um pequeno conjunto de estados. A soma das contagens desses estados produz uma recorrência.

Para sequências binárias sem dois algarismos 1 consecutivos, uma sequência válida termina em 0 após qualquer sequência válida menor ou termina em 01 após uma sequência válida dois lugares menor.

a_n=a_{n-1}+a_{n-2}

Recorrência típica de escolhas sem adjacência.

D

VOCABULÁRIO

Definições essenciais

Caminho mínimo

Percurso que usa a menor quantidade possível de passos permitidos.

Estado

Informação mínima sobre a etapa atual necessária para decidir os próximos passos.

Condição inicial

Valores de partida que tornam uma recorrência capaz de gerar toda a sequência.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Contagem de caminhos retangulares

Uma malha que exige d passos horizontais e s verticais possui $C(d+s,s)$ caminhos mínimos quando não há bloqueios.

1

EXEMPLO RESOLVIDO

Entrega em uma malha urbana

Um entregador precisa avançar 5 quarteirões para leste e 3 para norte, sem recuar. Quantas rotas mínimas existem?

Toda rota mínima possui 8 movimentos.
Escolha as 3 posições dos movimentos para o norte.
Calcule $C(8{,}3)$ .

2

EXEMPLO RESOLVIDO

Agenda sem plantões consecutivos

Em quantas sequências de 5 dias uma pessoa pode marcar ou não um plantão, sem marcar dois dias consecutivos?

Separe sequências que terminam sem plantão das que terminam com plantão.
A contagem satisfaz aₙ=aₙ₋₁+aₙ₋₂.
Use $a_{1}=2$ e $a_{2}=3$ para obter 2,3,5,8,13.

Voltar ao início ↑

12

CAPÍTULO 12

Contagem aplicada à probabilidade

Quando os resultados são equiprováveis, técnicas combinatórias calculam probabilidades pela razão entre casos favoráveis e casos possíveis.

SÍNTESE DO CAPÍTULO

P(A)=\frac{n(A)}{n(\Omega)}

Probabilidade clássica em um espaço equiprovável.

P(A^c)=1-P(A)

Probabilidade pelo evento complementar.

P(X=k)=\frac{\binom{r}{k}\binom{n-r}{p-k}}{\binom{n}{p}}

Escolha de p objetos com exatamente k de um grupo de r.

Espaço amostral equiprovável

O primeiro passo é definir com precisão o resultado elementar. Em sorteios sem ordem, combinações evitam contar várias vezes o mesmo grupo; em sequências de retiradas, arranjos ou o princípio multiplicativo podem ser mais naturais.

A probabilidade clássica é uma razão de contagens e só pode ser aplicada diretamente quando os resultados elementares escolhidos possuem a mesma chance.

P(A)=\frac{n(A)}{n(\Omega)}

Probabilidade clássica em um espaço equiprovável.

Eventos com restrições

Conte o universo e o evento com o mesmo tipo de objeto. Se o universo usa comissões, o evento também deve usar comissões; misturar ordens e grupos produz razões incorretas.

Complementar, inclusão-exclusão e divisão em casos continuam válidos dentro do numerador e ajudam em expressões como ao menos um, nenhum ou exatamente k.

P(A^c)=1-P(A)

Probabilidade pelo evento complementar.

P(X=k)=\frac{\binom{r}{k}\binom{n-r}{p-k}}{\binom{n}{p}}

Escolha de p objetos com exatamente k de um grupo de r.

D

VOCABULÁRIO

Definições essenciais

Espaço amostral

Conjunto de todos os resultados elementares do experimento.

Evento

Subconjunto de resultados que satisfazem uma condição.

Equiprobabilidade

Condição em que todos os resultados elementares têm a mesma chance.

T

RESULTADOS CENTRAIS

Teoremas e propriedades

Probabilidade combinatória

Em um espaço finito equiprovável, a probabilidade de um evento é a razão entre suas contagens favorável e total.

1

EXEMPLO RESOLVIDO

Equipe sorteada

Uma equipe de 3 pessoas será sorteada entre 5 estudantes de um turno e 4 de outro. Qual é a probabilidade de sair exatamente 2 do primeiro turno?

Conte todas as equipes: $C(9{,}3)$ .
Conte as favoráveis: $C(5{,}2)$ $C(4{,}1)$ .
Divida 40 por 84 e simplifique.

2

EXEMPLO RESOLVIDO

Código com ao menos um zero

Um código de 4 algarismos é escolhido uniformemente entre 0000 e 9999. Qual é a probabilidade de conter ao menos um zero?

Há $10^{4}$ códigos no universo.
Sem zero, há $9^{4}$ códigos.
Use o complementar: ( $10^{4}$ $-9^{4}$ )/ $10^{4}$ .

Voltar ao início ↑

Experimentos, listas e tabelas

Árvore de possibilidades

Trajes organizados

Sequências curtas sem repetição

Princípio aditivo

Princípio multiplicativo

Identificador de acesso

Rotas alternativas

Fatorial como produto decrescente

Permutação linear

Fila com posição fixa

Livros que permanecem juntos

Elementos repetidos

Disposição circular

Anagramas de BANANA

Reunião em mesa redonda

Arranjo simples

Repetição permitida

Pódio de uma final

PIN com repetição

Escolhas sem ordem

Simetria e relação de Pascal

Equipe de projeto

Escolha com integrante obrigatório

Contagem pelo complementar

Método das lacunas

Senha com ao menos um zero

Vogais não adjacentes

Dois e três conjuntos

Divisibilidade e propriedades

Clubes escolares

Múltiplos em um intervalo

Termo geral da expansão

Triângulo de Pascal e identidades

Coeficiente específico

Termo independente

Combinações com repetição

Casa dos pombos e recorrências

Distribuição de fichas

Aniversários e garantia

Caminhos mínimos em uma malha

Recorrências e estados

Entrega em uma malha urbana

Agenda sem plantões consecutivos

Espaço amostral equiprovável

Eventos com restrições

Equipe sorteada

Código com ao menos um zero

O que observar ao estudar

Uma situação para resolver

Exercícios de Análise Combinatória