Prove, usando um argumento combinatório, que os números abaixo são inteiros para qualquer
natural.
d)
;
d)
Passo 1
O que queremos provar é que, para todo natural
,
é um inteiro. O truque é usar um argumento combinatório via ação de um grupo finito de ordem
sobre um conjunto de tamanho
.
Passo 2
Considere todas as bijeções
isto é, todos os jeitos de preencher uma grade com
linhas e
colunas usando exatamente os números de
a
sem repetir. O número total de tais preenchimentos é
Passo 3
Definimos agora um grupo
que age sobre esses preenchimentos, da seguinte forma:
- Para cada coluna
temos uma permutação que troca as linhas daquela coluna. - Além disso temos uma permutação
que permuta as colunas inteiras.
Portanto
e sua ordem é
Passo 4
A ação de
em
é dada assim:
- Se
e , então é o preenchimento em que primeiro permutamos as colunas de segundo e depois, em cada coluna , aplicamos a permutação de linhas .
Essa ação é livre, pois nenhum elemento não trivial depode fixar um preenchimento : permutar linhas dentro de uma coluna ou trocar colunas exigiria que dois lugares distintos contivessem o mesmo número, o que não acontece em .
Passo 5
Como a ação é livre, cada órbita tem exatamente
elementos, e portanto o número de órbitas é
que é um inteiro (pois conta exatamente quantas órbitas de preenchimentos há).
Resposta
Portanto
é inteiro para todo
.