Suponha que
. 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
Temos um conjunto
com
. Queremos:
– o número de todas as funções tais que não exista
com
;
– o número de todas as bijeções tais que não exista
com
.
– o número de todas as funções
– o número de todas as bijeções
Para (i) usaremos o princípio multiplicativo: em cada
proibimos apenas a imagem igual a
.
Para (ii) identificamos que são as derangements (permutations sem pontos fixos) e usamos o princípio de inclusão-exclusão.
Para (ii) identificamos que são as derangements (permutations sem pontos fixos) e usamos o princípio de inclusão-exclusão.
Passo 2
Para qualquer
, ao exigir
há
escolhas possíveis de imagem. Como as escolhas em pontos diferentes de
são independentes, pelo princípio multiplicativo o total de funções sem ponto fixo é
Passo 3
Entre as bijeções de
em si existem
no total. Para contar as que não fixam nenhum elemento aplicamos inclusão-exclusão assim:
– Se fixarmos um determinado conjunto de elementos de
, o restante pode permutar livremente em
maneiras;
– Há maneiras de escolher quais
elementos ficariam fixos;
– Pelo princípio de inclusão-exclusão, o número de permutações sem nenhum ponto fixo é
– Se fixarmos um determinado conjunto de
– Há
– Pelo princípio de inclusão-exclusão, o número de permutações sem nenhum ponto fixo é
que também pode ser escrito como
Resposta
O número de funções
sem solução para
é
O número de bijeções
sem solução para
(derangements) é