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

Passo 1

O enunciado diz que X e Y são conjuntos finitos com lvert Xrvert = n e lvert Yrvert = m, e pede o número de funções fcolon Xto Y que sejam sobrejetivas (isto é, atinjam todo elemento de Y). Para resolver isso vamos usar o Princípio da Inclusão-Exclusão, que é a ferramenta clássica para contar funções que satisfazem condições “de imagem” como essa.

Passo 2

Primeiro, sem nenhuma restrição, o total de funções de X em Y é
m^n,
pois cada um dos n elementos de X pode ser enviado a qualquer um dos m alvos em Y.

Passo 3

Para impor a sobrejetividade, queremos excluir as funções que deixam de atingir pelo menos um elemento de Y. Denotemos, para cada iin Y, o conjunto
Ai = ,fcolon Xto Y mid inotin f(X),
isto é, as funções que “perdem” o elemento i. Então as funções não-sobrejetivas são aquelas que estão em cupiin YAi.

Passo 4

Pelo Princípio da Inclusão-Exclusão, o número de funções que deixam de atingir pelo menos um elemento de Y é
sumk=1^m (-1)^,k-1 sumsubstackIsubseteq Y|I|=k l|capiin IAir|
Mas capiin IAi é o conjunto de funções que não atingem nenhum dos k alvos em I, logo seu tamanho é (m-k)^n. Como há binom mk maneiras de escolher I, a fórmula vira
l|cupiin YAir| = sumk=1^m(-1)^,k-1binom mk (m-k)^n

Passo 5

O número de funções sobrejetivas é então o total m^n menos as não-sobrejetivas:
sumk=0^m(-1)^kbinom mk (m-k)^n,
onde o termo k=0 é binom m0(m-0)^n = m^n, de modo que a soma já dá diretamente o valor desejado.

Passo 6

Em resumo, o número de funções fcolon Xto Y sobrejetivas é
boxed sumk=0^m(-1)^kbinom mk,(m-k)^n
Alternativamente, identificando com os números de Stirling de segunda espécie !nbrace m, obtém-se também
m!,nbrace m

Resposta

sumk=0^m(-1)^kbinom mk,(m-k)^n

Exercícios relacionados