How many 10 digit strings of 0's and 1's are there that do not contain any consecutive 0's?
Answers
How many 8 bit strings are there with no consecutive 0's?
I just sat an exam, and the only question I think I got wrong was the above(The decider for a high-distinction or a distinction :SSS)
I took Number with consecutive 0's
1 zero 0
2 zeros 7!6!
3 zeros above + 6!5!
4 zeroes above + 5!4!
5 zeros above + 4!3!
6 zeroes above + 3!2!
7 zeroes above + 2!1!
8 zeroes above + 1
(7∗7)+(6∗6)+(5∗5)+(4∗4)+(3∗3)+(2∗2)+1=140
and we have 28−140=116
Is this correct?
Answer:
No. of strings = 144
Step-by-step explanation:
Let c(N) be the count of numbers with N binary digits that have no consecutive 0’s.
c(1) = 2 as 0 and 1 are not having any consecutive zeros
c(2) = 3 as 01, 10, and 11 are not having any consecutive zeros
Now, for the general case :
Consider all N digit numbers. If the first digit is 1, then the there are c(N-1) numbers that contains the remaining digits. If the first two digits are 01, then there are c(N-2) numbers that contains the remaining digits.
Therefore in general, c(N) = c(N-1) + c(N-2).
The resulting recursion is quite similar to that of Fibonacci, but the starting conditions are quite different.
c(1) = 2,
c(2) = 3,
c(3) = 5,
c(4) = 8,
c (5) = 13,
c(6) = 21,
c(7) = 34,
c(8) = 55,
c(9) = 89,
c(10) = 144
Hence, 10 digit strings of 0's and 1's that do not contain any consecutive 0's are c(10) = 144