Suponha que |A|=n. 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 as funções f: A \rightarrow A bijetoras para as quais a equação f(x)=x não possui solução?

Passo 1

Temos um conjunto A com \lvert A\rvert = n. Queremos:
– o número de todas as funções f\colon A\to A tais que não exista x\in A com f(x)=x;
– o número de todas as bijeções f\colon A\to A tais que não exista x\in A com f(x)=x.
Para (i) usaremos o princípio multiplicativo: em cada x proibimos apenas a imagem igual a x.
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 x\in A, ao exigir f(x)\neq x n-1 escolhas possíveis de imagem. Como as escolhas em pontos diferentes de A são independentes, pelo princípio multiplicativo o total de funções sem ponto fixo é
(n-1)^n.

Passo 3

Entre as bijeções de A em si existem n! no total. Para contar as que não fixam nenhum elemento aplicamos inclusão-exclusão assim:
– Se fixarmos um determinado conjunto de k elementos de A, o restante pode permutar livremente em (n-k)! maneiras;
– Há \binom{n}{k} maneiras de escolher quais k elementos ficariam fixos;
– Pelo princípio de inclusão-exclusão, o número de permutações sem nenhum ponto fixo é
\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)!
que também pode ser escrito como
n!\,\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

Resposta

O número de funções f\colon A\to A sem solução para f(x)=x é
(n-1)^n.
O número de bijeções f\colon A\to A sem solução para f(x)=x (derangements) é
\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)! \;=\; n!\,\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

Exercícios relacionados