(OBM-08) Determine a quantidade de funções
tais que
para todo
.
Solução:
Para que
então a imagem de
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
funções
Com 3 pontos fixos na imagem teremos
funções
Com 2 pontos fixos na imagem teremos
funções
Com I ponto fixo na imagem teremos
funções
Com 5 pontos fixos na imagem teremos 1 função possivel.
Com 4 pontos fixos na imagem teremos
Com 3 pontos fixos na imagem teremos
Com 2 pontos fixos na imagem teremos
Com I ponto fixo na imagem teremos
Passo 1
O enunciado pede o número de funções
que satisfazem
para todo .
Esse tipo de função é chamado de idempotente, e vamos contar quantas existem usando ideias de combinatória.
que satisfazem
para todo
Esse tipo de função é chamado de idempotente, e vamos contar quantas existem usando ideias de combinatória.
Passo 2
Se
está na imagem de
, isto é,
para algum
, então
Logo todo elemento da imagem de
é um ponto fixo (satisfaz
).
Passo 3
Seja
o número de pontos fixos, isto é,
. Para construir
com exatamente
pontos fixos:
- Escolhemos quais
elementos de serão pontos fixos. Há maneiras de escolher esse conjunto . - Em cada ponto de
, forçamos . - Para os
elementos que não estão em , cada um pode ser mapeado para qualquer elemento de , totalizando possibilidades.
Portanto, para umfixo, temos
funções idempotentes com exatamente
pontos fixos.
Passo 4
Agora somamos sobre
:
Somando esses valores, obtemos
Resposta
196