Suponha #A =n. Quantas são as funções f: A A para as quais a equação f(x)=x não possui solução? Quantas são as funções f: A A bijetoras para as quais a equação f(x)=x não possui solução?

Passo 1

O problema trata de um conjunto finito A com #A=n e pede dois contagens de funções fcolon Ato A que não tenham solução para f(x)=x (isto é, sem ponto fixo).
Conteúdos usados:
  1. Princípio fundamental da contagem (regra do produto).
  2. Princípio da inclusão–exclusão para contar bijeções sem ponto fixo (derangements).

Passo 2

Queremos todas as funções fcolon Ato A tais que, para cada xin A, f(x)neq x.
Pelo princípio do produto, para cada elemento x ,n-1 escolhas de imagem (todas as opções em A exceto x mesmo). Como as escolhas são independentes para cada um dos n elementos, o total é
(n-1)^n

Passo 3

Agora queremos contar as bijeções fcolon Ato A sem ponto fixo (derangements). Denotemos por Dn esse número.
Pelo princípio da inclusão–exclusão, se escolhermos exatamente k pontos que ficam fixos, há binomnk maneiras de escolher quais são eles e (n-k)! permutações dos restantes. Então
Dn ;=;sumk=0^n(-1)^kbinomnk(n-k)!
Uma forma alternativa de escrever é
Dn ;=;n!sumk=0^n(-1)^kk!

Resposta

A quantidade de todas as funções fcolon Ato A sem solução de f(x)=x é
(n-1)^n
A quantidade de bijeções fcolon Ato A sem ponto fixo é
sumk=0^n(-1)^kbinomnk(n-k)! ;=; n!sumk=0^n(-1)^kk!

Exercícios de Livros Relacionados