De quantas formas podemos alinhar em sequência p sinais “+” e q sinais “-” de modo que 2 sinais “-” nunca fiquem juntos?
(Observação: É dado que p +1 >= q.)

Passo 1

O problema pede o número de sequências formadas por p sinais “ +” e q sinais “ -” de modo que nunca haja dois “ -” consecutivos. É um exercício de contagem em combinatória, aplicando o princípio de lacunas (gaps).

Passo 2

Primeiro, imaginemos colocar todos os p sinais “ +” em fila:
+;+;dots+(p vezes)
Entre e nas extremidades desses p sinais há exatamente p+1 lacunas onde podemos eventualmente inserir sinais “ -”.

Passo 3

Para garantir que não haja dois “ -” juntos, só podemos colocar no máximo um “ -” em cada lacuna. Como p+1>= q (condição dada), há lacunas suficientes para acomodar todos os q sinais “ -”, desde que escolhamos lacunas distintas.

Passo 4

O número de maneiras de escolher q lacunas dentre as p+1 disponíveis é dado pelo coeficiente binomial. Logo, o total de sequências válidas é
binomp+1q

Resposta

binomp+1q

Exercícios de Livros Relacionados