O princípio multiplicativo
Um projeto exige duas subtarefas, \(A\) e \(B\). Existem \(m\) maneiras de completar \(A\) e \(n\) maneiras de completar \(B\). O número de maneiras de concluir o projeto é
$$m \times n$$Cada uma das \(m\) escolhas de \(A\) se combina com cada uma das \(n\) escolhas de \(B\): as rotas vão de \(\{A{:}1 + B{:}1\}\) até \(\{A{:}m + B{:}n\}\).
O comitê de planejamento tem 3 calouros, 4 alunos do segundo ano, 5 juniores e 2 veteranos. Uma subcomissão de 4, com 1 pessoa de cada classe, deve ser escolhida.
$$3 \times 4 \times 5 \times 2$$Multiplicativo: a subcomissão só fica pronta quando escolho um calouro e um do segundo ano e um júnior e um veterano.
Os 3 primeiros lugares são letras e os 4 finais são números, como ITH-0827. Repetição permitida.
O princípio aditivo
Um projeto pode ser concluído executando a tarefa \(A\) ou a tarefa \(B\). Existem \(m\) maneiras de completar \(A\) e \(n\) maneiras de completar \(B\). O número de maneiras de concluir o projeto é
$$m + n$$Aqui as rotas da origem ao destino passam por \(A\) ou por \(B\), nunca pelos dois.
Contagem sem repetição
Continua sendo o princípio multiplicativo, mas cada escolha consome uma opção: o número de possibilidades cai de uma em uma.
Quantas placas seriam possíveis se a repetição entre letras ou entre números fosse proibida?
$$\text{letras: } 26 \times 25 \times 24 = 15\,600$$ $$\text{números: } 10 \times 9 \times 8 \times 7 = 5\,040$$ $$\text{total} = 15\,600 \times 5\,040 = 78\,624\,000$$Compare com o exemplo anterior: proibir repetição derrubou o total de \(175\,760\,000\) para \(78\,624\,000\).
Permutação ou combinação?
Preciso selecionar 3 letras de 26 para fazer uma placa. Quantos arranjos diferentes são possíveis? A resposta difere:
- a ordem das 3 letras importa \(\Rightarrow\) Permutação. Por exemplo, ITH, TIH e HIT são todos diferentes;
- a ordem das 3 letras não importa \(\Rightarrow\) Combinação.
Esta aula resolve o lado da permutação. A combinação é o assunto da A2.
Permutações: \(n!\)
Suponha \(n\) objetos. O número de permutações diferentes é
$$n \times (n-1) \times (n-2) \times \dots \times 1 = n!$$Por quê? Princípio multiplicativo: a primeira casa tem \(n\) escolhas, a segunda \(n-1\), a terceira \(n-2\), até a última, com 1 escolha.
Um time, sem o goleiro, é composto por 10 jogadores. Quantas ordens de posição diferentes são possíveis?
$$10!$$Uma classe tem 6 homens e 4 mulheres, classificados pelo desempenho na final, sem empates.
1. Quantas classificações diferentes são possíveis?
$$10!$$2. Se as mulheres forem classificadas entre elas e os homens entre si?
$$6! \times 4!$$São duas classificações independentes, uma dentro de cada grupo — daí o produto.
Permutações com elementos repetidos
Quando alguns objetos são idênticos, \(n!\) conta demais: ele separa arranjos que, na prática, são o mesmo.
Passo 1: permutações assumindo que \(P_1\) e \(P_2\) são diferentes — são \(3! = 6\):
$$P_1P_2E \quad P_1EP_2 \quad P_2P_1E \quad P_2EP_1 \quad EP_1P_2 \quad EP_2P_1$$Passo 2: remover duplicatas assumindo que \(P_1\) e \(P_2\) são iguais — sobram 3:
$$PPE \quad PEP \quad EPP$$Cada arranjo real apareceu \(2! = 2\) vezes, uma para cada troca entre os dois P.
Quantas permutações diferentes de \(n\) objetos, das quais \(n_1\) são idênticas, \(n_2\) são idênticas, …, \(n_r\) são idênticas?
- Etapa 1: supondo todos os \(n\) objetos distintos, há \(n!\) permutações;
- Etapa 2: para cada permutação, há \(n_1! \times n_2! \times \dots \times n_r!\) maneiras de trocar objetos e permanecer a mesma permutação;
- Etapa 3: o número total de permutações únicas é
São 6 letras: 3 são P, 2 são E, 1 é R.
$$\frac{6!}{3! \times 2! \times 1!} = 60$$Numa fila de 11 figuras com 6 de um tipo, 3 de outro e 2 de um terceiro, quantas maneiras de trocar os elementos e permanecer a mesma permutação?
$$6! \times 3! \times 2! = 8\,640$$É exatamente o denominador da fórmula acima — o número de arranjos que colapsam em um só.
Um sinal consiste em 9 bandeiras penduradas em uma linha, feitas de 4 bandeiras brancas, 3 vermelhas e 2 azuis. Bandeiras da mesma cor são idênticas.
$$\frac{9!}{4! \times 3! \times 2!} = \frac{362\,880}{24 \times 6 \times 2} = \frac{362\,880}{288} = 1\,260$$Exercício · ramos de tamanhos diferentes
Dois experimentos serão realizados. O primeiro pode levar a qualquer um dos \(m\) resultados possíveis. Se o primeiro experimento levar ao resultado \(i\), então o segundo pode levar a qualquer um dos \(n_i\) resultados possíveis, com \(i=1,2,\dots,m\). Qual é o número de resultados possíveis para os dois experimentos?
O total é a soma do número de resultados do segundo experimento associados a cada resultado do primeiro:
$$\text{Número total de resultados} = \sum_{i=1}^{m} n_i$$Ilustrando com \(m=3\):
$$n_1=2,\quad n_2=3,\quad n_3=4 \;\Rightarrow\; 2+3+4=9$$Exercício · placa de 2 letras e 5 números
(a) Quantas placas de 7 caracteres podem ser formadas se os dois primeiros campos forem reservados para letras e os outros cinco para números?
(b) Repita, supondo que nenhuma letra ou número possa ser repetido na mesma placa.
O alfabeto tem 26 letras, e cada campo numérico aceita qualquer dígito de 0 a 9.
$$\text{letras: } 26 \times 26 = 676$$ $$\text{números: } 10^5 = 100\,000$$ $$\text{total} = 676 \times 100\,000 = 67\,600\,000$$As duas letras devem ser diferentes; os cinco números, diferentes entre si.
$$\text{letras: } 26 \times 25 = 650$$ $$\text{números: } 10 \times 9 \times 8 \times 7 \times 6 = 30\,240$$ $$\text{total} = 650 \times 30\,240 = 19\,656\,000$$Exercício · dado lançado quatro vezes
Quantas sequências de resultados são possíveis quando um dado é rolado quatro vezes? Por exemplo, \(3,4,3,1\) é o resultado se o primeiro cair no 3, o segundo no 4, o terceiro no 3 e o quarto no 1.
Cada lançamento tem 6 resultados possíveis, e os lançamentos são independentes:
$$6 \times 6 \times 6 \times 6 = 6^4 = 1\,296$$O próprio exemplo do enunciado mostra que há repetição — o 3 aparece duas vezes — e que a ordem conta.
Exercício · a canção de São Ives
“Quando ia para São Ives, encontrei um homem com 7 mulheres. Cada mulher tinha 7 sacos. Cada saco tinha 7 gatos. Cada gato tinha 7 gatinhos…” Quantos gatinhos o viajante encontrou?
O viajante encontrou 1 homem com 7 mulheres.
$$\text{sacos} = 7 \times 7 = 49$$ $$\text{gatos} = 49 \times 7 = 343$$Exercício · oito pessoas em fila
De quantas maneiras 8 pessoas podem se sentar em fila se (a) não houver restrições; (b) as pessoas \(A\) e \(B\) tiverem que se sentar uma ao lado da outra; (c) houver 4 homens e 4 mulheres e não for permitido que dois do mesmo grupo se sentem em posições adjacentes; (d) houver 5 homens e for necessário que eles se sentem lado a lado; (e) houver 4 casais e cada casal precisar sentar-se junto?
Considere \(A\) e \(B\) como uma única entidade. Sobram 7 entidades para organizar (o bloco \(AB\) mais as outras 6 pessoas):
$$7! = 5\,040$$Dentro do bloco, \(A\) pode estar à esquerda de \(B\) ou o contrário — 2 arranjos:
$$7! \times 2 = 5\,040 \times 2 = 10\,080$$Para que dois do mesmo grupo nunca fiquem juntos, os grupos têm de se alternar. Há 2 padrões possíveis:
H M H M H M H M · M H M H M H M H
Em cada padrão, os 4 homens se organizam de \(4!\) maneiras e as 4 mulheres de \(4!\):
$$2 \times 4! \times 4! = 2 \times 24 \times 24 = 1\,152$$Os 5 homens viram uma entidade única. Sobram 4 entidades (o bloco mais as 3 mulheres):
$$4! \times 5! = 24 \times 120 = 2\,880$$Cada casal é uma entidade; são 4 entidades. Dentro de cada casal há 2 ordens, e são 4 casais:
$$4! \times 2^4 = 24 \times 16 = 384$$Exercício · cinco prêmios, trinta alunos
Cinco prêmios diferentes serão dados a estudantes de uma classe de trinta alunos. Quantos resultados diferentes são possíveis se (a) um estudante puder receber qualquer número de prêmios; (b) cada estudante puder receber no máximo um prêmio?
Cada um dos 5 prêmios pode ir para qualquer um dos 30 alunos, e os prêmios são diferentes:
$$30 \times 30 \times 30 \times 30 \times 30 = 30^5$$Cada prêmio vai para um aluno diferente, então o número de candidatos cai a cada prêmio:
$$30 \times 29 \times 28 \times 27 \times 26$$Checklist da A1
Se você consegue responder tudo abaixo sem consultar, a aula está fechada.
| Pergunta | Onde está |
|---|---|
| Decidir, lendo o enunciado, se as etapas multiplicam ou somam | Princípio multiplicativo |
| Contar arranjos com repetição permitida e com repetição proibida | Contagem sem repetição |
| Dizer se o problema pede permutação ou combinação | Permutação ou combinação? |
| Justificar por que \(n\) objetos geram \(n!\) ordens | Permutações: \(n!\) |
| Montar \(n!/(n_1!\dots n_r!)\) e explicar de onde vem o denominador | Elementos repetidos |
| Somar ramos quando o segundo experimento depende do primeiro | Ramos de tamanhos diferentes |
| Resolver contagem por blocos quando itens precisam ficar juntos | Oito pessoas em fila |
| Alternar dois grupos numa fila sem vizinhos iguais | Oito pessoas em fila (c) |
| Separar sorteio com reposição de sorteio sem reposição | Cinco prêmios, trinta alunos |