Suponha #A
. Quantas são as funções
para as quais a equação
não possui solução? Quantas são as funções
bijetoras para as quais a equação
não possui solução?
Passo 1
O problema trata de um conjunto finito
com
e pede dois contagens de funções
que não tenham solução para
(isto é, sem ponto fixo).
Conteúdos usados:
Conteúdos usados:
- Princípio fundamental da contagem (regra do produto).
- Princípio da inclusão–exclusão para contar bijeções sem ponto fixo (derangements).
Passo 2
Queremos todas as funções
tais que, para cada
,
.
Pelo princípio do produto, para cada elemento há
escolhas de imagem (todas as opções em
exceto
mesmo). Como as escolhas são independentes para cada um dos
elementos, o total é
Pelo princípio do produto, para cada elemento
Passo 3
Agora queremos contar as bijeções
sem ponto fixo (derangements). Denotemos por
esse número.
Pelo princípio da inclusão–exclusão, se escolhermos exatamente pontos que ficam fixos, há
maneiras de escolher quais são eles e
permutações dos restantes. Então
Pelo princípio da inclusão–exclusão, se escolhermos exatamente
Uma forma alternativa de escrever é
Resposta
A quantidade de todas as funções
sem solução de
é
A quantidade de bijeções
sem ponto fixo é