Quantas cadeias de bits com comprimento n, em que n é um número inteiro positivo, que começam e terminam com 1 são possíveis?

Passo 1

O enunciado pede para contar quantas cadeias de bits de comprimento n (com n inteiro positivo) começam e terminam com o dígito 1. O conteúdo aqui é contagem de configurações em que fixamos algumas posições e deixamos as outras livres, aplicando o princípio fundamental da contagem (ou “regra do produto”).

Passo 2

Como a cadeia deve começar com 1 e terminar com 1, nós já fixamos dois bits: o primeiro e o último. Sobram, portanto, n-2 posições “livres” (caso n\ge2) que podem ser preenchidas com 0 ou 1 de forma independente.

Passo 3

Para cada uma das n-2 posições internas temos 2 escolhas (0 ou 1). Pelo princípio fundamental da contagem, o total de cadeias possíveis com essas posições livres é
2^{n-2}.

Passo 4

Observação do caso extremo n=1: quando n=1 só existe uma cadeia de tamanho 1, que é “1”, e ela começa e termina com 1. Logo, nesse caso há exatamente 1 cadeia possível.

Resposta

Para n\ge2 o número de cadeias é
2^{n-2},
e para n=1 é 1.

Exercícios de Livros Relacionados