Prove, usando um argumento combinatório, que os números abaixo são inteiros para qualquer
natural.
c)
;
c)
Passo 1
Resumindo, queremos mostrar por contagem combinatória que
é um inteiro para todo . A ideia é interpretar esse quociente como o número de formas de particionar um conjunto de
elementos em
blocos de tamanho 3.
é um inteiro para todo
Passo 2
Imagine que temos
objetos distintos. O número de maneiras de ordená-los em uma fila é
Passo 3
A partir de cada uma dessas
permutações, corte a fila em
blocos consecutivos de 3 elementos cada. Assim, cada permutação gera uma lista “ordenada” de
blocos, em que
- a ordem dos blocos importa e
- dentro de cada bloco importa a ordem dos 3 elementos.
Passo 4
Agora fixe uma partição “não ordenada” do conjunto de
objetos em
blocos de 3 (ou seja, cada bloco é um subconjunto de tamanho 3, mas sem ordem entre os blocos nem ordem interna). Quantas permutações da fila geram exatamente essa mesma partição?
- Podemos escolher a ordem dos
blocos de maneiras. - Dentro de cada bloco podemos permutar seus 3 elementos de
maneiras. Como há blocos, isso dá .
Logo, cada partição fixa aparece exatamente
vezes entre as
permutações.
Passo 5
Como todas as partições em
blocos de 3 são igualmente representadas pelas
permutações, o número total de partições é
que deve ser inteiro.