Consideremos os conjuntos
e
. Quantas
funções
existem? Quantas são injetoras? e quantas são sobrejetoras?
funções
Passo 1
O enunciado dá os conjuntos
e
.
Logo e
.
Precisamos contar:
Logo
Precisamos contar:
- todas as funções
, - quantas são injetoras,
- quantas são sobrejetoras.
Para isso usamos:
- Número de funções gerais de um conjunto de tamanho
para um de tamanho é . - Número de injeções de um conjunto de tamanho
num de tamanho é , que vale zero se . - Número de sobrejeções de um conjunto de tamanho
para um de tamanho é
onde
é o número de Stirling de segunda espécie.
Passo 2
Contagem de todas as funções
.
Cada um dos elementos de
pode ir para qualquer dos
de
.
Cada um dos
Passo 3
Contagem das funções injetoras.
Como e
, não há como atribuir valores distintos em
a cada elemento de
.
Como
Passo 4
Cálculo de
.
Para vale
Para
Aqui
, logo
Passo 5
Contagem das funções sobrejetoras.
Aplicando a fórmula
Aplicando a fórmula
Resposta
(a)
(b)
(c)
(b)
(c)