Em uma cidade de n+1 habitantes, uma pessoa conta um boato a uma segunda, a qual, por sua vez, o repete a uma terceira, etc. A cada passo a pessoa que recebe o boato é escolhida aleatoriamente dentre as n pessoa disponíveis. Ache o número de resultados em que o boato seja transmitido r vezes sem que seja repetido a nenhuma pessoa.

Passo 1

Beleza, vamos lá! O enunciado diz o seguinte: numa cidade com pessoas, alguém começa um boato e passa pra outra pessoa, que passa pra outra, e assim por diante, fazendo exatamente transmissões. A cada passo, a pessoa que vai ouvir é sorteada aleatoriamente entre as possíveis (a gente não conta quem tá falando). A gente quer contar de quantas formas isso pode acontecer sem nunca repetir quem já ouviu o boato antes.
Conteúdo: combinatória básica, mais precisamente o princípio fundamental da contagem e permutações simples. Vamos precisar usar a ideia de “multiplicar as opções de cada etapa” e reconhecer que isso dá uma permutação de elementos tomados a .

Passo 2

Primeiro, pense no passo 1 de transmissão:
  • O boato parte de quem começa (fixo) e vai pra mais uma pessoa.
  • Quem recebe pode ser qualquer uma das pessoas restantes.
    Logo, temos opções para a 1ª transmissão.

Passo 3

Agora, na 2ª transmissão:
  • Quem acabou de ouvir (chama ele de “locutor atual”) não pode ser escolhido de novo, então a gente olha só pras outras pessoas.
  • Dessas possíveis, já teve uma que ouviu na transmissão 1 e não pode repetir.
    Isso deixa opções para a 2ª transmissão.

Passo 4

Repetindo essa lógica, na k-ésima transmissão (até chegar em ):
  • O locutor atual não conta, e também não podem ser escolhidas nenhuma das já ouvidas antes.
  • Então, no passo , as opções restantes são .

Passo 5

Pela regra do produto (princípio fundamental da contagem), o total de maneiras sem repetir é:
n times (n-1) times (n-2) times cdots times l(n-(r-1)r)
Isso é exatamente a permutação de P(n,r);=;n!(n-r)! elementos tomados a , que escrevemos como

Resposta

boxedn!(n-r)!

Exercícios relacionados