Seja X um conjunto com n elementos. Determine o número de funções injetivas f: Ip X.

Passo 1

O enunciado diz que temos um conjunto X com n elementos e o domínio é Ip, um conjunto com p elementos. Precisamos contar quantas funções fcolon Ipto X são injetivas. Para isso vamos usar o princípio fundamental da contagem, atribuindo imagens distintas a cada um dos p elementos do domínio.

Passo 2

Escolhemos a imagem de cada elemento de Ip de forma que não haja repetições. Para o primeiro ponto do domínio há n opções de imagem em X; para o segundo, como não podemos repetir, restam n-1 opções; para o terceiro, n-2 opções; e assim por diante, até o p-ésimo, que terá n-(p-1) opções. Pelo princípio multiplicativo, o total de funções injetivas é
ncdot (n-1)cdot (n-2)cdotsl(n-(p-1)r)

Passo 3

Reconhecemos esse produto como a permutação de n elementos tomados p a p, que pode ser escrito em termos de fatoriais como
n!(n-p)!

Resposta

n!(n-p)!

Exercícios relacionados