(Generalização do 1^circ Lema de Kaplansky). De quantos modos é possível formar um p-subconjunto de 1,2, ldots, n de modo que entre cada dois elementos escolhidos para o subconjunto haja, no conjunto, pelo menos r elementos não escolhidos para o subconjunto?

Passo 1

O enunciado pede: de quantos modos podemos escolher um subconjunto de tamanho p de 1,2,dots,n de modo que, entre quaisquer dois elementos escolhidos, haja pelo menos r elementos não escolhidos. O conteúdo aqui é uma bijeção que transforma essa escolha restrita numa escolha livre de p elementos em um conjunto menor, usando uma ideia de “subtrair” espaços mínimos entre escolhas.

Passo 2

Sejam x1<x2<cdots<xp os elementos escolhidos em 1,2,dots,n. A condição “entre xi e xi+1 há pelo menos r não escolhidos” equivale a
xi+1-xi ;>=; r+1,
para todo i=1,2,dots,p-1. Definimos então
yi = xi ;-;(i-1),r,
para cada i=1,2,dots,p.

Passo 3

Com essa definição vemos que
  1. yi+1 = xi+1-i r >= xi + (r+1) - i r = (xi-(i-1)r) +1 = yi+1, ou seja, os yi são estritamente crescentes com diferença ao menos 1.
  2. Em particular 1<= y1<y2<cdots<yp<= n-(p-1)r.
Logo (y1,dots,yp) é simplesmente uma escolha de p elementos distintos em 1,2,dots,n-(p-1)r, sem mais restrições.

Passo 4

O número de formas de escolher p elementos de um conjunto de tamanho n-(p-1)r é
binom,n-(p-1)r,p

Resposta

boxedbinomn-(p-1)rp

Exercícios de Livros Relacionados