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 e são conjuntos finitos com e , e pede o número de funções que sejam sobrejetivas (isto é, atinjam todo elemento de ). 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 em é
pois cada um dos elementos de pode ser enviado a qualquer um dos alvos em .
Passo 3
Para impor a sobrejetividade, queremos excluir as funções que deixam de atingir pelo menos um elemento de . Denotemos, para cada , o conjunto
isto é, as funções que “perdem” o elemento . Então as funções não-sobrejetivas são aquelas que estão em .
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 é
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