Prove, usando um argumento combinatório, que os números abaixo são inteiros para qualquer n natural.
c) (3 n)!n!2^n 3^n;

Passo 1

Resumindo, queremos mostrar por contagem combinatória que
(3n)!n!,2^n,3^n
é um inteiro para todo ninN. A ideia é interpretar esse quociente como o número de formas de particionar um conjunto de 3n elementos em n blocos de tamanho 3.

Passo 2

Imagine que temos 3n objetos distintos. O número de maneiras de ordená-los em uma fila é
(3n)!

Passo 3

A partir de cada uma dessas (3n)! permutações, corte a fila em n blocos consecutivos de 3 elementos cada. Assim, cada permutação gera uma lista “ordenada” de n 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 3n objetos em n 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?
  1. Podemos escolher a ordem dos n blocos de n! maneiras.
  2. Dentro de cada bloco podemos permutar seus 3 elementos de 3!=6 maneiras. Como há n blocos, isso dá (3!)^n.
    Logo, cada partição fixa aparece exatamente
n!times (3!)^n ;=;n!times 2^n,3^n
vezes entre as (3n)! permutações.

Passo 5

Como todas as partições em n blocos de 3 são igualmente representadas pelas (3n)! permutações, o número total de partições é
(3n)!n!,(3!)^n ;=; (3n)!n!,2^n,3^n,
que deve ser inteiro.

Resposta

(3n)!n!,2^n,3^n é inteiro porque conta o número de maneiras de particionar um conjunto de 3n elementos em n blocos de 3.

Exercícios de Livros Relacionados