O princípio de inclusão-exclusão pode ser usado para calcular o número de funções sobrejetivas entre um conjunto de elementos para um conjunto de elementos, com . A fórmula resultante é
Confirme a resposta do item anterior para m=n=1,2,3 e 4 . Mostre seus cálculos.
Passo 1
Beleza, vamos resolver esse exercício juntos! A questão fala sobre funções sobrejetivas entre dois conjuntos, usando o Princípio da Inclusão-Exclusão. A gente precisa calcular quantas funções do conjunto $ A $ com $ m $ elementos para o conjunto $ B $ com $ n $ elementos são sobrejetivas, ou seja, que todo elemento de $ B $ é atingido por pelo menos um elemento de $ A $. Vamos usar a fórmula que utiliza esse princípio para conferir os resultados quando $ m = n = 1, 2, 3 $ e $ 4 $.
Passo 2
Primeiro, vamos entender a fórmula que vamos usar:
Essa fórmula aplica o Princípio da Inclusão-Exclusão para contar o número de funções que cobrem todos os elementos de $ B $. Cada termo da soma ajusta a contagem para evitar contar múltiplas vezes funções que não atingem todos os elementos.
Vamos calcular para cada caso de $ m = n = 1, 2, 3, 4 $.
Passo 3
Caso 1: $ m = n = 1 $
Aqui, $ A $ e $ B $ têm apenas um elemento cada. Vamos aplicar a fórmula:
m = n = 1
Explicação:
$ 1^{1} = 1 $: Total de funções possíveis.
$ \binom{1}{1}(0)^{1} = 0 $: Subtrai funções que não atingem nenhum elemento, mas como só tem um, não tem o que subtrair além da própria função.
Passo 4
Caso 2: $ m = n = 2 $
Agora, $ A $ e $ B $ têm dois elementos cada. Aplicando a fórmula:
m = n = 2
Explicação:
$ 2^{2} = 4 $: Total de funções possíveis.
$ \binom{2}{1}(1)^{2} = 2 \cdot 1 = 2 $: Subtrai as funções que não atingem um dos dois elementos de $ B $.
$ \binom{2}{2}(0)^{2} = 1 \cdot 0 = 0 $: Adiciona de volta as funções que não atingem ambos, mas como isso é impossível, é zero.
Passo 5
Caso 3: $ m = n = 3 $
Agora, $ A $ e $ B $ têm três elementos cada. Vamos aplicar a fórmula:
m = n = 3
Explicação:
$ 3^{3} = 27 $: Total de funções possíveis.
$ \binom{3}{1}(2)^{3} = 3 \cdot 8 = 24 $: Subtrai as funções que não atingem um dos três elementos.
$ \binom{3}{2}(1)^{3} = 3 \cdot 1 = 3 $: Adiciona de volta as funções que não atingem dois elementos.
$ \binom{3}{3}(0)^{3} = 1 \cdot 0 = 0 $: Subtrai as funções que não atingem nenhum, mas isso é zero.
Passo 6
Caso 4: $ m = n = 4 $
Finalmente, $ A $ e $ B $ têm quatro elementos cada. Aplicando a fórmula:
m = n = 4
Calculando cada termo:
$ 4^{4} = 256 $
$ \binom{4}{1}(3)^{4} = 4 \cdot 81 = 324 $
$ \binom{4}{2}(2)^{4} = 6 \cdot 16 = 96 $
$ \binom{4}{3}(1)^{4} = 4 \cdot 1 = 4 $
$ \binom{4}{4}(0)^{4} = 1 \cdot 0 = 0 $
Agora, somando:
A
Explicação:
$ 4^{4} = 256 $: Total de funções possíveis.
$ \binom{4}{1}(3)^{4} = 324 $: Subtrai as funções que não atingem um dos quatro elementos.
$ \binom{4}{2}(2)^{4} = 96 $: Adiciona de volta as funções que não atingem dois elementos.
$ \binom{4}{3}(1)^{4} = 4 $: Subtrai as funções que não atingem três elementos.
$ \binom{4}{4}(0)^{4} = 0 $: Adiciona de volta as funções que não atingem nenhum, mas isso é zero.
Resposta
Portanto, o número de funções sobrejetivas para cada caso é: