Quantas cadeias de bits de extensão 12 contêm
a) exatamente três 1 s ?
b) no máximo três 1 s?
c) pelo menos três 1 s?
d) um número igual de 0 s e 1 s ?
a) exatamente três 1 s ?
b) no máximo três 1 s?
c) pelo menos três 1 s?
d) um número igual de 0 s e 1 s ?
Passo 1
O enunciado pede para contar cadeias de bits (strings de
e
) de comprimento
sujeitas a várias restrições: exatamente três
s, no máximo três
s, pelo menos três
s e mesmo número de
s e
s.
O que vamos usar é a ideia de coeficiente binomial: para escolher exatamente posições de
dentre
, existem
O que vamos usar é a ideia de coeficiente binomial: para escolher exatamente
maneiras.
Passo 2
Para ter exatamente três
s basta escolher três posições dentre doze para colocar o
. Logo, o número de cadeias é
Passo 3
“No máximo três
s” significa contar as cadeias com
,
,
ou
uns. Somamos os coeficientes binomiais correspondentes:
Passo 4
“Pelo menos três
s” abrange
. Podemos usar que o total de cadeias é
e subtrair as que têm menos de três
s (casos
):
Passo 5
“Mesmo número de
s e
s” em comprimento
significa
zeros e
uns. O número de formas de escolher as seis posições dos uns é
Resposta
(a)
(b)
(c)
(d)
(b)
(c)
(d)