Prove, usando um argumento combinatório, que os números abaixo são inteiros para qualquer
natural.
a)
;
a)
Passo 1
O enunciado pede para mostrar, por argumento combinatório, que
é um número inteiro para todo
.
O que vamos fazer é interpretar como “o número de maneiras de colocar
objetos distintos em
posições numeradas” e depois agrupar essas colocações em pacotes de tamanho
, de modo a concluir que
é múltiplo de
.
O que vamos fazer é interpretar
Passo 2
Dividimos as
posições em
blocos, cada bloco contendo exatamente duas posições:
Há
maneiras de distribuir os objetos distintos nessas
posições.
Passo 3
Agora definimos uma relação de equivalência: duas distribuições são equivalentes se uma pode ser obtida da outra trocando, em cada bloco, as duas posições (isso dá 2 opções de permutações internas por bloco). Como temos
blocos e em cada um há exatamente 2 trocas possíveis, cada classe de equivalência contém exatamente
distribuições distintas.
Passo 4
Tendo particionado o conjunto de todas as
distribuições em classes de tamanho
, o número de classes é
que é, por definição, um inteiro.
Resposta
Portanto,
é inteiro pois conta o número de maneiras de distribuir
objetos em
blocos de 2 posições, sem distinguir a ordem dentro de cada bloco.