Seja X um conjuntos finito com n elementos. Use indução para provar que o conjuntos das bijeções f: X X tem n ! elementos.

Passo 1

O enunciado pede para provar, por indução em n, que se X é um conjunto finito com #X=n, então o número de bijeções fcolon Xto X é n!. Vamos usar o princípio multiplicativo de contagem e o esquema de indução em n.

Passo 2

Caso base ( n=0). Se #X=0 então X=emptyset. Há exatamente uma função emptysettoemptyset, que é bijetora. Logo o número de bijeções é 1. Como 0!=1, o resultado vale para n=0.

Passo 3

Hipótese de indução. Suponha que para todo conjunto finito Y com #Y=n, o número de bijeções Yto Y é n!.

Passo 4

Passo indutivo ( nto n+1). Seja X com #X=n+1. Escolha um elemento ain X.
  1. Primeiro escolhemos a imagem f(a)=b em X: há n+1 escolhas para b.
  2. Depois, a restrição de f ao complemento
Xsetminusa;longrightarrow;Xsetminusb
é uma bijeção entre dois conjuntos de tamanho n. Pelo HI existem n! formas de definir essa restrição.
Pelo princípio multiplicativo, o total de bijeções em X é
(n+1)times n! ;=;(n+1)!

Resposta

O número de bijeções fcolon Xto X é n!.

Exercícios relacionados