(OBM-08) Determine a quantidade de funções f:\{1,2,3,4,5\} \rightarrow\{1,2,3,4,5\} tais que f(f(x))=f(x) para todo x \in\{1,2,3,4,5\}.

Solução:

Para que f(f(x))=f(x) então a imagem de f deverá só conter pontos fixos. Utilizando esse fato temos:
Com 5 pontos fixos na imagem teremos 1 função possivel.
Com 4 pontos fixos na imagem teremos \binom{5}{1} 4=20 funções
Com 3 pontos fixos na imagem teremos \binom{5}{2} \cdot 3^{2}=90 funções
Com 2 pontos fixos na imagem teremos \binom{5}{3} \cdot 2^{3}=80 funções
Com I ponto fixo na imagem teremos \binom{5}{4} \cdot 1^{4}=5 funções

Passo 1

O enunciado pede o número de funções
\;f : \{1,2,3,4,5\} \to \{1,2,3,4,5\}
que satisfazem
\;f(f(x)) = f(x)
para todo x.
Esse tipo de função é chamado de idempotente, e vamos contar quantas existem usando ideias de combinatória.

Passo 2

Se y está na imagem de f, isto é, y = f(x) para algum x, então
f(y) = f\bigl(f(x)\bigr) = f(x) = y.
Logo todo elemento da imagem de f é um ponto fixo (satisfaz f(y)=y).

Passo 3

Seja k o número de pontos fixos, isto é, k = |\mathrm{Im}(f)|. Para construir f com exatamente k pontos fixos:
  1. Escolhemos quais k elementos de \{1,2,3,4,5\} serão pontos fixos. Há \binom{5}{k}maneiras de escolher esse conjunto I.
  2. Em cada ponto de I, forçamos f(i)=i.
  3. Para os 5-k elementos que não estão em I, cada um pode ser mapeado para qualquer elemento de I, totalizando k^{\,5-k}possibilidades.
    Portanto, para um k fixo, temos
\binom{5}{k}\,k^{\,5-k}
funções idempotentes com exatamente k pontos fixos.

Passo 4

Agora somamos sobre k=1,2,3,4,5:
\binom{5}{1}1^{4}=5
\binom{5}{2}2^{3}=80
\binom{5}{3}3^{2}=90
\binom{5}{4}4^{1}=20
\binom{5}{5}5^{0}=1
Somando esses valores, obtemos
5 + 80 + 90 + 20 + 1 = 196.

Resposta

196

Exercícios de Livros Relacionados