(Generalização do
Lema de Kaplansky). De quantos modos é possível formar um
-subconjunto de
de modo que entre cada dois elementos escolhidos para o subconjunto haja, no conjunto, pelo menos
elementos não escolhidos para o subconjunto?
Passo 1
O enunciado pede: de quantos modos podemos escolher um subconjunto de tamanho
de
de modo que, entre quaisquer dois elementos escolhidos, haja pelo menos
elementos não escolhidos. O conteúdo aqui é uma bijeção que transforma essa escolha restrita numa escolha livre de
elementos em um conjunto menor, usando uma ideia de “subtrair” espaços mínimos entre escolhas.
Passo 2
Sejam
os elementos escolhidos em
. A condição “entre
e
há pelo menos
não escolhidos” equivale a
para todo
. Definimos então
para cada
.
Passo 3
Com essa definição vemos que
-
, ou seja, os são estritamente crescentes com diferença ao menos 1. - Em particular
.
Logo
é simplesmente uma escolha de
elementos distintos em
, sem mais restrições.
Passo 4
O número de formas de escolher
elementos de um conjunto de tamanho
é