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
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:
n^m - binomn1(n-1)^m + binomn2(n-2)^m - cdots + (-1)^n-1 binomnn-1 cdot 1^m
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 é:
  • $ m = n = 1 $: 1 função
  • $ m = n = 2 $: 2 funções
  • $ m = n = 3 $: 6 funções
  • $ m = n = 4 $: 24 funções

Exercícios relacionados