O princípio de inclusão-exclusão pode ser usado para calcular o número de funções sobrejetivas entre um conjunto A de m elementos para um conjunto B de n elementos, com m >= n. A fórmula resultante é
n^m-underbracebinomn1(n-1)^m+binomn2(n-2)^m-cdots+(-1)^n-1 C(n, n-1) cdot 1^m
Calcule o número exato para m=5, n=4

Passo 1

Beleza, vamos resolver esse exercício juntos! A gente precisa calcular o número de funções sobrejetivas de um conjunto $ A $ com $ m = 5 $ elementos para um conjunto $ B $ com $ n = 4 $ elementos. Para isso, vamos usar o Princípio de Inclusão-Exclusão, que é uma técnica de contagem na combinatória. Vamos precisar entender um pouquinho de como esse princípio funciona para não perder o fio da meada.

Passo 2

Primeiro, vamos lembrar que uma função sobrejetiva é aquela em que todos os elementos de $ B $ são atingidos por pelo menos um elemento de $ A $. Para contar todas as funções possíveis de $ A $ para $ B $, sem nenhuma restrição, usamos a fórmula $ n^m $.
Aqui, $ n = 4 $ e $ m = 5 $, então:
B
Ou seja, existem 1024 funções possíveis de $ A $ para $ B $ sem considerar a sobrejetividade.

Passo 3

Agora, queremos excluir as funções que não são sobrejetivas, ou seja, aquelas que faltam pelo menos um elemento no conjunto $ B $. Para isso, usamos o Princípio de Inclusão-Exclusão.
Primeiro, calculamos quantas funções faltam exatamente 1 elemento de $ B $. Para escolher qual elemento falta, usamos a combinação $ \binom{4}{1} $, que é:
B
Cada escolha resulta em funções que mapeiam para os outros $ 3 $ elementos, então temos $ (4-1)^5 = 3^5 = 243 $.
Multiplicando:
B

Passo 4

Depois, precisamos voltar os casos que foram subtraídos duas vezes. Ou seja, funções que faltam exatamente 2 elementos de $ B $.
Escolhemos quais 2 elementos faltam com $ \binom{4}{2} $:
B
E as funções mapeiam para os outros $ 2 $ elementos, então $ (4-2)^5 = 2^5 = 32 $.
Multiplicando:
binom42

Passo 5

Por último, ajustamos novamente para não ter sobrecontagem. Calculamos as funções que faltam exatamente 3 elementos de $ B $.
Escolhemos quais 3 elementos faltam com $ \binom{4}{3} $:
B
E as funções mapeiam para o $ 1 $ elemento restante, então $ (4-3)^5 = 1^5 = 1 $.
Multiplicando:
binom43

Resposta

Agora, juntando tudo usando o Princípio de Inclusão-Exclusão:
4^5 - binom41 times 3^5 + binom42 times 2^5 - binom43 times 1^5 = 1024 - 972 + 192 - 4 = 240
Então, o número exato de funções sobrejetivas de $ A $ para $ B $ é 240.

Exercícios relacionados