Sejam e conjuntos finitos com e elementos, respectivamente. Determine quantos elementos tem os seguintes conjuntos de funções:
é função injetiva })

Passo 1

O enunciado pede o número de funções injetivas fcolon Xto Y onde lvert Xrvert = n e lvert Yrvert = m. O conteúdo envolve contagem de funções e o princípio multiplicativo em combinatória, mais especificamente arranjos.

Passo 2

Para que exista uma função injetiva de X em Y, precisamos de imagens distintas para cada elemento de X. Isso só é possível se o número de elementos de X não ultrapassar o de Y, ou seja, é necessário
n <= m
Se n>m, não há como atribuir imagens distintas e o total de funções injetivas é zero.

Passo 3

Supondo n <= m, vamos contar quantas funções injetivas há. Enumeramos os elementos de X como x1,x2,dots,xn. Para definir f injetiva, escolhemos:
  • para x1: ,m possibilidades de imagem em Y,
  • para x2: ,m-1 possibilidades (não pode repetir a imagem de x1),
  • para x3: ,m-2 possibilidades,
    ···
  • para xn: ,m-(n-1) possibilidades.
Pelo princípio multiplicativo, o total é
m times (m-1) times (m-2) times cdots times l(m-(n-1)r)

Passo 4

O produto acima é exatamente o número de arranjos de m elementos tomados n a n, denotado por P(m,n). Em termos de fatoriais,
P(m,n) = m,(m-1),(m-2),cdots,(m-n+1) = m!(m-n)!

Resposta

Se n>m, não existe função injetiva e o total é 0.
Se n<= m, o número de funções injetivas é
m!(m-n)!

Exercícios relacionados