Questão 2

Considere os conjuntos $X = \{x_1,x_2,x_3,x_4,x_5\}$ e $Y = \{1,2,3,4,5,6,7,8\}$. Quantas funções injetivas $f : X \to Y$ existem, tais que, para dois elementos previamente fixados $x_i$ e $x_j \in X$, $|f(x_i) - f(x_j)| \neq 1$?

A restrição incide sobre dois elementos fixos $x_i$ e $x_j$ de $X$: as imagens desses dois não podem ser inteiros consecutivos. Contar diretamente exigiria separar casos; vamos usar a contagem complementar: do total de funções injetivas subtraímos aquelas em que $|f(x_i)-f(x_j)| = 1$.

Total de funções injetivas: pelo Princípio Fundamental da Contagem, escolhemos as imagens dos $5$ elementos de $X$ sem repetição entre os $8$ elementos de $Y$, ou seja, um arranjo:
$$A_{8,5} = 8\cdot 7\cdot 6\cdot 5\cdot 4 = 6720 .$$

Casos proibidos ($|f(x_i)-f(x_j)| = 1$): devemos escolher, para o par ordenado $\left(f(x_i),\,f(x_j)\right)$, dois inteiros consecutivos de $Y$.

• Pares de valores consecutivos em $\{1,\dots,8\}$: $\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\}$, ou seja, $7$ pares.

• Cada par pode ser atribuído a $(x_i, x_j)$ em $2$ ordens (por exemplo, $f(x_i)=3$ e $f(x_j)=4$, ou $f(x_i)=4$ e $f(x_j)=3$).

Logo há $7\cdot 2 = 14$ maneiras de atribuir imagens a $x_i$ e $x_j$. Fixadas essas duas imagens, restam $3$ elementos de $X$ para receber imagens distintas entre os $8-2 = 6$ valores de $Y$ ainda livres:
$$A_{6,3} = 6\cdot 5\cdot 4 = 120 .$$

Portanto, o número de funções injetivas que violam a condição é
$$14 \cdot 120 = 1680 .$$

Contagem final: subtraindo do total,
$$N = 6720 - 1680 = 5040 .$$

Resolução alternativa

Pelo primeiro Lema de Kaplansky podemos escolher os elementos da imagem de $x_i$ e $x_j$ — isto é, os dois valores não consecutivos de $Y$. Isso pode ser feito de
$$f(8,2) = C_{7,2} = 21$$
maneiras. Permutando esses dois elementos entre $x_i$ e $x_j$: $2! = 2$.

Fixadas essas duas imagens, restam $3$ elementos de $X$ para receber imagens distintas entre os $8-2 = 6$ valores de $Y$ ainda livres:
$$A_{6,3} = 6\cdot 5\cdot 4 = 120 .$$

Contagem final:
$$N = 120 \cdot 2 \cdot 21 = 5040 .$$