- De quantos modos podemos selecionar
elementos do conjunto
, sem selecionar dois números consecutivos?
Passo 1
O que o problema pede: contar de quantos modos podemos selecionar
elementos do conjunto
de tal forma que nenhum par de elementos selecionados seja composto por números consecutivos.
Informações dadas: temos dois inteiros e
(com
,
em geral) e o conjunto
. A restrição é: se
é subconjunto selecionado com
, então não pode ocorrer
.
Pergunta explícita: qual é o número de subconjuntos de tamanho que satisfazem essa condição?
Informações dadas: temos dois inteiros
Pergunta explícita: qual é o número de subconjuntos de tamanho
Passo 2
Modelagem com posições ordenadas. Seja uma seleção válida representada por
índices crescentes
onde cada
está em
e a condição “não consecutivos” significa
Essa é uma maneira natural de pensar: escolher
posições
sujeitas a diferenças mínimas.
Passo 3
Construção de uma bijeção simples (a técnica do “shift”). Defina novos números
Vou explicar por que isso é útil e bijetivo:
- Como
, temos . - Para
,
pois
. Portanto os
são inteiros estritamente crescentes com diferença pelo menos
, ou seja,
- Qual é o maior valor possível de
? Temos , então
Assim cada
pertence a
.
Logo a transformação
envia seleções válidas de
elementos de
em subconjuntos estritamente crescentes de tamanho
de
.
Passo 4
Prova de bijetividade (inversibilidade). Dada qualquer lista estritamente crescente
podemos recuperar os
por
Esses
satisfazem
e
, logo correspondem exatamente a uma seleção válida sem consecutivos. Assim a correspondência é bijetiva: contar seleções válidas é o mesmo que contar subconjuntos de tamanho
em
.
Passo 5
Contagem final via coeficiente binomial. O número de subconjuntos de tamanho
do conjunto
é o coeficiente binomial
Aqui eu explico o significado:
é o número de maneiras de escolher
elementos distintos e sem ordem de um conjunto com
elementos; sua fórmula fechada é
onde
(fatorial) é o produto
. No nosso caso
e
.
Passo 6
Intuição alternativa (método “zeros e uns” / stars and bars) — olhando de outro ângulo para fixar a ideia. Imagine uma palavra de comprimento
com
símbolos “1” (os elementos escolhidos) e
símbolos “0” (não escolhidos). A condição “não ter dois 1 consecutivos” exige pelo menos um “0” entre quaisquer dois “1”. Colocando esses
uns, precisamos reservar
zeros mínimos entre eles; sobra um total de
zeros livres para distribuir em
lacunas (antes do primeiro 1, entre os 1s já com um zero obrigatório, e após o último 1). O número de maneiras de distribuir
zeros indistinguíveis em
lacunas é
confirmando o resultado anterior.
Passo 7
Exemplo numérico para checar e ver na prática. Seja
e
. A fórmula dá
Listando:
— são exatamente
seleções, bate com a fórmula.
Passo 8
Observações finais sobre validade e casos especiais. Se
(ou seja, se
) então
no sentido combinatório: não há seleções possíveis. Para
a fórmula dá
, correspondente ao conjunto vazio, o que faz sentido.