De quantos modos podemos formar uma sequência de p elementos iguais a 1 e q elementos iguais a 0 se dois elementos iguais a zero não podem ser adjacentes?

Passo 1

O enunciado quer contar o número de sequências de comprimento p+q formadas por exatamente p uns e q zeros, sujeitas à restrição de que não apareçam dois zeros consecutivos. O conteúdo é contagem de sequências com restrição de adjacência, que vamos tratar com um argumento de “vãos” entre os uns.

Passo 2

Imagine colocar primeiro os p uns em fila. Entre esses uns e também antes do primeiro e depois do último há exatamente p+1 vãos onde os zeros podem eventualmente ser inseridos. Para garantir que não haja dois zeros adjacentes, permitimos no máximo um zero em cada vão.

Passo 3

Como precisamos inserir precisamente q zeros e cada zero deve ficar num vão distinto, basta escolher quais q vãos dentre os p+1 disponíveis vão receber um zero. O número de maneiras de escolher q vãos de um total de p+1 é dado por
binomp+1q

Passo 4

Portanto, o total de sequências procurado é
binomp+1q,
com a convenção de que se q>p+1 então binomp+1q=0, refletindo a impossibilidade de colocar mais zeros do que vãos.

Resposta

binomp+1q

Exercícios de Livros Relacionados