Seja
um conjuntos finito com
elementos. Use indução para provar que o conjuntos das bijeções
tem
! elementos.
Passo 1
O enunciado pede para provar, por indução em
, que se
é um conjunto finito com
, então o número de bijeções
é
. Vamos usar o princípio multiplicativo de contagem e o esquema de indução em
.
Passo 2
Caso base (
). Se
então
. Há exatamente uma função
, que é bijetora. Logo o número de bijeções é
. Como
, o resultado vale para
.
Passo 3
Hipótese de indução. Suponha que para todo conjunto finito
com
, o número de bijeções
é
.
Passo 4
Passo indutivo (
). Seja
com
. Escolha um elemento
.
- Primeiro escolhemos a imagem
em : há escolhas para . - Depois, a restrição de
ao complemento
é uma bijeção entre dois conjuntos de tamanho
. Pelo HI existem
formas de definir essa restrição.
Pelo princípio multiplicativo, o total de bijeções em é
Pelo princípio multiplicativo, o total de bijeções em
Resposta
O número de bijeções
é
.