1. De quantos modos podemos selecionar p elementos do conjunto \{1,2, \ldots, n\}, sem selecionar dois números consecutivos?

Passo 1

O que o problema pede: contar de quantos modos podemos selecionar p elementos do conjunto \{1,2,\ldots,n\} de tal forma que nenhum par de elementos selecionados seja composto por números consecutivos.
Informações dadas: temos dois inteiros n e p (com n\ge 1, p\ge 0 em geral) e o conjunto \{1,2,\ldots,n\}. A restrição é: se \{i,j\} é subconjunto selecionado com i<j, então não pode ocorrer j=i+1.
Pergunta explícita: qual é o número de subconjuntos de tamanho p que satisfazem essa condição?

Passo 2

Modelagem com posições ordenadas. Seja uma seleção válida representada por p índices crescentes
i_1<i_2<\cdots<i_p,
onde cada i_k está em \{1,2,\ldots,n\} e a condição “não consecutivos” significa
i_{k+1}-i_k\ge 2\quad\text{para }k=1,\dots,p-1.
Essa é uma maneira natural de pensar: escolher p posições i_k sujeitas a diferenças mínimas.

Passo 3

Construção de uma bijeção simples (a técnica do “shift”). Defina novos números
j_k = i_k - (k-1)\quad\text{para }k=1,\dots,p.
Vou explicar por que isso é útil e bijetivo:
  • Como i_1\ge 1, temos j_1\ge 1.
  • Para k\ge 1,
j_{k+1}-j_k = (i_{k+1} - k) - (i_k - (k-1)) = i_{k+1}-i_k-1 \ge 1,
pois i_{k+1}-i_k\ge 2. Portanto os j_k são inteiros estritamente crescentes com diferença pelo menos 1, ou seja,
1\le j_1<j_2<\cdots<j_p.
  • Qual é o maior valor possível de j_p? Temos i_p\le n, então
j_p = i_p - (p-1) \le n-(p-1).
Assim cada j_k pertence a \{1,2,\ldots,n-(p-1)\}.
Logo a transformação (i_1,\dots,i_p)\mapsto (j_1,\dots,j_p) envia seleções válidas de p elementos de \{1,\dots,n\} em subconjuntos estritamente crescentes de tamanho p de \{1,\dots,n-(p-1)\}.

Passo 4

Prova de bijetividade (inversibilidade). Dada qualquer lista estritamente crescente
1\le j_1<j_2<\cdots<j_p\le n-(p-1),
podemos recuperar os i_k por
i_k = j_k + (k-1).
Esses i_k satisfazem 1\le i_1<\cdots<i_p\le n e i_{k+1}-i_k = (j_{k+1}-j_k)+1\ge 2, 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 p em \{1,2,\ldots,n-(p-1)\}.

Passo 5

Contagem final via coeficiente binomial. O número de subconjuntos de tamanho p do conjunto \{1,2,\ldots,n-(p-1)\} é o coeficiente binomial
\binom{n-(p-1)}{p}=\binom{n-p+1}{p}.
Aqui eu explico o significado: \binom{a}{b} é o número de maneiras de escolher b elementos distintos e sem ordem de um conjunto com a elementos; sua fórmula fechada é
\binom{a}{b}=\frac{a!}{b!(a-b)!},
onde a! (fatorial) é o produto a(a-1)\cdots 1. No nosso caso a=n-p+1 e b=p.

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 n com p símbolos “1” (os elementos escolhidos) e n-p 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 p uns, precisamos reservar p-1 zeros mínimos entre eles; sobra um total de
r = (n-p) - (p-1) = n-2p+1
zeros livres para distribuir em p+1 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 r zeros indistinguíveis em p+1 lacunas é
\binom{r+(p+1)-1}{(p+1)-1}=\binom{n-2p+1+p}{p}=\binom{n-p+1}{p},
confirmando o resultado anterior.

Passo 7

Exemplo numérico para checar e ver na prática. Seja n=5 e p=2. A fórmula dá
\binom{5-2+1}{2}=\binom{4}{2}=6.
Listando: \{1,3\},\{1,4\},\{1,5\},\{2,4\},\{2,5\},\{3,5\} — são exatamente 6 seleções, bate com a fórmula.

Passo 8

Observações finais sobre validade e casos especiais. Se n-p+1<p (ou seja, se n<2p-1) então \binom{n-p+1}{p}=0 no sentido combinatório: não há seleções possíveis. Para p=0 a fórmula dá \binom{n+1}{0}=1, correspondente ao conjunto vazio, o que faz sentido.

Resposta

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

Exercícios relacionados