Questão 18. Suponha que o conjunto A possua n elementos. Quantas são as funções f: A \rightarrow A para as quais a equação f(x)=x não possui solução? Quantas são asa funções f: A \rightarrow A bijetoras para as quais a equação f(x)=x па̃о possui solução?

Passo 1

O enunciado diz que A é um conjunto com n elementos e pede duas contagens:
  1. Quantas funções f\colon A\to A não têm solução da equação f(x)=x (isto é, sem pontos fixos).
  2. Quantas funções f\colon A\to A 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 f\colon A\to A que não permita f(x)=x, cada x\in A deve ser enviado em algum elemento distinto de si mesmo. Assim, para cada x há exatamente n-1 escolhas, e como as escolhas são independentes em cada um dos n elementos, o total é
(n-1)^{n}.

Passo 3

Quando exigimos que f seja bijetora, estamos contando permutações de A sem pontos fixos, isto é, derangements. Pelo princípio da inclusão–exclusão, o número de permutações sem ponto fixo é
\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)!.
Aqui \binom{n}{k}(n-k)! é a quantidade de permutações que fixam um subconjunto de k pontos, e alternamos sinais conforme inclusão–exclusão. Uma forma equivalente de escrever esse somatório é
n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!},
que é a fórmula clássica de dérangements.

Resposta

Funções f\colon A\to A sem solução de f(x)=x:
(n-1)^{n}.
Funções bijetoras f\colon A\to A sem ponto fixo (derangements):
\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)! \;=\; n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}.

Exercícios relacionados