\bigcirc 11 (Lema de Kaplansky) Seja X=\{1, \ldots, n\}, onde n \in \mathbb{N}. Mostre que o número de subconjuntos de X com r elementos e que não contêm elementos consecutivos é dado por
\binom{n-r+1}{r},
onde 0 \leqslant r \leqslant n-r+1.

Passo 1

O enunciado pede para contar quantos subconjuntos de tamanho r de X=\{1,\dots,n\} não têm elementos consecutivos. O conteúdo usado será um argumento bijetivo, transformando cada subconjunto sem consecutivos num subconjunto qualquer de tamanho r em um universo reduzido, de modo que a contagem seja uma binomial.

Passo 2

Seja \{a_1<a_2<\cdots<a_r\} um subconjunto de X sem nenhum par de elementos consecutivos. Então para todo i\ge2 temos a_i\ge a_{i-1}+2. Definimos novos números
b_i = a_i - (i-1),
para i=1,\dots,r. Como o “sobra” de (i-1) afasta cada b_i do anterior, garantimos
1 \le b_1 < b_2 < \cdots < b_r \le n-(r-1) = n-r+1.

Passo 3

O mapeamento
\{a_1,\dots,a_r\} \;\longmapsto\; \{b_1,\dots,b_r\}
é bijetivo entre:
  1. Os subconjuntos de X com r elementos sem consecutivos, e
  2. Todos os subconjuntos de tamanho r de \{1,2,\dots,n-r+1\}.
    Logo, contar os subconjuntos originais equivale a contar todos os r-subconjuntos de \{1,\dots,n-r+1\}.

Passo 4

Sabemos que o número de subconjuntos de tamanho r de um conjunto com n-r+1 elementos é
\binom{n-r+1}{r}.
Isso vale exatamente quando 0\le r\le n-r+1. Portanto, a resposta é essa binomial.

Resposta

\displaystyle \binom{n-r+1}{r}

Exercícios relacionados