2º Ano: Aula — Análise Combinatória

📚 Resumo

A Análise Combinatória estuda métodos de contar agrupamentos de elementos de um conjunto, sem necessidade de listá-los um a um. A pergunta central sempre é: a ordem importa? e há repetição?

Princípio Fundamental da Contagem: $N = n_1 \times n_2 \times \cdots \times n_k$

Permutação simples: $P_n = n!$ | Arranjo: $A_{n,p} = \dfrac{n!}{(n-p)!}$ | Combinação: $C_{n,p} = \dfrac{n!}{p!\,(n-p)!}$

Diferença-chave: Arranjo = ordem importa. Combinação = ordem NÃO importa.

📖 1. Princípio Fundamental da Contagem (PFC)

Se uma tarefa pode ser realizada em $k$ etapas sucessivas e independentes, com $n_1$ escolhas na 1ª etapa, $n_2$ na 2ª, …, $n_k$ na $k$-ésima, então o número total de maneiras de realizar a tarefa é:

$$N = n_1 \times n_2 \times \cdots \times n_k$$

Exemplo 1 — Senhas: Quantas senhas de 3 dígitos distintos podem ser formadas com os algarismos $\{1, 2, 3, 4, 5\}$?
1ª posição: 5 escolhas → 2ª posição: 4 escolhas (sem repetir) → 3ª posição: 3 escolhas
$N = 5 \times 4 \times 3 = \mathbf{60}$

Exemplo 2 — Cardápio: Um restaurante oferece 3 entradas, 4 pratos e 2 sobremesas. Quantas refeições completas diferentes são possíveis?
$N = 3 \times 4 \times 2 = \mathbf{24}$

Exemplo 3 — Placas de veículos: Uma placa tem 3 letras (26 disponíveis) seguidas de 4 dígitos (0–9). Quantas placas são possíveis (com repetição)?
$N = 26^3 \times 10^4 = 17.576 \times 10.000 = \mathbf{175.760.000}$

Figura 1: Diagrama de árvore para senhas de 2 dígitos distintos com o conjunto $\{1, 2, 3\}$. Cada ramificação representa uma escolha. O total de ramos finais ($6 = 3 \times 2$) confirma o PFC.

⚠️ Atenção — Adição vs. Multiplicação: Use multiplicação quando as etapas são realizadas simultaneamente/em sequência (PFC). Use adição quando as opções são alternativas exclusivas. Exemplo: "um prato OU uma salada" → soma; "uma entrada E um prato" → multiplica.

📖 2. Fatorial

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1, \quad n \in \mathbb{N}$$

Convenção importante: $\mathbf{0! = 1}$ (por definição)

Relação de recorrência: $n! = n \cdot (n-1)!$

Tabela de fatoriais

$n$	$n!$	Frase mnemônica
$0$	$1$	Convenção
$1$	$1$	Um jeito
$2$	$2$	Dois jeitos
$3$	$6$	Seis arranjos de 3
$4$	$24$	Vinte e quatro
$5$	$120$	Cento e vinte
$6$	$720$	Setecentos e vinte
$7$	$5.040$	Cinco mil e quarenta
$10$	$3.628.800$	Mais de 3,6 milhões!

Simplificação de fatoriais:
$\dfrac{8!}{6!} = \dfrac{8 \times 7 \times \cancel{6!}}{\cancel{6!}} = 8 \times 7 = 56$

$\dfrac{10!}{7! \cdot 3!} = \dfrac{10 \times 9 \times 8 \times \cancel{7!}}{\cancel{7!} \times 6} = \dfrac{720}{6} = 120$

💡 Crescimento do fatorial: O fatorial cresce muito rápido. $20! \approx 2{,}4 \times 10^{18}$ — mais que o número de grãos de areia da Terra! Por isso, o fatorial aparece em problemas de contagem onde as quantidades parecem explodir rapidamente.

📖 3. Permutação Simples

A permutação simples conta o número de maneiras de ordenar todos os $n$ elementos distintos de um conjunto. A ordem importa e todos os elementos são usados.

$$P_n = n!$$

Número de maneiras de ordenar $n$ elementos distintos.

Figura 2: As 6 permutações do conjunto $\{A, B, C\}$. Cada bloco colorido ocupa uma posição diferente em cada linha. Todas as 6 sequências possíveis são mostradas — confirma $P_3 = 3! = 6$.

Exemplo 1: De quantas formas 5 amigos podem se sentar em fila?
$P_5 = 5! = 120$ formas.

Exemplo 2: Quantos anagramas tem a palavra AMOR?
São 4 letras distintas: $P_4 = 4! = 24$ anagramas.

Permutação com Repetição

Quando há elementos iguais, dividimos pelo fatorial de cada grupo de iguais:

$$P_n^{a,b,c,\ldots} = \frac{n!}{a!\; b!\; c!\; \cdots}$$

onde $a, b, c, \ldots$ são as quantidades de cada elemento repetido, com $a + b + c + \cdots = n$.

Exemplo: Quantos anagramas tem a palavra BANANA?
Letras: B(1), A(3), N(2) → total 6 letras
$P_6^{1,3,2} = \dfrac{6!}{1!\;3!\;2!} = \dfrac{720}{1 \times 6 \times 2} = \dfrac{720}{12} = \mathbf{60}$ anagramas

📖 4. Arranjo Simples

O arranjo simples conta o número de maneiras de escolher e ordenar $p$ elementos dentre $n$ distintos ($p \leq n$). A ordem importa e os elementos não se repetem.

$$A_{n,p} = \frac{n!}{(n-p)!} = n \cdot (n-1) \cdot (n-2) \cdots (n-p+1)$$

$n$ = total de elementos disponíveis | $p$ = quantidade a selecionar e ordenar

Relação com a permutação: Quando $p = n$, o arranjo coincide com a permutação:
$A_{n,n} = \dfrac{n!}{(n-n)!} = \dfrac{n!}{0!} = \dfrac{n!}{1} = n! = P_n$ ✓

Exemplo 1: De quantas maneiras podemos escolher e ordenar 3 livros dentre 7?
$A_{7,3} = \dfrac{7!}{(7-3)!} = \dfrac{7!}{4!} = 7 \times 6 \times 5 = \mathbf{210}$

Exemplo 2: Quantas senhas de 4 dígitos distintos podem ser formadas com os algarismos de 1 a 9?
$A_{9,4} = 9 \times 8 \times 7 \times 6 = \mathbf{3024}$

Exemplo 3: Em uma corrida com 10 atletas, de quantas formas pode-se distribuir ouro, prata e bronze?
$A_{10,3} = 10 \times 9 \times 8 = \mathbf{720}$

⚠️ Arranjo vs. Permutação: A permutação usa todos os $n$ elementos. O arranjo seleciona apenas $p$ deles ($p < n$) e os ordena. Se o problema pede para "escolher e ordenar" ou "distribuir posições diferentes" entre parte dos elementos, use arranjo.

📖 5. Combinação Simples

A combinação simples conta o número de maneiras de escolher $p$ elementos dentre $n$ distintos, sem se importar com a ordem. Um grupo de elementos = apenas uma combinação, independentemente de como são listados.

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

Lê-se: "$n$ escolhe $p$" ou "combinação de $n$, $p$ a $p$"

Relação Arranjo × Combinação

$A_{n,p} = C_{n,p} \times p!$ (o arranjo é a combinação multiplicada pelo número de ordenações possíveis dos $p$ elementos)

Isso faz sentido: para formar um arranjo, primeiro escolhemos os $p$ elementos ($C_{n,p}$ formas) e depois os ordenamos ($p!$ formas).

Exemplo 1: De quantas formas podemos escolher 3 representantes em uma turma de 20 alunos?
(Ordem não importa — representantes têm o mesmo papel)
$C_{20,3} = \dfrac{20!}{3!\;17!} = \dfrac{20 \times 19 \times 18}{3 \times 2 \times 1} = \dfrac{6840}{6} = \mathbf{1140}$

Exemplo 2: Quantos triângulos podem ser formados com 8 pontos não colineares?
(3 pontos determinam um triângulo, sem importar a ordem)
$C_{8,3} = \dfrac{8!}{3!\;5!} = \dfrac{8 \times 7 \times 6}{6} = \dfrac{336}{6} = \mathbf{56}$

Exemplo 3: Quantas diagonais tem um polígono de 10 lados?
Cada diagonal conecta 2 vértices não adjacentes. Total de segmentos: $C_{10,2} = 45$. Lados do polígono: 10.
Diagonais $= 45 - 10 = \mathbf{35}$

Propriedades da Combinação

P1 — Simetria: $C_{n,p} = C_{n,n-p}$ (escolher $p$ ou "deixar $n-p$ de fora" dá o mesmo resultado)
P2 — Extremos: $C_{n,0} = C_{n,n} = 1$
P3 — Relação de Pascal: $C_{n+1,p} = C_{n,p-1} + C_{n,p}$ (base do triângulo de Pascal)
P4 — Soma de uma linha de Pascal: $C_{n,0} + C_{n,1} + \cdots + C_{n,n} = 2^n$

📖 6. Triângulo de Pascal e Binômio de Newton

O Triângulo de Pascal organiza os coeficientes binomiais $C_{n,p}$ de forma que cada número é a soma dos dois imediatamente acima:

Figura 3: Triângulo de Pascal. Cada círculo contém $C_{n,p}$, onde $n$ é a linha e $p$ a posição (começando em 0). A propriedade de Pascal: $C_{n,p} = C_{n-1,p-1} + C_{n-1,p}$. A soma de cada linha é $2^n$.

Binômio de Newton

$$(a + b)^n = \sum_{p=0}^{n} C_{n,p}\; a^{n-p}\; b^p = C_{n,0}a^n + C_{n,1}a^{n-1}b + \cdots + C_{n,n}b^n$$

Os coeficientes são exatamente os números do Triângulo de Pascal!

Exemplo: Expanda $(x + 2)^4$.
Usando a linha $n=4$ do triângulo: $1, 4, 6, 4, 1$
$(x+2)^4 = x^4 + 4x^3\cdot2 + 6x^2\cdot4 + 4x\cdot8 + 16$
$= \mathbf{x^4 + 8x^3 + 24x^2 + 32x + 16}$

📖 7. Quando usar Cada Contagem?

A dúvida mais comum é escolher entre permutação, arranjo e combinação. O quadro abaixo resume a decisão:

📋 Permutação Simples $P_n = n!$

Quando: ordenar todos os $n$ elementos distintos.
Ordem importa · Usa todos os elementos
Exemplos: anagramas, fila, ordenar livros na prateleira.

🔢 Arranjo $A_{n,p} = \dfrac{n!}{(n-p)!}$

Quando: escolher e ordenar $p$ de $n$ distintos.
Ordem importa · Usa apenas $p$ dos $n$
Exemplos: pódio, presidente+vice, senhas sem repetição.

🤝 Combinação $C_{n,p} = \dfrac{n!}{p!(n-p)!}$

Quando: escolher $p$ de $n$ sem importar a ordem.
Ordem NÃO importa · Usa apenas $p$ dos $n$
Exemplos: comissão, mão de cartas, selecionar time.

✖️ Permutação c/ Repetição $\dfrac{n!}{a!\,b!\,\ldots}$

Quando: ordenar $n$ elementos com repetições.
Ordem importa · Há elementos iguais
Exemplos: anagramas de palavras com letras repetidas.

Tabela-resumo comparativa

Tipo	Fórmula	Ordem importa?	Usa todos?	Palavra-chave
Permutação simples	$n!$	✓ Sim	✓ Sim	ordenar, anagrama, fila
Perm. c/ repetição	$\dfrac{n!}{a!\,b!\,\ldots}$	✓ Sim	✓ Sim	letras repetidas, cores iguais
Arranjo	$\dfrac{n!}{(n-p)!}$	✓ Sim	✗ Não	pódio, presidente/vice, senha
Combinação	$\dfrac{n!}{p!(n-p)!}$	✗ Não	✗ Não	comissão, grupo, selecionar

💡 Teste rápido: Troque dois elementos de posição no grupo. Se o resultado é diferente, a ordem importa → use arranjo. Se o resultado é o mesmo grupo, a ordem não importa → use combinação.

📖 8. Problemas com Restrições

Muitos problemas de combinatória têm condições adicionais (restrições). A estratégia geral é:

Estratégia 1 — Contar o favorável diretamente: aplique as restrições de cada etapa, modificando o número de opções em cada passo do PFC.

Estratégia 2 — Complemento: Total − (casos que violam a restrição). Útil quando "pelo menos" ou "ao menos um" aparecem.

Estratégia 3 — Fixar elementos: se um elemento deve estar num lugar específico, fixe-o e conte as permutações dos restantes.

Exemplo 1 — Restrição direta: Quantas senhas de 4 dígitos (0–9) começam com 5 e têm todos os dígitos distintos?
1ª posição: fixada em 5 (1 jeito)
2ª posição: 9 opções (0–9, exceto 5)
3ª posição: 8 opções; 4ª: 7 opções
$N = 1 \times 9 \times 8 \times 7 = \mathbf{504}$

Exemplo 2 — Complemento ("pelo menos"): Numa comissão de 5 membros escolhida de 8 pessoas (4 homens e 4 mulheres), quantas têm pelo menos uma mulher?
Total: $C_{8,5} = 56$
Sem mulher (só homens): $C_{4,5} = 0$ (impossível, pois há só 4 homens)
Com pelo menos 1 mulher $= 56 - 0 = \mathbf{56}$

Ajuste do enunciado: Se fossem 6 homens e 4 mulheres: Total $C_{10,5}=252$; só homens $C_{6,5}=6$; pelo menos 1 mulher $= 252-6=246$.

Exemplo 3 — Elemento fixo: De quantas formas 6 pessoas podem se sentar em fila se A e B devem ficar juntos?
Trate o par (A,B) como um bloco → 5 elementos para permutar: $P_5 = 120$
Internamente, A e B podem trocar de posição: $P_2 = 2$
$N = 120 \times 2 = \mathbf{240}$

💡 Matemática em Ação

🔐 Criptografia e Senhas

A segurança de senhas depende diretamente de análise combinatória. Uma senha de 8 caracteres com letras minúsculas e números tem $36^8 \approx 2{,}8 \times 10^{12}$ possibilidades — impossível de testar em tempo razoável por força bruta.

🃏 Jogos e Probabilidade

Em um baralho de 52 cartas, o número de mãos de pôquer (5 cartas) é $C_{52,5} = 2.598.960$. A análise combinatória determina as probabilidades de cada mão, base para a estratégia do jogo.

🧬 Genética e Bioinformática

O DNA é formado por 4 bases (A, T, C, G). Um gene de 1000 bases tem $4^{1000}$ sequências possíveis — número astronomicamente grande. Algoritmos de bioinformática usam combinatória para analisar apenas as sequências biologicamente relevantes.

📡 Redes e Computação

O número de rotas possíveis em uma rede de computadores, o número de subconjuntos de servidores para backup e a otimização de caminhos são problemas resolvidos com arranjos e combinações em grafos.

✅ 5 Questões Resolvidas (R 1 a 5)

R 1: Princípio Fundamental da Contagem

Enunciado: Uma loja de uniformes tem 4 modelos de camisa, 3 modelos de calça e 2 tipos de tênis. De quantas formas diferentes um cliente pode montar um uniforme completo? E se ele quiser apenas camisa e tênis (sem calça)?

Resolução:
Uniforme completo (camisa + calça + tênis):
$N = 4 \times 3 \times 2 = \mathbf{24}$ combinações

Apenas camisa + tênis:
$N = 4 \times 2 = \mathbf{8}$ combinações

(Nesse segundo caso, a etapa "calça" é eliminada — não multiplicamos por ela.)

R 2: Anagrama com e sem repetição

Enunciado: Quantos anagramas têm as palavras: (a) CAMPO; (b) BRASIL; (c) TATAME?

Resolução:
(a) CAMPO: 5 letras distintas → $P_5 = 5! = \mathbf{120}$

(b) BRASIL: 6 letras distintas → $P_6 = 6! = \mathbf{720}$

(c) TATAME: 6 letras, com T(2) e A(2):
$P_6^{2,2} = \dfrac{6!}{2!\;2!} = \dfrac{720}{4} = \mathbf{180}$

R 3: Arranjo — distribuição de vagas

Enunciado: Uma empresa tem 12 candidatos para 4 vagas distintas (gerente, supervisor, analista e assistente). De quantas formas as vagas podem ser preenchidas?

Resolução:
As 4 vagas são distintas → a ordem importa → arranjo.
$A_{12,4} = \dfrac{12!}{(12-4)!} = \dfrac{12!}{8!} = 12 \times 11 \times 10 \times 9 = \mathbf{11.880}$ formas

R 4: Combinação — formação de comissão

Enunciado: De um grupo de 6 professores e 4 alunos, quantas comissões de 5 membros podem ser formadas com exatamente 3 professores e 2 alunos?

Resolução:
Escolha dos 3 professores (de 6): $C_{6,3} = \dfrac{6!}{3!\;3!} = 20$
Escolha dos 2 alunos (de 4): $C_{4,2} = \dfrac{4!}{2!\;2!} = 6$
Total: $20 \times 6 = \mathbf{120}$ comissões
(Multiplicamos porque escolhemos professores E alunos — etapas independentes)

R 5: Complemento — "pelo menos"

Enunciado: Uma urna tem 5 bolas vermelhas e 4 azuis. Sorteando 3 bolas, de quantas formas há pelo menos 1 bola azul?

Resolução: Usando o complemento:
Total de formas de sortear 3 bolas: $C_{9,3} = \dfrac{9!}{3!\;6!} = 84$
Sem nenhuma azul (só vermelhas): $C_{5,3} = \dfrac{5!}{3!\;2!} = 10$
Com pelo menos 1 azul $= 84 - 10 = \mathbf{74}$

✍️ 5 Questões Propostas (P 6 a 10)

P 6: PFC com restrição

Enunciado: Quantas senhas de 5 dígitos distintos, formadas com os algarismos de 1 a 7, começam com número ímpar?

Resolução:
Ímpares disponíveis: $\{1, 3, 5, 7\}$ → 4 opções para o 1º dígito
2ª posição: 6 opções restantes; 3ª: 5; 4ª: 4; 5ª: 3
$N = 4 \times 6 \times 5 \times 4 \times 3 = \mathbf{1440}$

P 7: Permutação com repetição

Enunciado: Quantos anagramas tem a palavra MISSISSIPPI?

Resolução:
Letras: M(1), I(4), S(4), P(2) → total 11 letras
$P_{11}^{1,4,4,2} = \dfrac{11!}{1!\;4!\;4!\;2!} = \dfrac{39.916.800}{1 \times 24 \times 24 \times 2} = \dfrac{39.916.800}{1152} = \mathbf{34.650}$

P 8: Combinação com propriedade

Enunciado: Calcule: (a) $C_{10,3}$ (b) $C_{10,7}$ e explique por que os resultados são iguais. (c) $C_{15,1} + C_{15,14}$

Resolução:
(a) $C_{10,3} = \dfrac{10!}{3!\;7!} = \dfrac{10\times9\times8}{6} = \mathbf{120}$

(b) $C_{10,7} = C_{10,10-7} = C_{10,3} = \mathbf{120}$ — iguais pela simetria $C_{n,p}=C_{n,n-p}$: escolher 7 para incluir é equivalente a escolher 3 para excluir.

(c) $C_{15,1} = 15$ e $C_{15,14} = C_{15,1} = 15$; soma $= \mathbf{30}$

P 9: Arranjo vs. Combinação

Enunciado: De 10 atletas, precisamos escolher: (a) os três primeiros colocados (ouro, prata, bronze); (b) uma equipe de 3 atletas para representar o país. Calcule cada caso e explique a diferença.

Resolução:
(a) Pódio: ordem importa (ouro ≠ prata ≠ bronze) → Arranjo
$A_{10,3} = 10 \times 9 \times 8 = \mathbf{720}$

(b) Equipe: ordem não importa (os 3 têm o mesmo papel) → Combinação
$C_{10,3} = \dfrac{720}{3!} = \dfrac{720}{6} = \mathbf{120}$

Diferença: $A_{10,3} = C_{10,3} \times 3! = 120 \times 6 = 720$. O arranjo é sempre maior pois conta também as ordenações internas.

P 10: Polígonos e diagonais

Enunciado: Um polígono convexo tem 35 diagonais. Quantos lados ele possui?

Resolução:
Número de diagonais de um polígono de $n$ lados: $D = C_{n,2} - n = \dfrac{n(n-1)}{2} - n$
$35 = \dfrac{n(n-1)}{2} - n \Rightarrow 70 = n(n-1) - 2n = n^2 - 3n$
$n^2 - 3n - 70 = 0 \Rightarrow (n-10)(n+7) = 0 \Rightarrow n = 10$ (positivo)
O polígono tem 10 lados (decágono).
Verificação: $C_{10,2} - 10 = 45 - 10 = 35$ ✓

🎓 5 Questões de Vestibular (T 11 a 15)

T 11: (FUVEST) Anagramas com restrição

Enunciado: Quantos anagramas da palavra FUVEST começam com vogal?

A) 120
B) 240
C) 360
D) 480
E) 720

Resposta: B
FUVEST tem 6 letras distintas: F, U, V, E, S, T. Vogais: U, E → 2 opções para a 1ª posição.
Restam 5 letras para as 5 posições seguintes: $5! = 120$
Total: $2 \times 120 = \mathbf{240}$

T 12: (ENEM) Combinação em contexto

Enunciado: Uma turma de 8 alunos precisa formar um grupo de 3 para apresentar um trabalho. Quantos grupos diferentes podem ser formados?

A) 24
B) 56
C) 112
D) 168
E) 336

Resposta: B
Grupo = sem importar ordem → Combinação
$C_{8,3} = \dfrac{8!}{3!\;5!} = \dfrac{8 \times 7 \times 6}{6} = \dfrac{336}{6} = \mathbf{56}$

T 13: (UNICAMP) PFC com etapas

Enunciado: Uma senha de 4 caracteres usa apenas letras ($A$–$Z$) e dígitos ($0$–$9$), com pelo menos um dígito. Quantas senhas são possíveis (com repetição)?

A) $36^4 - 26^4$
B) $36^4 - 10^4$
C) $26^4 \times 10$
D) $4 \times 26^3 \times 10$
E) $36^4$

Resposta: A
Total de senhas (sem restrição): $36^4$ (36 caracteres, 4 posições com repetição)
Senhas sem nenhum dígito (só letras): $26^4$
Com pelo menos 1 dígito $= 36^4 - 26^4$

T 14: (Mackenzie) Arranjo com restrição

Enunciado: De quantas maneiras 5 pessoas podem se sentar em uma fila se duas delas, A e B, não podem ficar lado a lado?

A) 48
B) 60
C) 72
D) 96
E) 120

Resposta: C
Total sem restrição: $5! = 120$
Casos em que A e B ficam juntos: bloco (A,B) → $4!$ formas de posicionar o bloco × $2!$ para ordenar A e B internamente $= 24 \times 2 = 48$
A e B NÃO lado a lado $= 120 - 48 = \mathbf{72}$

T 15: (UFMG) Combinação com condição

Enunciado: Em uma sala há 5 homens e 4 mulheres. De quantas formas pode-se escolher uma comissão de 4 pessoas com exatamente 2 mulheres?

A) 30
B) 40
C) 50
D) 60
E) 80

Resposta: D
Escolha de 2 mulheres (de 4): $C_{4,2} = 6$
Escolha de 2 homens (de 5): $C_{5,2} = 10$
Total: $6 \times 10 = \mathbf{60}$