Exercício 0.9 Quantas são as injeções de
em
? E quantas são as sobrejeções de
em
?
Passo 1
O enunciado faz duas perguntas distintas:
- Quantas são as injeções de
em ? - Quantas são as sobrejeções de
em ?
Informações relevantes fornecidas pelo enunciado:
- No primeiro item, o conjunto domínio tem
elementos e o conjunto contradomínio tem elementos. - No segundo item, o conjunto domínio tem
elementos e o conjunto contradomínio tem elementos.
Passo 2
Definição e ideia para contar injeções (essa é a parte teórica que vamos usar para o primeiro item).
- Uma função
é injetora (injeção) se elementos distintos de vão para elementos distintos de . Em outras palavras, não pode haver dois elementos diferentes de que tenham a mesma imagem em . - Para construir uma injeção de um conjunto de tamanho
para um conjunto de tamanho (com ), a ideia prática é: para cada um dos elementos do domínio escolhemos uma imagem em , mas sem repetir imagens já escolhidas. Isso é o mesmo que contar arranjos de elementos tomados a . - A fórmula geral para o número de injeções quando
e é
que também se pode pensar como
.
Explicação das notações na fórmula:
-
é o fatorial de , ou seja, . -
é o fatorial de . - A razão
cancela os fatores de e deixa exatamente os fatores decrescentes que representam as escolhas sem reposição.
Passo 3
Aplicando a ideia de injeção ao primeiro item.
- Aqui
e . - Pelo método prático: escolhemos a imagem de
em . Há escolhas possíveis. - Depois escolhemos a imagem de
, que não pode ser igual à de . Então há escolhas restantes. - Multiplicando as escolhas sucessivas obtemos o número total de injeções:
- Pela fórmula de arranjos isso seria
Passo 4
Definição e ideia para contar sobrejeções (essa é a teoria usada no segundo item).
- Uma função
é sobrejetora (sobrejeção) se para todo elemento existe pelo menos um com . Ou seja, a imagem de é todo o conjunto . - Para contar sobrejeções de um conjunto de tamanho
para um conjunto de tamanho (com ), existem fórmulas gerais usando números de Stirling ou inclusão-exclusão. Mas quando os conjuntos são pequenos é mais simples raciocinar diretamente. - Dois métodos simples que servem aqui:
- Contar todas as funções e subtrair as que não são sobrejetoras.
- Contar diretamente as distribuições dos elementos do domínio entre as pré-imagens dos elementos do contradomínio, exigindo que cada célula receba pelo menos um elemento.
Vou usar o método 1 por ser direto e prático neste caso.
Passo 5
Aplicando ao segundo item com o método de todas as funções menos as não-sobrejetoras.
- O domínio tem
elementos e o contradomínio tem elementos. - Número total de funções
(sem nenhuma restrição) é , porque cada um dos elementos do domínio tem escolhas independentes de imagem. Logo
- Agora contamos quantas funções NÃO são sobrejetoras. Essas são exatamente as funções cuja imagem é um único elemento de
, isto é, as funções constantes. Há exatamente funções constantes: a que envia todos os elementos de para e a que envia todos para . - Portanto o número de funções sobrejetoras é
Passo 6
Outra forma de ver (verificação rápida) pelo método das partições:
- Para ser sobrejetora precisamos que a pré-imagem de
seja um subconjunto não vazio de e a pré-imagem de seja o complemento, também não vazio. - O número de subconjuntos não vazios e não totais de um conjunto de
elementos é
que coincide com o resultado acima. Cada escolha do subconjunto que mapeia para
determina uma sobrejeção única (o resto vai para
).