Como é possível encontrar o número da cadeia de bits de extensão 10 que ou começa com 101 ou termina com 010 ?
Passo 1
O enunciado pede o número de cadeias binárias de extensão
que ou começam com
ou terminam com
.
Conteúdo da matéria: princípio fundamental da contagem e princípio de inclusão-exclusão.
Conteúdo da matéria: princípio fundamental da contagem e princípio de inclusão-exclusão.
Passo 2
Definimos
como o conjunto de cadeias que começam com
. Nesse caso, os 3 primeiros bits estão fixos e os 7 bits restantes podem ser
ou
livremente. Pelo princípio da multiplicação,
Passo 3
Definimos
como o conjunto de cadeias que terminam com
. Analogamente, os 3 últimos bits estão fixos e os outros 7 livres, de modo que
Passo 4
Para
, queremos cadeias que simultaneamente comecem com
e terminem com
. Há 3 bits fixos no início e 3 no fim, restando
bits livres. Assim,
Passo 5
Aplicando o princípio de inclusão-exclusão para obter
,
Resposta
O número de cadeias de extensão
que ou começam com
ou terminam com
é
.