Combinação e sua fórmula
A questão básica de combinação: o número de diferentes grupos de \(r\) objetos que podem ser formados a partir de um total de \(n\) objetos.
$$\binom{n}{r} = \frac{n!}{(n-r)! \times r!}$$Lê-se “\(n\) sobre \(r\)”, também “\(n\) escolhe \(r\)”.
Passo 1. Quando a ordem é relevante, o número de grupos de \(r\) objetos formados a partir de \(n\) é
$$n \times (n-1) \times (n-2) \times \dots \times (n-r+1)$$São \(r\) casas: a primeira com \(n\) escolhas, a segunda com \(n-1\), até a \(r\)-ésima com \(n-r+1\).
Passo 2. Quando a ordem não é relevante, cada grupo de \(r\) objetos pode ser formado de \(r!\) jeitos diferentes — todos contados como um só.
Passo 3. Portanto o número de grupos distintos é
$$\frac{n \times (n-1) \times \dots \times (n-r+1)}{r!}$$ $$= \frac{n \times (n-1) \times \dots \times (n-r+1) \times (n-r) \times (n-r-1) \times \dots \times 1}{r! \times (n-r) \times (n-r-1) \times \dots \times 1}$$ $$= \frac{n!}{(n-r)! \times r!} = \binom{n}{r}$$O truque da passagem é multiplicar em cima e embaixo pelo que falta para completar \(n!\).
Escolher um grupo
Um comitê de 3 deve ser formado por um grupo de 20 pessoas. Quantos comitês diferentes são possíveis?
$$\binom{20}{3} = \frac{20!}{3! \times 17!} = 1\,140$$Escolher de dois grupos ao mesmo tempo
Quantas comissões diferentes compostas por 2 mulheres e 3 homens podem ser formadas, de um grupo de 5 mulheres e 7 homens?
$$\binom{5}{2} \times \binom{7}{3} = \frac{5!}{2! \times 3!} \times \frac{7!}{3! \times 4!} = 10 \times 35 = 350$$São duas escolhas independentes, ligadas pelo princípio multiplicativo da A1: escolho as mulheres e escolho os homens.
Antenas: contar os espaços, não os objetos
Considere um conjunto de \(n\) antenas, das quais \(m\) estão com defeito e \(n-m\) são funcionais. Quantas ordens lineares existem nas quais não existem duas antenas defeituosas consecutivas?
$$\binom{n-m+1}{m}$$Alinhe as \(n-m\) antenas funcionais. Insira, no máximo, uma antena com defeito entre duas antenas funcionais — é isso que impede duas defeituosas seguidas.
Considerando também os limites, à esquerda da primeira e à direita da última, há no total \(n-m+1\) locais para inserir antenas com defeito. Escolher \(m\) desses locais é
$$\binom{n-m+1}{m}$$Propriedades do coeficiente binomial
1. \(\binom{n}{0} = 1\) e \(\binom{n}{n} = 1\). Observe que \(0! = 1\).
2. Simetria:
$$\binom{n}{r} = \binom{n}{n-r}$$3. Relação de Pascal:
$$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$e \(r + n - r = n\), o que reconstrói \(n!\) no numerador.
Uma seleção de \(r\) objetos contém o objeto 1 ou não contém o objeto 1.
- Se contém: falta escolher \(r-1\) objetos entre os \(n-1\) restantes \(\Rightarrow \binom{n-1}{r-1}\);
- se não contém: escolhem-se os \(r\) entre os \(n-1\) restantes \(\Rightarrow \binom{n-1}{r}\).
Os dois casos são exclusivos e cobrem tudo — princípio aditivo.
Truques computacionais
1. Evite o fatorial \(n!\), que fica grande depressa: \(170! = 7{,}2574 \times 10^{306}\).
2. Tire proveito de \(\binom{n}{r} = \binom{n}{n-r}\) — calcule sempre pelo lado menor.
3. Converta produtos em adições:
$$\binom{n}{r} = \frac{n(n-1)(n-2)\dots(n-r+1)}{r!} = \exp\left\{\sum_{j=0}^{r-1}\log(n-j) - \sum_{j=1}^{r}\log j\right\}$$Binômio de Newton
Primeiro para \(n=1\), e depois: se vale para \(n-1\), provamos para \(n\).
Base, \(n=1\):
$$\sum_{k=0}^{1}\binom{1}{k}x^k y^{1-k} = \binom{1}{0}x^0y^{1-0} + \binom{1}{1}x^1y^{1-1} = y + x$$Hipótese, vale para \(n-1\):
$$(x+y)^{n-1} = \sum_{k=0}^{n-1}\binom{n-1}{k}x^k y^{n-1-k}$$Passo indutivo: separa-se os extremos, aplica-se Pascal e reagrupa-se.
$$\sum_{k=0}^{n}\binom{n}{k}x^ky^{n-k} = \sum_{k=1}^{n-1}\binom{n}{k}x^ky^{n-k} + x^n + y^n$$ $$= \sum_{k=1}^{n-1}\binom{n-1}{k}x^ky^{n-k} + \sum_{k=1}^{n-1}\binom{n-1}{k-1}x^ky^{n-k} + x^n + y^n$$ $$= y\sum_{k=0}^{n-1}\binom{n-1}{k}x^ky^{n-1-k} - y^n + \sum_{k=1}^{n-1}\binom{n-1}{k-1}x^ky^{n-k} + x^n + y^n$$ $$= y(x+y)^{n-1} + \sum_{j=0}^{n-2}\binom{n-1}{j}x^{j+1}y^{n-1-j} + x^n \qquad (\text{seja } j = k-1)$$ $$= y(x+y)^{n-1} + x\sum_{j=0}^{n-1}\binom{n-1}{j}x^{j}y^{n-1-j} - x^n + x^n$$ $$= y(x+y)^{n-1} + x(x+y)^{n-1} = (x+y)^n$$Coeficiente multinomial
Um conjunto de \(n\) itens distintos deve ser dividido em \(r\) grupos distintos de tamanhos \(n_1, n_2, \dots, n_r\), com \(\sum_{i=1}^{r} n_i = n\). Quantas divisões diferentes são possíveis?
$$\binom{n}{n_1, n_2, \dots, n_r} = \frac{n!}{n_1!\,n_2! \dots n_r!}$$Etapa 1: há \(\binom{n}{n_1}\) maneiras de formar o primeiro grupo, de tamanho \(n_1\).
Etapa 2: existem \(\binom{n-n_1}{n_2}\) maneiras de formar o segundo grupo, de tamanho \(n_2\).
Etapa \(r\): existem \(\binom{n-n_1-n_2-\dots-n_{r-1}}{n_r}\) maneiras de formar o último grupo.
Portanto o total é
$$\binom{n}{n_1}\times\binom{n-n_1}{n_2}\times\dots\times\binom{n-n_1-n_2-\dots-n_{r-1}}{n_r}$$ $$= \frac{n!}{(n-n_1)!\,n_1!}\times\frac{(n-n_1)!}{(n-n_1-n_2)!\,n_2!}\times\dots\times\frac{(n-n_1-\dots-n_{r-1})!}{(n-n_1-\dots-n_r)!\,n_r!}$$ $$= \frac{n!}{n_1!\,n_2!\dots n_r!}$$Os fatoriais intermediários se cancelam em cascata: o denominador de um vira o numerador do seguinte.
O departamento de uma pequena cidade tem 10 policiais. A política é ter 5 patrulhando as ruas, 2 em tempo integral na estação e 3 na reserva na estação. Quantas divisões de 10 policiais em 3 grupos são possíveis?
$$\frac{10!}{5! \times 2! \times 3!} = 2\,520$$Comitê com restrições
De um grupo de 8 mulheres e 6 homens, um comitê composto por 3 homens e 3 mulheres deve ser formado.
1. Quantos comitês diferentes são possíveis? 2. Quantos, se 2 dos homens se recusarem a servir juntos? 3. Quantos, se 2 das mulheres se recusarem a servir juntas? 4. Quantos, se 1 homem e 1 mulher se recusam a servir juntos?
As mulheres ficam livres: \(\binom{8}{3}\). Entre os homens, ou nenhum dos dois brigados entra — \(\binom{4}{3}\) — ou entra exatamente um deles — \(\binom{2}{1}\times\binom{4}{2}\):
$$\binom{8}{3} \times \left[\binom{4}{3} + \binom{2}{1}\binom{4}{2}\right] = 56 \times (4 + 12) = 56 \times 16 = 896$$Mesma decomposição, agora do lado das mulheres, com os 6 restantes:
$$\left[\binom{6}{3} + \binom{2}{1}\binom{6}{2}\right] \times \binom{6}{3} = (20 + 30) \times 20 = 50 \times 20 = 1\,000$$Três casos exclusivos: nenhum dos dois entra; entra ele e não ela; entra ela e não ele.
$$\binom{7}{3}\binom{5}{3} + \binom{7}{3}\binom{5}{2}\binom{1}{1} + \binom{7}{2}\binom{1}{1}\binom{5}{3}$$ $$= 350 + 350 + 210 = 910$$Identidade combinatória de Fermat
Considere \(S = \{1,2,3,\dots,n\}\). O coeficiente \(\binom{n}{k}\) é o número de subconjuntos de \(S\) com \(k\) elementos. Conte-os de outra maneira, fixando o maior elemento de cada subconjunto.
Se o maior elemento for \(i\), com \(i \in \{k, k+1, \dots, n\}\):
- o elemento \(i\) está obrigatoriamente incluído;
- os \(k-1\) restantes vêm dos \(i-1\) elementos menores que \(i\), ou seja, de \(\{1,2,\dots,i-1\}\);
- isso pode ser feito de \(\binom{i-1}{k-1}\) maneiras.
Somando todas as possibilidades para \(i\), e como as duas contagens descrevem o mesmo conjunto:
$$\binom{n}{k} = \sum_{i=k}^{n}\binom{i-1}{k-1}$$Formar uma equipe de \(r=3\) pessoas de um grupo de \(n=5\), numeradas de 1 a 5, contando pela pessoa de maior número na equipe. Ela pode ser a 3, a 4 ou a 5.
Maior é 3: as outras 2 vêm de \(\{1,2\}\) \(\Rightarrow \binom{2}{2} = 1\).
Maior é 4: as outras 2 vêm de \(\{1,2,3\}\) \(\Rightarrow \binom{3}{2} = 3\).
Maior é 5: as outras 2 vêm de \(\{1,2,3,4\}\) \(\Rightarrow \binom{4}{2} = 6\).
$$\text{Total} = 1 + 3 + 6 = 10 \qquad\text{e}\qquad \sum_{k=2}^{4}\binom{k}{2} = \binom{5}{3} = 10$$A identidade \(\sum k\binom{n}{k} = n\,2^{n-1}\)
Passo 1. Expanda o termo geral da soma:
$$k\binom{n}{k} = k \cdot \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!}$$Passo 2. Fatorando \(n\), reescreva a soma:
$$\sum_{k=1}^{n} k\binom{n}{k} = n\sum_{k=1}^{n}\frac{(n-1)!}{(k-1)!(n-k)!}$$Passo 3. Observe que \(\frac{(n-1)!}{(k-1)!(n-k)!} = \binom{n-1}{k-1}\). Substituindo:
$$n\sum_{k=1}^{n}\binom{n-1}{k-1}$$Passo 4. Mude o índice: seja \(m = k-1\). Quando \(k=1\), \(m=0\); quando \(k=n\), \(m=n-1\):
$$n\sum_{m=0}^{n-1}\binom{n-1}{m}$$Passo 5. A soma dos coeficientes binomiais \(\sum_{m=0}^{n-1}\binom{n-1}{m}\) é igual a \(2^{n-1}\). Portanto:
$$\sum_{k=1}^{n} k\binom{n}{k} = n \cdot 2^{n-1}$$“Pelo menos um”: contar pelo complementar
Uma empresa possui 50 funcionários, dos quais 10 ocupam cargos de gestão. Quantas maneiras existem para escolher um comitê de 4 pessoas, se deve haver pelo menos uma pessoa de nível gerencial?
Todos os comitês possíveis, menos os que não têm nenhum gestor — esses saem dos 40 não gestores:
$$\binom{50}{4} - \binom{40}{4} = 138\,910 = \sum_{k=1}^{4}\binom{10}{k}\binom{40}{4-k}$$A soma à direita é a contagem direta, caso a caso pelo número \(k\) de gestores no comitê. Dá o mesmo, com muito mais trabalho.
O teorema das estrelas e barras
Método para determinar o número de maneiras de distribuir objetos idênticos em grupos distintos. O nome vem da representação visual de “estrelas” \((*)\) como os objetos e “barras” \((|)\) como separadores entre os grupos.
Existem dois cenários:
Distribuir \(n\) objetos idênticos em \(k\) grupos distintos, com grupos possivelmente vazios:
$$\binom{n+k-1}{k-1}$$Exemplo: distribuir 7 doces entre 3 crianças, podendo alguma receber zero.
$$\binom{7+3-1}{3-1} = \binom{9}{2} = 36 \text{ maneiras}$$Por quê: alinhe \(n\) estrelas e \(k-1\) barras. Cada permutação desses símbolos é uma distribuição — por exemplo
$$*\,*\;|\;*\;|\;*\,*\,*$$significa 2, 1 e 3 doces. O total de arranjos é \(\binom{n+k-1}{k-1}\).
Distribuir \(n\) objetos em \(k\) grupos, cada um com pelo menos 1 objeto:
$$\binom{n-1}{k-1}$$Exemplo: 7 doces entre 3 crianças, cada uma recebendo pelo menos 1 doce. Dê primeiro 1 doce a cada uma; sobram 4 para distribuir livremente:
$$\binom{4+3-1}{3-1} = \binom{6}{2} = 15 \text{ maneiras}$$Por quê: subtraia \(k\) objetos, um por grupo, e resolva o problema para \(n-k\) objetos com grupos podendo ficar vazios. A fórmula se reduz a \(\binom{n-1}{k-1}\).
Se 8 quadros negros idênticos forem divididos entre 4 escolas, quantas divisões são possíveis? E se cada escola tiver que receber pelo menos um?
Sem restrição, com \(n=8\) e \(k=4\):
$$\binom{8+4-1}{4-1} = \binom{11}{3} = 165$$Cada escola com pelo menos um: aloque 1 quadro para cada escola; sobram \(8-4=4\). Aplicando a mesma fórmula com \(n=4\) e \(k=4\):
$$\binom{4+4-1}{4-1} = \binom{7}{3} = 35$$Checklist da A2
Se você consegue responder tudo abaixo sem consultar, a aula está fechada.
| Pergunta | Onde está |
|---|---|
| Deduzir \(\binom{n}{r} = n!/((n-r)!\,r!)\) a partir da permutação | Combinação e sua fórmula |
| Combinar duas escolhas independentes num só comitê | Escolher de dois grupos |
| Contar arranjos em que dois elementos não podem ficar juntos | Antenas: inserir nos espaços |
| Provar a relação de Pascal pelos dois caminhos | Propriedades do binomial |
| Expandir \((x+y)^n\) e justificar o coeficiente | Binômio de Newton |
| Dividir \(n\) itens em grupos rotulados de tamanhos dados | Coeficiente multinomial |
| Quebrar uma restrição de “não servem juntos” em casos exclusivos | Comitê com restrições |
| Aplicar a identidade de Fermat fixando o maior elemento | Identidade de Fermat |
| Resolver somas do tipo \(\sum k\binom{n}{k}\) com troca de índice | A soma \(k\binom{n}{k}\) |
| Responder “pelo menos um” pelo complementar | “Pelo menos um” |
| Escolher entre \(\binom{n+k-1}{k-1}\) e \(\binom{n-1}{k-1}\) | Estrelas e barras |