Matemática · Ensino Médio · Contagem

Contagem

Quantas placas cabem no padrão Mercosul, quantas senhas de quatro algarismos existem, de quantas maneiras se marcam seis números entre sessenta? Listar as possibilidades uma a uma raramente é viável, e quase sempre basta multiplicar as escolhas de cada etapa e dividir pelas repetições que não interessam. Essa maneira de contar sem listar é a análise combinatória, e quase toda ela sai de um único princípio, o de multiplicar escolhas feitas em etapas.

1Princípio multiplicativo
2Senhas e placas
3Permutações
4O tamanho de n!
5Arranjos
6Combinações
7Anagramas
8Triângulo de Pascal
✓Desafios

PASSO 1

De quantas maneiras dá para montar um lanche?

Uma lanchonete deixa o cliente escolher o pão, o recheio e a bebida. Com 3 pães, 4 recheios e 2 bebidas, cada pão pode ir com qualquer recheio, e cada par de pão e recheio pode ir com qualquer bebida. Desenhando as escolhas em sequência, cada etapa abre galhos novos na ponta de cada galho anterior, e a figura que se forma é a árvore de possibilidades.

Cada caminho da raiz até uma folha é um lanche. A primeira etapa abre 3 galhos, cada um deles se abre em 4 e cada um desses em 2, o que dá $3 \cdot 4 \cdot 2 = 24$ folhas. Esse é o princípio multiplicativo. Quando uma escolha é feita em etapas e o número de opções de cada etapa não depende do que se escolheu nas anteriores, o total é o produto desses números.

Escolhas que se excluem somam. Se a lanchonete vende também 3 combos prontos, o cliente monta um lanche ou leva um combo, nunca as duas coisas, e o total passa a $24 + 3 = 27$. Esse é o princípio aditivo, e boa parte dos problemas de contagem mistura os dois. Separamos os casos que não se sobrepõem, multiplicamos dentro de cada caso e somamos no fim.

$n_1 \cdot n_2 \cdot \ldots \cdot n_k$$|A \cup B| = |A| + |B|$O produto vale quando a etapa $i$ tem $n_i$ opções, qualquer que tenha sido a escolha nas etapas anteriores. A soma vale para casos $A$ e $B$ sem elemento em comum.

Para conversar

Com 3 pães, 4 recheios e 2 bebidas, toque em "Crescer a árvore" e conte os pontos de cada nível. Como cada nível sai do anterior?
Leve a bebida para 1 opção. A árvore muda de forma, e o total? O que uma etapa com uma única opção faz com o produto?
Imagine a árvore com a bebida escolhida antes do pão. Ela teria outra cara, e o número de folhas mudaria?
Ponha 3 combos prontos. Por que eles entram somando ao total, e não multiplicando?

Pães

Recheios

Bebidas

Combos prontos

Lanches montados

Total com os combos

Caminho destacado

Exercícios do passo 1 10 questões · 4 básicas · 4 médias · 2 desafios

básico
Uma sorveteria tem 5 sabores e 3 coberturas. Quantas taças diferentes, com um sabor e uma cobertura, ela pode servir?

Ver resolução
A escolha tem duas etapas, o sabor e a cobertura, e qualquer cobertura serve com qualquer sabor.
$5 \cdot 3 = 15$.
15 taças.
básico
Uma pessoa tem 4 camisas, 3 calças e 2 pares de tênis. De quantas maneiras ela pode se vestir usando uma peça de cada tipo?

Ver resolução
São três etapas independentes, com 4, 3 e 2 opções.
$4 \cdot 3 \cdot 2 = 24$.
24 maneiras.
básico
Quantos números naturais de dois algarismos existem?

Ver resolução
O algarismo das dezenas não pode ser 0, senão o número teria um algarismo só, e sobram 9 opções. O das unidades aceita os 10.
$9 \cdot 10 = 90$, os números de 10 a 99.
90 números.
básico
No almoço de um restaurante, o cliente escolhe um entre 4 pratos principais e, além dele, uma entrada entre 3 ou uma sobremesa entre 5, só uma das duas. Quantos almoços diferentes são possíveis?

Ver resolução
O complemento é uma entrada ou uma sobremesa, casos que se excluem, e por isso somam: $3 + 5 = 8$ opções.
Cada uma delas vai com qualquer dos 4 pratos, e $4 \cdot 8 = 32$.
32 almoços.
médio
Quantos números naturais de três algarismos distintos existem?

Ver resolução
O algarismo das centenas tem 9 opções, de 1 a 9.
O das dezenas pode ser o 0, mas não o já usado, e também tem 9 opções. O das unidades fica com 8.
$9 \cdot 9 \cdot 8 = 648$.
648 números.
médio
Quantos números pares de três algarismos existem, com repetição permitida?

Ver resolução
As centenas têm 9 opções e as dezenas, 10. As unidades precisam ser 0, 2, 4, 6 ou 8, 5 opções.
$9 \cdot 10 \cdot 5 = 450$.
450 números, exatamente a metade dos 900 números de três algarismos.
médio
Uma moeda é lançada três vezes. Desenhe a árvore dos resultados. Quantos resultados há, e em quantos deles saem exatamente duas caras?

Ver resolução
Cada lançamento abre dois galhos, cara (K) e coroa (C), e a árvore termina com $2 \cdot 2 \cdot 2 = 8$ folhas.
As folhas com duas caras são KKC, KCK e CKK.
8 resultados, 3 deles com exatamente duas caras.
médio
Entre as cidades A e B há 3 estradas, entre B e C há 2, e de A até C há ainda 2 estradas diretas, que não passam por B. De quantas maneiras dá para ir de A até C?

Ver resolução
Passando por B, a viagem tem duas etapas, $3 \cdot 2 = 6$ maneiras.
Pelas estradas diretas são 2 maneiras, e os dois casos não se sobrepõem.
$6 + 2 = 8$.
8 maneiras.
desafio
Nas estradas do exercício anterior, uma pessoa vai de A até C passando por B e volta de C até A, pela estrada direta ou por B, sem usar na volta nenhuma estrada usada na ida. Quantas viagens de ida e volta são possíveis?

Ver resolução
A ida por B tem $3 \cdot 2 = 6$ maneiras.
Na volta por B, sobra 1 estrada de C a B e 2 de B a A, o que dá $1 \cdot 2 = 2$ maneiras. A volta direta tem as 2 estradas, que a ida não usou. A volta tem então $2 + 2 = 4$ maneiras, qualquer que tenha sido a ida.
$6 \cdot 4 = 24$.
24 viagens.
desafio
Quantos divisores positivos tem o número 360?

Ver resolução
Fatorando, $360 = 2^3 \cdot 3^2 \cdot 5$. Um divisor positivo é um produto $2^a \cdot 3^b \cdot 5^c$ com $0 \le a \le 3$, $0 \le b \le 2$ e $0 \le c \le 1$, e cada escolha dos três expoentes dá um divisor diferente.
O expoente $a$ tem 4 opções, $b$ tem 3 e $c$ tem 2, e $4 \cdot 3 \cdot 2 = 24$.
24 divisores.

PASSO 2

Quantas senhas e placas cabem num padrão?

Uma senha de 4 algarismos se escolhe em quatro etapas, uma por posição, e cada posição aceita os 10 algarismos, qualquer que seja o escolhido antes. Pelo princípio multiplicativo, há $10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10{.}000$ senhas, de 0000 a 9999. Quando o mesmo alfabeto de $n$ símbolos serve às $k$ posições e os símbolos podem se repetir, o total é a potência $n^k$.

As placas de carro seguem a mesma conta, com alfabetos diferentes em cada posição. A placa cinza, no padrão "AAA-1111" da Resolução CONTRAN nº 969/2022, tem três letras e quatro algarismos, e cabem nela $26^3 \cdot 10^4 = 175{.}760{.}000$ combinações. A placa Mercosul, da mesma resolução, tem sete caracteres na sequência LLLNLNN, em que L é letra e N é algarismo, e o total sobe para $26^4 \cdot 10^3 = 456{.}976{.}000$.

$\underbrace{n \cdot n \cdot \ldots \cdot n}_{k} = n^k$$26^3 \cdot 10^4$$26^4 \cdot 10^3$Com repetição, cada uma das $k$ posições tem as $n$ opções do alfabeto. Sem repetição, o alfabeto perde um símbolo a cada posição preenchida, e a senha de 4 algarismos distintos fica com $10 \cdot 9 \cdot 8 \cdot 7$ opções.

A placa Mercosul trocou o segundo algarismo por uma letra, e o fator 10 dessa posição virou 26. As placas possíveis ficaram multiplicadas por 2,6, e não por 26, porque só uma das sete posições mudou de alfabeto. Proibir a repetição muda as contas de outro jeito. Numa senha de 4 algarismos distintos, a segunda posição tem 9 opções, porque um algarismo já foi usado, e o total cai para $10 \cdot 9 \cdot 8 \cdot 7 = 5040$.

A bancada calcula também quanto tempo alguém levaria para testar todas as senhas a um certo ritmo. É uma estimativa grosseira, e mesmo assim sugere por que um sistema tende a bloquear o acesso depois de poucas tentativas erradas. Senhas curtas caem em minutos quando o ritmo é de máquina.

Para conversar

Escolha a senha de 4 algarismos e depois a de 6. Por quanto o total foi multiplicado quando a senha ganhou duas posições?
Compare a placa cinza com a Mercosul. Que caixa mudou de alfabeto, e de onde vem o fator 2,6?
Ligue "Sem repetir símbolo" na senha de 4 algarismos. Que fração das senhas some? E na placa Mercosul?
Com a senha de 6 letras ou algarismos, leve o ritmo a mil tentativas por segundo. Quanto tempo levaria para testar todas? E com a senha de 4 algarismos, no mesmo ritmo?

Tentativas por segundo

Possibilidades

A conta

Tempo para testar todas

Exemplo sorteado

Padrões de placa da Resolução CONTRAN nº 969/2022 (art. 2º e Anexos I e II). As senhas são exemplos ilustrativos, e o comprimento da senha de cartão muda de um banco para outro.

Exercícios do passo 2 10 questões · 4 básicas · 4 médias · 2 desafios

básico
Um cadeado tem 3 discos, cada um com os algarismos de 0 a 9. Quantas combinações ele aceita?

Ver resolução
Cada disco tem 10 posições, e os algarismos podem se repetir.
$10^3 = 1000$, de 000 a 999.
1000 combinações.
básico
Quantas placas cinza, no padrão LLL-NNNN, começam com as letras ABC?

Ver resolução
As três letras estão fixas, e sobram as quatro posições de algarismo, com 10 opções cada.
$10^4 = 10{.}000$.
10.000 placas.
básico
Uma prova tem 10 questões de verdadeiro ou falso. De quantas maneiras diferentes um aluno pode preencher o gabarito, respondendo a todas?

Ver resolução
Cada questão tem 2 respostas possíveis, e as 10 escolhas são independentes.
$2^{10} = 1024$.
1024 gabaritos, e só um deles acerta tudo.
básico
Quantas senhas de 5 letras, escolhidas entre as 26 do alfabeto e com repetição permitida, existem?

Ver resolução
Cada uma das 5 posições tem 26 opções.
$26^5 = 11{.}881{.}376$.
11.881.376 senhas.
médio
Quantas senhas de 4 algarismos têm pelo menos um algarismo repetido?

Ver resolução
Contar diretamente pede muitos casos. É mais simples contar o contrário.
Há $10^4 = 10{.}000$ senhas ao todo, e $10 \cdot 9 \cdot 8 \cdot 7 = 5040$ delas têm os quatro algarismos distintos.
$10{.}000 - 5040 = 4960$.
4960 senhas, quase a metade.
médio
Um carro com a placa cinza RTA4078 passa para a placa Mercosul. Pela tabela do Anexo II da Resolução CONTRAN nº 969/2022, o segundo algarismo vira letra, com 0 → A, 1 → B, e assim por diante até 9 → J. Qual é a placa nova?

Ver resolução
Os algarismos da placa são 4, 0, 7 e 8, e o segundo é o 0, que vira A.
RTA4A78. A troca usa só as letras de A a J nessa posição, o que deixa ler a placa antiga na nova.
médio
Quantas placas Mercosul, no padrão LLLNLNN, têm as três primeiras letras iguais?

Ver resolução
As três primeiras letras se escolhem juntas, com 26 opções, de AAA a ZZZ.
As outras posições seguem livres, com 10, 26, 10 e 10 opções.
$26 \cdot 10 \cdot 26 \cdot 10 \cdot 10 = 676{.}000$.
676.000 placas.
médio
Uma senha de 6 caracteres pode usar as 26 letras maiúsculas, as 26 minúsculas e os 10 algarismos. Por quanto, aproximadamente, o total de senhas fica multiplicado em relação ao de senhas de 6 algarismos?

Ver resolução
Com 62 símbolos há $62^6$ senhas, e com 10 há $10^6$.
$\dfrac{62^6}{10^6} = 6{,}2^6 \approx 56{.}800$.
Cerca de 56.800 vezes. Uma questão do ENEM de 2013, listada no fim da aula, pede justamente essa razão.
desafio
Quantas placas Mercosul não têm nenhuma letra repetida nem nenhum algarismo repetido? Que fração do total isso representa?

Ver resolução
Nas posições LLLNLNN, as letras recebem 26, 25, 24 e 23 opções, na ordem em que aparecem, e os algarismos recebem 10, 9 e 8.
$26 \cdot 25 \cdot 24 \cdot 10 \cdot 23 \cdot 9 \cdot 8$
$= 258{.}336{.}000$.
$\dfrac{258{.}336{.}000}{456{.}976{.}000} \approx 0{,}565$.
258.336.000 placas, cerca de 56,5% do total.
desafio
Um programa testa mil senhas numéricas por segundo. Quantos algarismos uma senha precisa ter, no mínimo, para que testar todas leve mais de um ano, de 365,25 dias?

Ver resolução
Um ano tem $365{,}25 \cdot 86{.}400 = 31{.}557{.}600$ segundos, e nesse tempo o programa testa cerca de $3{,}16 \cdot 10^{10}$ senhas.
Com $k$ algarismos há $10^k$ senhas, e precisamos de $10^k > 3{,}16 \cdot 10^{10}$.
Com $k = 10$ o programa termina em cerca de 116 dias, e com $k = 11$, em cerca de 3,2 anos.
11 algarismos.

PASSO 3

De quantas maneiras uma fila pode se formar?

Cinco amigos chegam juntos à fila do cinema. O primeiro lugar pode ficar com qualquer um dos cinco, o segundo com qualquer um dos quatro que sobram, e assim por diante, até o último lugar, que fica com quem restou. Pelo princípio multiplicativo, as filas possíveis são $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$.

Cada uma dessas ordens é uma permutação dos cinco amigos. O produto dos naturais de 1 até $n$ tem nome e símbolo próprios, o fatorial de $n$, escrito $n!$. A diferença em relação às senhas do passo 2 está na repetição, porque uma pessoa não ocupa dois lugares da fila, e cada etapa tem uma opção a menos que a anterior.

Convencionamos $0! = 1$. A convenção mantém a relação $n! = n \cdot (n - 1)!$ válida também para $n = 1$, e corresponde a uma contagem razoável, porque há uma única maneira de arrumar zero objetos. Listas de permutações costumam vir na ordem do dicionário, como na bancada. Com $n = 3$, as ordens de A, B e C são ABC, ACB, BAC, BCA, CAB e CBA.

$P_n = n! = n \cdot (n - 1) \cdot \ldots \cdot 2 \cdot 1$$n! = n \cdot (n - 1)!$$0! = 1$$P_n$ é o número de permutações de $n$ objetos distintos, isto é, de maneiras de pô-los em fila.

Para conversar

Com $n = 3$, toque em "Próxima ordem" até a lista recomeçar. Quantas ordens começam com A, e por que são tantas quantas as que começam com B?
Passe de $n = 4$ para $n = 5$. Por quanto o total foi multiplicado? E de 5 para 6?
Com $n = 4$, em que posição da lista fica a ordem DCBA? Por que ela é a última?
Ligue "Animar" com $n = 7$. Vendo uma ordem por segundo, quanto tempo levaria para ver todas?

Pessoas na fila, n

Filas possíveis, n!

A conta

Ordem atual

Exercícios do passo 3 10 questões · 4 básicas · 4 médias · 2 desafios

básico
De quantas maneiras 4 livros diferentes podem ser arrumados lado a lado numa prateleira?

Ver resolução
O primeiro lugar tem 4 opções, o segundo 3, o terceiro 2 e o último 1.
$4! = 24$.
24 maneiras.
básico
Calcule $\dfrac{6!}{4!}$ sem calcular os dois fatoriais.

Ver resolução
Como $6! = 6 \cdot 5 \cdot 4!$, o $4!$ se cancela.
$\dfrac{6!}{4!} = 6 \cdot 5 = 30$.
30.
básico
De quantas maneiras 5 pessoas podem se sentar num banco de 5 lugares?

Ver resolução
Sentar as pessoas no banco é pô-las em fila, uma por lugar.
$5! = 120$.
120 maneiras.
básico
Quantos anagramas tem a palavra AMOR, contando a própria palavra?

Ver resolução
As quatro letras são distintas, e cada anagrama é uma ordem delas.
$4! = 24$.
24 anagramas, de AMOR a ROMA e RAMO.
médio
Quantos anagramas da palavra CINEMA começam com vogal?

Ver resolução
A primeira letra precisa ser I, E ou A, 3 opções.
As 5 letras restantes se arrumam em $5! = 120$ ordens.
$3 \cdot 120 = 360$.
360 anagramas, exatamente a metade dos $6! = 720$, porque CINEMA tem tantas vogais quanto consoantes.
médio
Seis pessoas vão posar em fila para uma foto, e Ana e Bia querem ficar lado a lado. De quantas maneiras a fila pode ser formada?

Ver resolução
Colamos Ana e Bia num bloco só, e a fila passa a ter 5 elementos, que se arrumam em $5! = 120$ ordens.
Dentro do bloco, a ordem pode ser Ana e Bia ou Bia e Ana, 2 maneiras.
$2 \cdot 120 = 240$.
240 maneiras.
médio
Resolva a equação $\dfrac{(n + 1)!}{(n - 1)!} = 56$, com $n$ natural.

Ver resolução
Como $(n + 1)! = (n + 1) \cdot n \cdot (n - 1)!$, a fração vale $(n + 1)\,n$.
$(n + 1)\,n = 56 = 8 \cdot 7$, e daí $n = 7$. A outra raiz de $n^2 + n - 56 = 0$, $n = -8$, não é natural.
$n = 7$.
médio
As permutações de A, B, C e D são listadas em ordem alfabética, de ABCD a DCBA. Em que posição fica CABD?

Ver resolução
Antes das ordens que começam com C vêm as que começam com A e com B, $2 \cdot 3! = 12$ ordens.
Entre as que começam com C, as que continuam com A vêm primeiro, e CABD é a primeira delas, porque B vem antes de D.
13ª posição.
desafio
De quantas maneiras 5 pessoas podem se sentar em volta de uma mesa redonda, se duas arrumações que diferem só por uma rotação contam como a mesma?

Ver resolução
Em fila seriam $5! = 120$ ordens. Cada arrumação da mesa aparece nessa lista 5 vezes, uma para cada pessoa que escolhemos como ponto de partida.
$\dfrac{120}{5} = 24 = 4!$.
24 maneiras. Fixar uma pessoa e arrumar as outras 4 dá a mesma conta, $(n - 1)!$.
desafio
Com os algarismos 1, 2, 3, 4 e 5, sem repetir, formamos todos os números de cinco algarismos. Quanto dá a soma de todos eles?

Ver resolução
São $5! = 120$ números. Fixando um algarismo numa posição, os outros quatro se arrumam em $4! = 24$ ordens, e cada algarismo aparece 24 vezes em cada posição.
Em cada posição a soma dos algarismos é $24 \cdot (1 + 2 + 3 + 4 + 5) = 360$.
As posições valem 1, 10, 100, 1000 e 10.000, que somam 11.111.
$360 \cdot 11{.}111 = 3{.}999{.}960$.
3.999.960.

PASSO 4

Quão depressa cresce $n!$?

O fatorial acaba passando qualquer exponencial. Ir de $n!$ para $(n + 1)!$ multiplica o valor por $n + 1$, um fator que aumenta a cada passo, enquanto ir de $2^n$ para $2^{n+1}$ multiplica sempre por 2. Por isso $4! = 24$ já passa de $2^4 = 16$, e daí em diante a distância só aumenta. Contra $10^n$ o fatorial demora mais e só fica à frente a partir de $n = 25$.

Números desse tamanho não cabem num gráfico comum. A bancada põe no eixo vertical o logaritmo decimal do valor, uma escala em que cada marca vale dez vezes a anterior, como no passo 8 da aula de Exponencial e logaritmo. Nessa escala a exponencial $b^n$ vira uma reta de inclinação $\log b$, e o fatorial aparece como uma curva que fica cada vez mais inclinada.

$(n + 1)! = (n + 1) \cdot n!$$\log n! = \log 1 + \log 2 + \ldots + \log n$O logaritmo de um produto é a soma dos logaritmos, e por isso $\log n!$ se calcula somando. Um inteiro positivo $N$ tem $\lfloor \log N \rfloor + 1$ algarismos.

Um baralho de 52 cartas pode ficar em $52!$ ordens, um número de 68 algarismos, cerca de $8{,}07 \cdot 10^{67}$. É plausível que um embaralhamento bem feito produza uma ordem que nenhum baralho teve antes, porque todos os baralhos já embaralhados no mundo são uma parte desprezível desse total. Quem quisesse ver as ordens de uma fila de 20 pessoas, uma por segundo, levaria cerca de 77 bilhões de anos.

A bancada calcula $n!$ com inteiros de tamanho arbitrário e mostra todos os algarismos, mesmo depois de $2^{53} \approx 9 \cdot 10^{15}$, o limite a partir do qual os números comuns de um computador deixam de guardar inteiros com exatidão. A partir de $n = 19$, o valor exato ganha também a notação científica.

Para conversar

Leve o cursor a $n = 3$ e depois a $n = 4$. Em que momento $n!$ passa $2^n$, e o que a distância entre as duas curvas faz depois disso?
Ligue $10^n$ e procure o $n$ em que o fatorial cruza essa reta. Quantos algarismos tem $n!$ ali?
Em $n = 52$, quantos algarismos tem $n!$? Compare com o expoente da notação científica.
Compare $n^2$ com $2^n$ no começo do gráfico. Quem ganha em $n = 3$, e quem ganha de $n = 5$ em diante?

n! exato

Algarismos de n!

2ⁿ

n! ÷ 2ⁿ

Exercícios do passo 4 10 questões · 4 básicas · 4 médias · 2 desafios

básico
Calcule $7!$ e diga quantos algarismos tem $10! = 3{.}628{.}800$.

Ver resolução
$7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5040$.
O número 3.628.800 tem 7 algarismos.
$7! = 5040$, e $10!$ tem 7 algarismos.
básico
Qual é maior, $5!$ ou $2^5$? E $3!$ ou $2^3$?

Ver resolução
$5! = 120$ e $2^5 = 32$.
$3! = 6$ e $2^3 = 8$.
$5! > 2^5$, mas $3! < 2^3$. O fatorial passa $2^n$ em $n = 4$.
básico
Calcule $\dfrac{8!}{7!}$ e $\dfrac{100!}{99!}$.

Ver resolução
Como $n! = n \cdot (n - 1)!$, a razão entre fatoriais vizinhos é o maior dos dois números.
8 e 100.
básico
Com quantos zeros termina $10! = 3{.}628{.}800$? De onde eles vêm?

Ver resolução
O número termina em dois zeros.
Cada zero final vem de um fator 10, isto é, de um par 2 e 5. Entre 1 e 10, os fatores 5 aparecem no 5 e no 10, duas vezes, e fatores 2 sobram.
2 zeros.
médio
Encontre o natural $n$ tal que $\dfrac{n!}{(n - 2)!} = 30$.

Ver resolução
A fração vale $n\,(n - 1)$.
$n\,(n - 1) = 30 = 6 \cdot 5$.
$n = 6$.
médio
Usando $\log 2 \approx 0{,}301$, quantos algarismos tem $2^{50}$?

Ver resolução
$\log 2^{50} = 50 \log 2 \approx 15{,}05$.
O número fica entre $10^{15}$ e $10^{16}$, e tem $\lfloor 15{,}05 \rfloor + 1 = 16$ algarismos.
16 algarismos. De fato, $2^{50} = 1{.}125{.}899{.}906{.}842{.}624$.
médio
Mostre que $6! < 3^6$ e $7! > 3^7$. Por que, daí em diante, $n!$ fica sempre acima de $3^n$?

Ver resolução
$6! = 720 < 729 = 3^6$ e $7! = 5040 > 2187 = 3^7$.
De $n$ para $n + 1$, o fatorial é multiplicado por $n + 1$, que a partir de $n = 7$ vale pelo menos 8, e $3^n$ é multiplicado só por 3.
A partir de $n = 7$, o lado esquerdo começa maior e cresce mais depressa a cada passo.
médio
Com quantos zeros termina $25!$?

Ver resolução
Os múltiplos de 5 até 25 são 5, 10, 15, 20 e 25, e cada um dá um fator 5. O 25 dá dois, porque $25 = 5^2$.
$4 + 2 = 6$ fatores 5, e há fatores 2 de sobra para formar os pares.
6 zeros. De fato, 25! = 15.511.210.043.330.985.984.000.000.
desafio
Com $20! \approx 2{,}43 \cdot 10^{18}$, quanto tempo levaria para ver todas as ordens de uma fila de 20 pessoas, uma por segundo? Compare com a idade do Universo, cerca de $1{,}4 \cdot 10^{10}$ anos.

Ver resolução
Um ano tem cerca de $3{,}16 \cdot 10^{7}$ segundos.
$\dfrac{2{,}43 \cdot 10^{18}}{3{,}16 \cdot 10^{7}} \approx 7{,}7 \cdot 10^{10}$ anos.
Cerca de 77 bilhões de anos, umas 5,5 vezes a idade do Universo.
desafio
Sabendo que $24! \approx 6{,}20 \cdot 10^{23}$, mostre que $25! > 10^{25}$ e que $n! > 10^n$ para todo $n \ge 25$.

Ver resolução
$25! = 25 \cdot 24! \approx 25 \cdot 6{,}20 \cdot 10^{23}$
$= 1{,}55 \cdot 10^{25}$, maior que $10^{25}$.
Se $n! > 10^n$ para algum $n \ge 25$, então $(n + 1)! = (n + 1)\,n! > 26 \cdot 10^n$
$> 10 \cdot 10^n = 10^{n+1}$.
A desigualdade vale em 25 e passa de cada $n$ para o seguinte, e por isso vale para todo $n \ge 25$. Em $n = 24$ ela falha, porque $6{,}20 \cdot 10^{23} < 10^{24}$.

PASSO 5

E quando só alguns lugares vão ser ocupados?

Oito atletas disputam uma final, e só os três primeiros sobem ao pódio. O ouro pode ficar com qualquer um dos 8, a prata com qualquer um dos 7 restantes e o bronze com um dos 6 que sobram, o que dá $8 \cdot 7 \cdot 6 = 336$ pódios. É a fila do passo 3 interrompida no terceiro lugar.

Uma escolha de $k$ objetos entre $n$, sem repetição e com a ordem importando, é um arranjo de $n$ elementos tomados $k$ a $k$. O produto tem $k$ fatores, começa em $n$ e desce de um em um. Completando esse produto até o 1, com $(n - k)!$ no numerador e no denominador, ele se escreve com fatoriais.

A fórmula com fatoriais tem uma leitura direta. Das $8! = 40{.}320$ ordens de chegada completas, as que têm o mesmo pódio diferem só na ordem dos 5 atletas de fora, e cada pódio aparece $5! = 120$ vezes. Dividindo, $40{.}320 / 120 = 336$. Com $k = n$ o arranjo é a permutação inteira, e a fórmula dá $n!/0! = n!$, mais uma razão para a convenção $0! = 1$.

$A_{n,k} = n\,(n - 1) \cdots (n - k + 1)$$A_{n,k} = \dfrac{n!}{(n - k)!}$O produto tem $k$ fatores, e a fórmula vale para $0 \le k \le n$. Muitos livros escrevem $A_n^k$.

Para conversar

Com 8 atletas e 3 lugares, toque em "Próximo pódio" algumas vezes. Quem muda primeiro, o ouro ou o bronze? Por quê?
Fixe $n = 5$ e leve $k$ de 1 a 5. Que conta do passo 3 o último valor reproduz?
Compare $k = n - 1$ com $k = n$. Por que os dois arranjos dão o mesmo número?
Com $n = 4$ e $k = 2$, liste de cabeça os 12 pódios e confira com a bancada, tocando em "Próximo pódio".

Atletas, n

Lugares no pódio, k

Pódios possíveis

A conta

Pódio atual

Exercícios do passo 5 10 questões · 4 básicas · 4 médias · 2 desafios

básico
Uma corrida tem 10 participantes. Quantos resultados diferentes são possíveis para o ouro, a prata e o bronze?

Ver resolução
$A_{10,3} = 10 \cdot 9 \cdot 8 = 720$.
720 pódios.
básico
Calcule $A_{6,2}$ pelo produto e pela fórmula com fatoriais.

Ver resolução
Pelo produto, $6 \cdot 5 = 30$.
Pelos fatoriais, $\dfrac{6!}{4!} = \dfrac{720}{24} = 30$.
30.
básico
Um clube de 12 sócios vai eleger um presidente e um vice-presidente, que não podem ser a mesma pessoa. Quantas chapas são possíveis?

Ver resolução
Os cargos são diferentes, e trocar as duas pessoas de cargo dá outra chapa. A ordem importa.
$A_{12,2} = 12 \cdot 11 = 132$.
132 chapas.
básico
Quantos números de três algarismos distintos podem ser formados só com os algarismos de 1 a 9?

Ver resolução
Sem o zero, nenhuma posição tem restrição além da repetição.
$A_{9,3} = 9 \cdot 8 \cdot 7 = 504$.
504 números.
médio
Cinco pessoas vão se sentar numa fila de 8 cadeiras, e três cadeiras ficam vazias. De quantas maneiras elas podem se sentar?

Ver resolução
Cada pessoa escolhe uma cadeira, sem repetir. A primeira tem 8 opções, a segunda 7, e assim até a quinta, que tem 4.
$A_{8,5} = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 6720$.
6720 maneiras.
médio
Resolva $A_{n,2} = 42$, com $n$ natural.

Ver resolução
$A_{n,2} = n\,(n - 1) = 42 = 7 \cdot 6$.
$n = 7$.
médio
Uma bandeira tem 3 faixas horizontais, pintadas com cores escolhidas entre 6. Quantas bandeiras existem com as três cores distintas? E com a exigência só de que faixas vizinhas tenham cores diferentes?

Ver resolução
Com as três cores distintas, $A_{6,3} = 6 \cdot 5 \cdot 4 = 120$.
Com faixas vizinhas diferentes, a de cima tem 6 cores, a do meio 5, e a de baixo só não pode repetir a do meio, e também tem 5. A de baixo pode repetir a de cima.
$6 \cdot 5 \cdot 5 = 150$.
120 e 150 bandeiras.
médio
Quantas senhas de 4 algarismos distintos começam com 7?

Ver resolução
Com o 7 fixo na frente, as outras três posições se escolhem entre os 9 algarismos restantes, sem repetir.
$A_{9,3} = 9 \cdot 8 \cdot 7 = 504$.
504 senhas, um décimo das 5040 senhas com algarismos distintos.
desafio
Quantos números pares de quatro algarismos distintos existem?

Ver resolução
O zero cria dois casos que se excluem.
Terminando em 0, as outras três posições ficam com $9 \cdot 8 \cdot 7 = 504$ escolhas.
Terminando em 2, 4, 6 ou 8, a primeira posição não pode ser 0 nem o algarismo final, e tem 8 opções. As duas do meio ficam com 8 e 7. Isso dá $4 \cdot 8 \cdot 8 \cdot 7 = 1792$.
$504 + 1792 = 2296$.
2296 números.
desafio
Mostre que $A_{n,k} = n \cdot A_{n-1,k-1}$ e dê uma leitura da igualdade em termos de pódios.

Ver resolução
Pelos fatoriais, $n \cdot \dfrac{(n - 1)!}{(n - 1 - (k - 1))!}$
$= \dfrac{n!}{(n - k)!} = A_{n,k}$.
O primeiro lugar do pódio tem $n$ opções, e, escolhido o primeiro, os $k - 1$ lugares restantes formam um pódio menor entre os $n - 1$ atletas que sobraram.

PASSO 6

E quando a ordem não importa?

Uma comissão de 3 alunos sai de uma turma de 8. Ao contrário do pódio, a comissão formada por Ana, Bia e Caio é a mesma em qualquer ordem em que os nomes tenham sido escolhidos. Os 336 arranjos do passo 5 contam cada comissão $3! = 6$ vezes, uma para cada ordem dos seus membros, e as comissões são $336 / 6 = 56$.

Um subconjunto de $k$ elementos escolhido entre $n$ é uma combinação de $n$ elementos tomados $k$ a $k$, que se lê "$n$ escolhe $k$". A pergunta que separa arranjo de combinação é se trocar a ordem dos escolhidos produz um resultado diferente. Escolher os $k$ que entram é o mesmo que escolher os $n - k$ que ficam de fora, e por isso $C_{n,k} = C_{n,n-k}$.

A Mega-Sena é uma combinação. O apostador marca 6 números entre 60, sem ordem, o que dá $C_{60,6} = 50{.}063{.}860$ apostas simples diferentes, a R$ 6,00 cada, pelas regras da Caixa. Quem marca 7 números concorre com as $C_{7,6} = 7$ apostas de seis contidas no seu jogo e paga por elas, R$ 42,00, e a chance da sena passa a 1 em 7.151.980.

$C_{n,k} = \dbinom{n}{k} = \dfrac{A_{n,k}}{k!}$$\dbinom{n}{k} = \dfrac{n!}{k!\,(n - k)!}$$\dbinom{n}{k} = \dbinom{n}{n - k}$Vale para $0 \le k \le n$, com $\binom{n}{0} = \binom{n}{n} = 1$. Cada grupo de $k$ elementos corresponde a $k!$ arranjos.

Para conversar

No modo de grupos, com $n = 5$ e $k = 2$, toque em "Próximo grupo" até a lista recomeçar. Quantos grupos apareceram, e quantas ordens cada um junta?
Com $n = 6$, compare $k = 2$ com $k = 4$. Por que os dois totais coincidem? Toque nos pontos para ver os grupos complementares.
No volante, marque 6 números e depois 7. Quantas apostas simples o jogo de 7 contém, e quanto ele custa?
Leve o volante a 20 números. Quantas vezes o preço passou o de uma aposta simples, e por quanto a chance da sena foi multiplicada?

Elementos, n

Tamanho do grupo, k

Exercícios do passo 6 10 questões · 4 básicas · 4 médias · 2 desafios

básico
Quantas duplas diferentes podem ser formadas com 5 pessoas?

Ver resolução
A dupla de Ana e Bia é a mesma de Bia e Ana, e a ordem não importa.
$\binom{5}{2} = \dfrac{5 \cdot 4}{2} = 10$.
10 duplas.
básico
Numa reunião de 6 pessoas, cada uma aperta a mão de todas as outras uma vez. Quantos apertos de mão acontecem?

Ver resolução
Cada aperto corresponde a um par de pessoas, sem ordem.
$\binom{6}{2} = 15$.
15 apertos.
básico
Calcule $\binom{10}{8}$ da maneira mais curta que encontrar.

Ver resolução
Escolher os 8 que entram é escolher os 2 que ficam de fora.
$\binom{10}{8} = \binom{10}{2} = \dfrac{10 \cdot 9}{2} = 45$.
45.
básico
Quantos triângulos têm os três vértices entre 7 pontos marcados numa circunferência?

Ver resolução
Três pontos de uma circunferência nunca estão alinhados, e cada trio dá um triângulo, sem ordem.
$\binom{7}{3} = \dfrac{7 \cdot 6 \cdot 5}{6} = 35$.
35 triângulos.
médio
Uma comissão de 4 pessoas será escolhida entre 6 homens e 5 mulheres, com exatamente 2 mulheres. Quantas comissões são possíveis?

Ver resolução
As duas mulheres se escolhem em $\binom{5}{2} = 10$ maneiras, e os dois homens em $\binom{6}{2} = 15$.
$10 \cdot 15 = 150$.
150 comissões.
médio
Com as mesmas 11 pessoas, quantas comissões de 4 têm pelo menos uma mulher?

Ver resolução
Contamos o contrário. Comissões só de homens são $\binom{6}{4} = 15$, e comissões quaisquer são $\binom{11}{4} = 330$.
$330 - 15 = 315$.
315 comissões.
médio
Quantas diagonais tem um polígono convexo de 10 lados?

Ver resolução
Cada par de vértices determina um segmento, $\binom{10}{2} = 45$ segmentos, e 10 deles são lados.
$45 - 10 = 35$.
35 diagonais. Em geral, $\binom{n}{2} - n = \dfrac{n\,(n - 3)}{2}$.
médio
Na Mega-Sena, um jogo com 8 números marcados custa o mesmo que todas as apostas simples de 6 números que ele contém. Quantas são elas, e quanto custa o jogo, a R$ 6,00 a aposta simples?

Ver resolução
As apostas contidas são os grupos de 6 entre os 8 números marcados.
$\binom{8}{6} = \binom{8}{2} = 28$, e $28 \cdot 6 = 168$.
28 apostas e R$ 168,00, o valor da tabela da Caixa.
desafio
Dez pontos estão num plano, e só quatro deles estão alinhados, sobre uma mesma reta. Quantas retas distintas passam por pelo menos dois desses pontos?

Ver resolução
Se nenhum trio estivesse alinhado, cada par daria uma reta, $\binom{10}{2} = 45$.
Os $\binom{4}{2} = 6$ pares tirados dos quatro pontos alinhados dão todos a mesma reta, contada 6 vezes no lugar de uma.
$45 - 6 + 1 = 40$.
40 retas.
desafio
Num campeonato com 20 times, quantos jogos há se cada par de times se enfrenta uma vez? E se cada par joga duas vezes, uma no campo de cada time?

Ver resolução
Uma vez por par, a ordem não importa, $\binom{20}{2} = 190$.
Com dois jogos por par, o mandante distingue os jogos, e a ordem passa a importar, $A_{20,2} = 20 \cdot 19 = 380$.
190 e 380 jogos. A segunda conta é o dobro da primeira, porque cada par admite $2! = 2$ ordens.

PASSO 7

Quantos anagramas tem uma palavra com letras repetidas?

A palavra AMOR tem $4! = 24$ anagramas, porque as quatro letras são distintas. Em ARARA a conta muda. Se os três A fossem de cores diferentes, e os dois R também, haveria $5! = 120$ ordens, e trocar entre si os A, ou os R, não produz palavra nova. Cada anagrama aparece $3! \cdot 2! = 12$ vezes entre as 120 ordens, e os anagramas distintos são $120 / 12 = 10$.

Essa é a permutação com repetição. Com $n$ objetos, dos quais $a$ são de um tipo, $b$ de outro, e assim por diante, as ordens distintas são $n!$ dividido pelo produto dos fatoriais das repetições. A combinação do passo 6 é o caso de dois tipos, porque escolher as $k$ posições dos A entre $n$ é o mesmo que arrumar $k$ letras A e $n - k$ letras B.

A conta vale para objetos que não são letras. Um trem com 12 vagões, 4 vermelhos, 3 azuis, 3 verdes e 2 amarelos, pode ser montado de $\dfrac{12!}{4!\,3!\,3!\,2!} = 277{.}200$ maneiras quando só a cor distingue os vagões, a situação de uma questão do ENEM de 2019 listada no fim da aula. Na bancada, o acento de MATEMÁTICA é ignorado, e o Á conta como A.

$P_n^{\,a,\,b,\,\ldots} = \dfrac{n!}{a!\,b!\,\cdots}$$P_5^{\,3,\,2} = \dfrac{5!}{3!\,2!} = 10$Com $a + b + \ldots = n$. Com dois tipos, $P_n^{\,k,\,n-k} = \binom{n}{k}$.

Para conversar

Escolha ARARA e toque em "Distinguir as letras iguais". Quantas versões com índices aparecem para o anagrama atual, e o que elas têm em comum?
Percorra os anagramas de BANANA com "Próximo anagrama". Quantos começam com A, e por que são exatamente a metade?
Compare CONTAGEM com MATEMÁTICA. Qual tem mais letras, e qual tem mais anagramas, apesar das repetições?
Em ARARA, conte os anagramas escolhendo as 2 posições dos R entre as 5. Que número do passo 6 aparece?

Ordens das peças, n!

Divisor das repetições

Anagramas distintos

Anagrama atual

Exercícios do passo 7 10 questões · 4 básicas · 4 médias · 2 desafios

básico
Quantos anagramas tem a palavra OVO? Liste todos.

Ver resolução
$\dfrac{3!}{2!} = 3$.
3 anagramas, OVO, OOV e VOO.
básico
Quantos anagramas tem a palavra CASA?

Ver resolução
São 4 letras com o A repetido duas vezes.
$\dfrac{4!}{2!} = 12$.
12 anagramas.
básico
Quantos anagramas tem a palavra PAPAI?

Ver resolução
São 5 letras, com o P duas vezes e o A duas vezes.
$\dfrac{5!}{2!\,2!} = \dfrac{120}{4} = 30$.
30 anagramas.
básico
Uma moeda é lançada 5 vezes, e anotamos a sequência de caras (K) e coroas (C). Quantas sequências têm exatamente 2 caras?

Ver resolução
Cada sequência é um anagrama de KKCCC.
$\dfrac{5!}{2!\,3!} = 10 = \binom{5}{2}$.
10 sequências.
médio
Quantos anagramas de BANANA começam com B?

Ver resolução
Com o B fixo na frente, sobram ANANA, com três A e dois N.
$\dfrac{5!}{3!\,2!} = 10$.
10 anagramas.
médio
Ignorando o acento, quantos anagramas tem MATEMÁTICA? Quantos deles começam com M?

Ver resolução
São 10 letras, com A três vezes, M duas e T duas.
$\dfrac{10!}{3!\,2!\,2!} = \dfrac{3{.}628{.}800}{24} = 151{.}200$.
Com um M na frente sobram 9 letras, com A três vezes e T duas, e $\dfrac{9!}{3!\,2!} = 30{.}240$.
151.200 anagramas, 30.240 deles começando com M, exatamente um quinto, porque 2 das 10 letras são M.
médio
Para ir de casa até a escola, Lia anda 4 quadras para o leste e 3 para o norte, sem nunca voltar. Quantos trajetos diferentes ela pode fazer pelas ruas de um bairro quadriculado?

Ver resolução
Cada trajeto é uma sequência de 7 quadras, 4 marcadas L e 3 marcadas N, um anagrama de LLLLNNN.
$\dfrac{7!}{4!\,3!} = 35$.
35 trajetos.
médio
Uma fileira tem 8 lâmpadas, e 3 delas vão ficar acesas. De quantas maneiras isso pode acontecer? Faça a conta como combinação e como permutação com repetição.

Ver resolução
Como combinação, escolhemos as 3 posições acesas entre 8, $\binom{8}{3} = 56$.
Como permutação com repetição, arrumamos 3 lâmpadas acesas e 5 apagadas, $\dfrac{8!}{3!\,5!} = 56$.
56 maneiras, pelas duas contas.
desafio
Quantas soluções em inteiros não negativos tem a equação $x + y + z = 6$?

Ver resolução
Representamos uma solução por 6 bolinhas e 2 barras. As bolinhas antes da primeira barra dão $x$, as entre as barras dão $y$ e as depois da segunda dão $z$, e $\circ\circ|\circ|\circ\circ\circ$ é a solução $x = 2$, $y = 1$, $z = 3$.
Cada solução corresponde a um anagrama de 6 bolinhas e 2 barras, e cada anagrama a uma solução.
$\dfrac{8!}{6!\,2!} = 28$.
28 soluções.
desafio
Em quantos anagramas de ARARA os dois R não ficam lado a lado?

Ver resolução
São 10 anagramas ao todo. Para contar aqueles com os R juntos, colamos RR num bloco, que se arruma com os três A, e há 4 posições para o bloco.
$10 - 4 = 6$.
6 anagramas, ARARA, ARAAR, RARAA, RAARA, RAAAR e AARAR.

PASSO 8

Que padrões o triângulo de Pascal guarda?

Escrevendo os números $\binom{n}{k}$ em linhas, com $n = 0$ no alto e $k$ crescendo da esquerda para a direita, obtemos o triângulo de Pascal. Cada linha começa e termina em 1, e é simétrica, porque $\binom{n}{k} = \binom{n}{n-k}$.

Cada número do interior é a soma dos dois que estão logo acima dele, a relação de Stifel. A contagem explica por quê. Separamos um elemento entre os $n$. Os grupos de $k$ que o contêm são $\binom{n-1}{k-1}$, porque falta escolher os outros $k - 1$ entre os $n - 1$ restantes, e os grupos que não o contêm são $\binom{n-1}{k}$.

$\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$Stifel vale para $1 \le k \le n - 1$. A soma conta todos os subconjuntos de um conjunto com $n$ elementos.

A soma da linha $n$ é $2^n$. Num conjunto de $n$ elementos, cada elemento entra ou não entra num subconjunto, duas opções por elemento, e há $2^n$ subconjuntos, que a linha separa pelo número de elementos. Os números da linha são também os coeficientes de $(a + b)^n$, porque ao expandir o produto escolhemos $a$ ou $b$ em cada um dos $n$ fatores, e o termo $a^{n-k}\,b^k$ aparece $\binom{n}{k}$ vezes.

Numa grade, os caminhos que só andam para a direita ou para baixo, com $n$ passos dos quais $k$ para a direita, também são $\binom{n}{k}$, porque um caminho fica determinado pelas posições dos seus passos para a direita. É a mesma conta do trajeto de Lia, no exercício 7 do passo 7.

Para conversar

Toque numa casa do interior e compare o número com as duas casas destacadas acima dela. Repita em outra linha.
Some de cabeça uma linha inteira e compare com a leitura. Que potência aparece?
Toque em $\binom{6}{2}$ e percorra os caminhos. Quantos passos cada caminho tem, e quantos deles vão para a direita?
Na linha 7, onde fica o maior número? E nas linhas pares, onde ficam os maiores?

Linhas, até N

Casa escolhida

Stifel

Soma da linha

Caminho atual

Exercícios do passo 8 10 questões · 4 básicas · 4 médias · 2 desafios

básico
A linha 5 do triângulo é 1, 5, 10, 10, 5, 1. Escreva a linha 6.

Ver resolução
Pela relação de Stifel, cada número do interior é a soma dos dois de cima: $1 + 5 = 6$, $5 + 10 = 15$, $10 + 10 = 20$, e a simetria completa o resto.
1, 6, 15, 20, 15, 6, 1.
básico
Quanto dá a soma dos números da linha 10?

Ver resolução
A soma da linha $n$ é $2^n$.
$2^{10} = 1024$.
básico
Sabendo que $\binom{6}{2} = 15$ e $\binom{6}{3} = 20$, calcule $\binom{7}{3}$.

Ver resolução
Pela relação de Stifel, $\binom{7}{3} = \binom{6}{2} + \binom{6}{3} = 15 + 20$.
35.
básico
Quantos subconjuntos tem o conjunto $\{a, b, c, d, e\}$? Quantos deles têm exatamente 2 elementos?

Ver resolução
Cada um dos 5 elementos entra ou não entra, $2^5 = 32$.
Com 2 elementos, $\binom{5}{2} = 10$.
32 subconjuntos, 10 deles com 2 elementos. O vazio e o próprio conjunto estão entre os 32.
médio
Use a linha 4 do triângulo para expandir $(a + b)^4$.

Ver resolução
A linha 4 é 1, 4, 6, 4, 1.
$(a + b)^4 = a^4 + 4a^3 b + 6a^2 b^2$
$+\, 4a b^3 + b^4$.
médio
Qual é o coeficiente de $x^3$ na expansão de $(1 + x)^8$?

Ver resolução
O termo com $x^3$ aparece quando escolhemos $x$ em 3 dos 8 fatores e 1 nos outros 5.
$\binom{8}{3} = 56$.
56.
médio
Quantos subconjuntos de $\{1, 2, \ldots, 8\}$ têm pelo menos 2 elementos?

Ver resolução
Ao todo há $2^8 = 256$ subconjuntos. Tiramos o vazio, $\binom{8}{0} = 1$, e os 8 unitários, $\binom{8}{1} = 8$.
$256 - 1 - 8 = 247$.
247 subconjuntos.
médio
Numa grade, quantos caminhos que só andam para a direita ou para cima vão de $(0, 0)$ até $(5, 3)$ passando por $(2, 1)$?

Ver resolução
De $(0, 0)$ a $(2, 1)$ são 3 passos, 1 para cima, $\binom{3}{1} = 3$ caminhos.
De $(2, 1)$ a $(5, 3)$ são 5 passos, 2 para cima, $\binom{5}{2} = 10$ caminhos.
As duas metades se escolhem em etapas, $3 \cdot 10 = 30$.
30 caminhos, dos $\binom{8}{3} = 56$ que vão de $(0, 0)$ a $(5, 3)$.
desafio
Mostre que, para $n \ge 1$, $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \ldots \pm \binom{n}{n} = 0$. O que isso diz sobre os subconjuntos de um conjunto com $n$ elementos?

Ver resolução
Expandindo $(a + b)^n$ com $a = 1$ e $b = -1$, o lado esquerdo é exatamente a soma alternada, e o direito é $(1 - 1)^n = 0$.
A soma vale zero, e isso diz que um conjunto não vazio tem tantos subconjuntos com número par de elementos quanto com número ímpar, $2^{n-1}$ de cada tipo.
desafio
Calcule $\binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2}$ e compare com $\binom{6}{3}$. Use a relação de Stifel para explicar o resultado.

Ver resolução
A soma é $1 + 3 + 6 + 10 = 20 = \binom{6}{3}$.
Trocando $\binom{2}{2}$ por $\binom{3}{3}$, que também vale 1, Stifel dá $\binom{3}{3} + \binom{3}{2} = \binom{4}{3}$, depois $\binom{4}{3} + \binom{4}{2} = \binom{5}{3}$ e $\binom{5}{3} + \binom{5}{2} = \binom{6}{3}$.
20. No triângulo, a soma desce uma diagonal e termina na casa logo abaixo e ao lado da última parcela.

FECHAMENTO

Desafios

Passo 2 · Placas

Na troca da placa cinza pela Mercosul, o segundo algarismo vira uma letra de A a J. Quantas placas Mercosul têm a quinta posição entre A e J? Por que esse número coincide com o total de placas cinza, e quantas placas Mercosul nunca vêm de uma conversão?

Ver resolução

Com a quinta posição limitada a 10 letras, as posições LLLNLNN têm $26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10$
$= 26^3 \cdot 10^4 = 175{.}760{.}000$ opções.
É o total de placas cinza, porque a troca casa cada placa cinza com exatamente uma placa Mercosul desse tipo, e cada uma delas volta à sua placa cinza lendo a letra como algarismo.
As demais, $456{.}976{.}000 - 175{.}760{.}000$
$= 281{.}216{.}000$, têm na quinta posição uma letra de K a Z e ficam para veículos emplacados já no padrão novo.

Passos 2 e 5 · Repetição

Uma senha tem 6 caracteres escolhidos entre as 26 letras maiúsculas e os 10 algarismos. Que fração das senhas sobra quando o sistema proíbe repetir caracteres?

Ver resolução

Com repetição, $36^6 = 2{.}176{.}782{.}336$ senhas.
Sem repetição, $A_{36,6} = 36 \cdot 35 \cdot 34 \cdot 33 \cdot 32 \cdot 31$
$= 1{.}402{.}410{.}240$.
$\dfrac{1{.}402{.}410{.}240}{2{.}176{.}782{.}336} \approx 0{,}644$. Sobram cerca de 64% das senhas, e a regra, que talvez pareça deixar a senha mais segura, tira mais de um terço das possibilidades.

Passos 5 e 6 · Grupo com cargo

Uma turma de 10 alunos escolhe uma comissão de 4, e um dos 4 será o coordenador. Quantas comissões com coordenador são possíveis? Faça a conta de duas maneiras.

Ver resolução

Escolhendo primeiro o grupo e depois o coordenador dentro dele, $\binom{10}{4} \cdot 4 = 210 \cdot 4 = 840$.
Escolhendo primeiro o coordenador e depois os outros 3 entre os 9 restantes, $10 \cdot \binom{9}{3} = 10 \cdot 84 = 840$.
As duas ordens de escolha contam as mesmas comissões, 840.

Passo 6 · Mega-Sena

Um jogo de 8 números contém 28 apostas simples. Suponha que, entre os 8 marcados, estejam 5 dos 6 números sorteados. Quantas dessas 28 apostas fazem a quina, quantas fazem a quadra, e quantas não ganham nada?

Ver resolução

Os 8 marcados se dividem em 5 sorteados e 3 não sorteados, e cada aposta simples é um grupo de 6 entre eles.
Quina: os 5 sorteados e mais 1 dos 3 outros, $\binom{5}{5} \cdot \binom{3}{1} = 3$.
Quadra: 4 dos 5 sorteados e 2 dos 3 outros, $\binom{5}{4} \cdot \binom{3}{2} = 15$.
Com 3 acertos: $\binom{5}{3} \cdot \binom{3}{3} = 10$, sem prêmio.
$3 + 15 + 10 = 28$, e a sena fica de fora, porque o sexto número sorteado não foi marcado.

Passos 3 e 7 · Restrição

Quantos anagramas de BANANA não têm dois A lado a lado?

Ver resolução

Arrumamos primeiro as outras letras, B, N e N, em $\dfrac{3!}{2!} = 3$ ordens.
Cada ordem deixa 4 vãos, antes, entre e depois das letras, como em _B_N_N_. Os três A vão em vãos diferentes, para não ficarem vizinhos, e escolhemos 3 dos 4 vãos, $\binom{4}{3} = 4$.
$3 \cdot 4 = 12$, entre os 60 anagramas de BANANA.

Passos 6 e 8 · Caminho com obstáculo

Numa grade, um caminho vai de $(0, 0)$ até $(4, 4)$, só para a direita ou para cima. Quantos caminhos evitam o cruzamento $(2, 2)$, interditado por uma obra?

Ver resolução

Ao todo há $\binom{8}{4} = 70$ caminhos.
Pelo cruzamento passam $\binom{4}{2} \cdot \binom{4}{2} = 6 \cdot 6 = 36$, metade antes e metade depois dele.
$70 - 36 = 34$ caminhos evitam a obra.

Passos 1 e 8 · Subconjuntos

Uma pizzaria oferece 8 coberturas, e o cliente põe na pizza as que quiser, inclusive nenhuma. Quantas pizzas diferentes ela pode servir? Conte pelo princípio multiplicativo e pela linha 8 do triângulo.

Ver resolução

Cada cobertura entra ou não entra, 2 opções em 8 etapas, $2^8 = 256$.
Separando pela quantidade de coberturas, $\binom{8}{0} + \binom{8}{1} + \ldots + \binom{8}{8}$
$= 1 + 8 + 28 + 56 + 70$
$+\, 56 + 28 + 8 + 1 = 256$.
As duas contas dão 256 pizzas, a pizza sem cobertura incluída.

Questões no estilo ENEM

Escrevemos as cinco questões abaixo no formato do ENEM, com um texto-base tirado do cotidiano, um comando e cinco alternativas, e cada uma retoma um passo diferente da aula. Mais embaixo listamos questões reais da prova sobre contagem, que talvez sejam o melhor treino depois destas.

Princípios multiplicativo e aditivo · Passo 1
Uma lanchonete monta o pedido em duas etapas. Na primeira, o cliente escolhe um sanduíche, montado com um entre 3 pães e um entre 5 recheios, ou então uma entre 4 saladas prontas. Na segunda, ele escolhe um entre 3 sucos ou decide não levar suco.

Quantos pedidos diferentes a lanchonete pode atender?
1. 19
2. 57
3. 76
4. 80
5. 240
Ver resolução

Resposta: C.
Na primeira etapa, os sanduíches são $3 \cdot 5 = 15$, e as saladas são uma alternativa a eles, o que dá $15 + 4 = 19$ opções.
Na segunda etapa, os 3 sucos e a opção de não levar suco somam 4.
$19 \cdot 4 = 76$.
Os 19 param na primeira etapa, e os 57 esquecem que o cliente pode recusar o suco. Os 80 contam uma opção a mais na primeira etapa, e os 240 multiplicam as saladas, $3 \cdot 5 \cdot 4 \cdot 4$, como se o cliente levasse sanduíche e salada juntos.
Senhas · Passo 2
O aplicativo de um banco usava senhas de 6 algarismos. Numa atualização, a senha passou a ter 4 algarismos seguidos de 2 letras maiúsculas, escolhidas entre as 26 do alfabeto. Nos dois formatos, algarismos e letras podem se repetir.

O número de senhas possíveis no formato novo é quantas vezes o do formato antigo?
1. 0,52
2. 2,6
3. 6,76
4. 26
5. 67,6
Ver resolução

Resposta: C.
No formato antigo há $10^6$ senhas, e no novo, $10^4 \cdot 26^2$.
$\dfrac{10^4 \cdot 26^2}{10^6} = \dfrac{676}{100} = 6{,}76$.
Os 0,52 vêm de somar as letras, $\dfrac{26 + 26}{100}$, em vez de multiplicá-las. Os 2,6 correspondem a trocar uma só posição de algarismo por letra, e os 67,6 erram a potência de 10 da divisão. Os 26 valeriam se a senha nova acrescentasse uma letra aos 6 algarismos antigos. A troca de duas posições multiplica o total por $2{,}6 \cdot 2{,}6$.
Arranjos · Passo 5
Um concurso de fotografia escolhe, entre 12 finalistas, o primeiro, o segundo e o terceiro lugares, e dá ainda uma menção honrosa a um quarto finalista, diferente dos três premiados.

De quantas maneiras o resultado do concurso pode ser divulgado?
1. 495
2. 1320
3. 1980
4. 11.880
5. 20.736
Ver resolução

Resposta: D.
O pódio tem ordem, $12 \cdot 11 \cdot 10 = 1320$ maneiras, e a menção honrosa sai dos 9 que sobram.
$1320 \cdot 9 = 11{.}880$, que é o arranjo $A_{12,4}$, porque a menção honrosa funciona como um quarto lugar.
Os 495 são $\binom{12}{4}$ e ignoram a ordem dos prêmios, e os 1320 esquecem a menção. Os 1980 tratam o pódio como um grupo sem ordem, $\binom{12}{3} \cdot 9$, e os 20.736 são $12^4$, que deixaria a mesma pessoa receber mais de um prêmio.
Combinações · Passo 6
Sete amigos, 4 mulheres e 3 homens, vão sortear 3 deles para organizar a festa de fim de ano. O grupo combinou que a comissão precisa ter pelo menos um homem.

Quantas comissões diferentes atendem ao combinado?
1. 4
2. 18
3. 31
4. 35
5. 210
Ver resolução

Resposta: C.
A comissão não tem cargos, e a ordem não importa. Ao todo há $\binom{7}{3} = 35$ comissões, e as que não têm homem são as formadas só por mulheres, $\binom{4}{3} = 4$.
$35 - 4 = 31$.
Os 4 são as comissões proibidas, e os 18 contam só as comissões com exatamente um homem, $3 \cdot \binom{4}{2}$. Os 35 esquecem a exigência, e os 210 são $A_{7,3}$, que trata como diferentes as ordens de uma mesma comissão.
Permutação com repetição · Passo 7
Uma corredora monta o seu plano de treino para os próximos 9 dias, com um treino por dia. Serão 4 dias de corrida, 3 de musculação e 2 de natação, em qualquer ordem, e ela só distingue os dias pelo tipo de treino.

Quantos planos de treino diferentes ela pode montar?
1. 24
2. 288
3. 1260
4. 15.120
5. 362.880
Ver resolução

Resposta: C.
Cada plano é uma sequência de 9 treinos com 4 corridas, 3 musculações e 2 natações, uma permutação com repetição.
$\dfrac{9!}{4!\,3!\,2!} = \dfrac{362{.}880}{24 \cdot 6 \cdot 2} = \dfrac{362{.}880}{288} = 1260$.
Os 362.880 tratam os 9 dias de treino como todos diferentes, e os 15.120 descontam só as corridas, $\dfrac{9!}{4!}$. Os 288 são o divisor e os 24 são $4!$, contas do meio do caminho.

Questões reais do ENEM sobre este tema

As provas e os gabaritos oficiais ficam no site do INEP, onde podemos procurar cada questão pelo ano, pelo dia, pela cor do caderno e pelo número.

ENEM 2013, 2º dia, caderno azul, questão 138. Um banco troca as senhas de seis algarismos por senhas de seis caracteres com letras maiúsculas, minúsculas e algarismos, e a questão pede a razão entre os números de senhas dos dois sistemas.
ENEM 2014, 2º dia, caderno azul, questão 163. Um cliente de videolocadora aluga dois filmes por vez, combinando lançamentos de ação, comédia e drama, e precisamos contar as maneiras de pôr a estratégia em prática.
ENEM 2015, 2º dia, caderno azul, questão 164. Uma família de sete pessoas escolhe poltronas num voo quase lotado, e a questão pede a expressão que conta as maneiras de acomodá-la.
ENEM 2016, 2º dia, caderno azul, questão 147. Um técnico escolhe dois de dez tenistas para uma partida de exibição, sem que os dois sejam canhotos.
ENEM 2016, 2º dia, caderno azul, questão 168. Uma senha de site tem dois algarismos e duas letras, maiúsculas ou minúsculas, em qualquer posição, e precisamos da expressão que conta as senhas.
ENEM 2017, 2º dia, caderno azul, questão 177. Uma empresa compara cinco formatos de senha com letras e dígitos para atender cerca de um milhão de clientes sem passar do dobro disso.
ENEM 2017, 2º dia, caderno azul, questão 178. Num torneio de videogame cada jogador enfrenta todos os outros uma vez, e um quadro dá o número de partidas para até 7 jogadores.
ENEM 2018, 2º dia, caderno azul, questão 165. Uma montadora escolhe carros compactos e caminhonetes para dois estandes do Salão do Automóvel.
ENEM 2019, 2º dia, caderno azul, questão 156. Oito amigos, dois deles canhotos, formam quatro duplas de vôlei de praia sem que os canhotos fiquem juntos.
ENEM 2019, 2º dia, caderno azul, questão 171. Os 12 vagões de um trem de brinquedo têm quatro cores, e a questão pede, por meio de combinações, quantos trens diferentes podem ser montados.
ENEM 2020, 2º dia, caderno azul, questão 163. Anagramas da frase "I AM POTTER" com vogais e consoantes intercaladas.
ENEM 2022, 2º dia, caderno azul, questão 155. Uma pessoa quer comprar dois apartamentos de um mesmo andar, escolhidos pela posição em relação ao sol da manhã.
ENEM 2023, 2º dia, caderno azul, questão 160. Um aplicativo de investimentos compara três tipos de senha com letras, algarismos e caracteres especiais, sem repetição, pela probabilidade de ser descoberta ao acaso.
ENEM 2024, 2º dia, caderno azul, questão 180. Um hospital forma uma equipe de 5 médicos, com pelo menos 3 cardiologistas, entre 7 cardiologistas e 6 neurologistas.

Provas e gabaritos do ENEM no site do INEP →

Cola da aula

Princípio multiplicativo$n_1 \cdot n_2 \cdot \ldots \cdot n_k$

Princípio aditivocasos que não se sobrepõem somam

$k$ escolhas entre $n$, com repetição$n^k$

Fatorial$n! = n \cdot (n - 1)!$, com $0! = 1$

Permutação de $n$ objetos$P_n = n!$

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

Combinação$\dbinom{n}{k} = \dfrac{n!}{k!\,(n - k)!}$

Permutação com repetição$\dfrac{n!}{a!\,b!\,\cdots}$

Simetria$\dbinom{n}{k} = \dbinom{n}{n - k}$

Relação de Stifel$\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$

Soma da linha $n$$2^n$ subconjuntos

Contar pelo contráriototal menos os casos proibidos

Que conta usar
A ordem importa?	Pode repetir?	Conta
sim	sim	$n^k$, como nas senhas e placas
sim	não	$A_{n,k}$, como no pódio, e $n!$ quando $k = n$
não	não	$\binom{n}{k}$, como na comissão e na Mega-Sena
sim, todos os objetos	há objetos iguais	$\dfrac{n!}{a!\,b!\,\cdots}$, como nos anagramas

A ordem importa?	Pode repetir?	Conta
sim	sim	\(n^k\), como nas senhas e placas
sim	não	\(A_{n,k}\), como no pódio, e \(n!\) quando \(k = n\)
não	não	\(\binom{n}{k}\), como na comissão e na Mega-Sena
sim, todos os objetos	há objetos iguais	\(\dfrac{n!}{a!\,b!\,\cdots}\), como nos anagramas

De quantas maneiras dá para montar um lanche?

Para conversar

Quantas senhas e placas cabem num padrão?

Para conversar

De quantas maneiras uma fila pode se formar?

Para conversar

Quão depressa cresce \(n!\)?

Para conversar

E quando só alguns lugares vão ser ocupados?

Para conversar

E quando a ordem não importa?

Para conversar

Quantos anagramas tem uma palavra com letras repetidas?

Para conversar

Que padrões o triângulo de Pascal guarda?

Para conversar

Desafios

Questões no estilo ENEM

Questões reais do ENEM sobre este tema

Cola da aula