Questão 18. Suponha que o conjunto
possua
elementos. Quantas são as funções
para as quais a equação
não possui solução? Quantas são asa funções
bijetoras para as quais a equação
па̃о possui solução?
Passo 1
O enunciado diz que
é um conjunto com
elementos e pede duas contagens:
- Quantas funções
não têm solução da equação (isto é, sem pontos fixos). - Quantas funções
são bijetoras e também não têm pontos fixos.
O conteúdo envolve contagem simples de funções e, no caso bijetoras, uso do princípio da inclusão–exclusão para permutações.
Passo 2
Para qualquer função
que não permita
, cada
deve ser enviado em algum elemento distinto de si mesmo. Assim, para cada
há exatamente
escolhas, e como as escolhas são independentes em cada um dos
elementos, o total é
Passo 3
Quando exigimos que
seja bijetora, estamos contando permutações de
sem pontos fixos, isto é, derangements. Pelo princípio da inclusão–exclusão, o número de permutações sem ponto fixo é
Aqui
é a quantidade de permutações que fixam um subconjunto de
pontos, e alternamos sinais conforme inclusão–exclusão. Uma forma equivalente de escrever esse somatório é
que é a fórmula clássica de dérangements.
Resposta
Funções
sem solução de
:
Funções bijetoras
sem ponto fixo (derangements):