Seja
um conjunto com
elementos. Determine o número de funções injetivas
.
Passo 1
O enunciado diz que temos um conjunto
com
elementos e o domínio é
, um conjunto com
elementos. Precisamos contar quantas funções
são injetivas. Para isso vamos usar o princípio fundamental da contagem, atribuindo imagens distintas a cada um dos
elementos do domínio.
Passo 2
Escolhemos a imagem de cada elemento de
de forma que não haja repetições. Para o primeiro ponto do domínio há
opções de imagem em
; para o segundo, como não podemos repetir, restam
opções; para o terceiro,
opções; e assim por diante, até o
-ésimo, que terá
opções. Pelo princípio multiplicativo, o total de funções injetivas é
Passo 3
Reconhecemos esse produto como a permutação de
elementos tomados
a
, que pode ser escrito em termos de fatoriais como