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
Para o caso que m=n existe uma fórmula muito mais simples. Qual? (Dica: se não souber responder, tente ítem (d) primeiro.)

Passo 1

Beleza, vamos lá! O exercício fala sobre o princípio da inclusão-exclusão, que a gente usa pra contar quantas funções são sobrejetivas (ou seja, que todo elemento do conjunto de chegada é atingido por pelo menos um elemento do conjunto de partida). A gente tem dois conjuntos: A com m elementos e B com n elementos, onde m >= n. A pergunta quer saber qual é a fórmula mais simples para o caso quando m = n.

Passo 2

Primeiro, quando m = n, estamos lidando com funções de um conjunto com n elementos para outro também com n elementos. Nesse cenário, uma função pode ser sobrejetiva e injeção ao mesmo tempo, o que chamamos de bijeção. Então, contar funções sobrejetivas nesse caso é o mesmo que contar bijeções.

Passo 3

Agora, vamos lembrar da teoria: o número de bijeções entre dois conjuntos com n elementos é dado pelo fatorial de n, representado por n!. O fatorial de um número é o produto de todos os inteiros positivos até esse número. Por exemplo, 3! = 3 times 2 times 1 = 6.

Resposta

A fórmula mais simples para o caso m = n é n!.

Exercícios relacionados