recategorized by
1,103 views
6 votes
6 votes

We want those bit strings of length $10$ which

  1. Start and end with the symbol $1.$
  2. No two zeroes are consecutive.

How many such bit strings are there?

recategorized by

3 Answers

Best answer
15 votes
15 votes

Okay so for this one i request to go through this previous year gate question where it shows an beautiful application of Fibonacci series .

So for bit string of length $n$ , the number of string which not contain two consecutive 0’s are there follow Fibonacci series where$ f1 =2 ,f2=3,f3=5 …..fn=fn-1+fn-2$

GATE CSE 2016 Set 1 | Question: 2 - GATE Overflow for GATE CSE

So we can think think this problem as , given first and last bit as 1  for a string of length $10$ we are remaining with $8$ bit . 

so the problem reduce to “the number of 8 bit string  that do not contain two consecutive 0’s” which is $f8$.

$f4=f3+f2=5+3=8$

$f5=f4+f3=8+5=13$

$f6=f5+f4=13+8=21$

$f7=f5+f6=13+21=34$

$f8=f7+f6=34+21=55$

So our required number of string is $55$.

selected by
9 votes
9 votes

Put $1$'s in the left-most and right position directly. Now we have $8$-bit positions such that No two zeroes are consecutive.

So, we can have No $0$'s OR exactly one $0$ Or exactly two $0$'s Or exactly three $0$'s Or exactly four $0$'s.

So, No $0$'s $=1$ Way $/$ String

  • exactly one $0=8$ ways (No problem when we have exactly one 0, So, 8 ways)
  • exactly two $0$'s $=\;^{7} \mathrm{C}_{2}=21$ ways (Two 0’s cannot be consecutive, So, we have six 1’s, and two 0’s and 0’s should not be consecutive)
  • exactly three $0$'s $=\;^{6} \mathrm{C}_{3}=20$ Ways (No two 0’s can be consecutive, So, we have five 1’s, and three 0’s and 0’s should not be consecutive)
  • exactly four $0$'s $= \;^{5} \mathrm{C}_{4}=5$ Ways (No two 0’s can be consecutive, So, we have four 1’s, and four 0’s and 0’s should not be consecutive)


Total $=55$.

edited by
1 votes
1 votes

okay have done it for no consecutive zeroes recurrence. Now one can find what a8 is. Fibonacci shows up. 

Answer:

Related questions

3 votes
3 votes
1 answer
1
4 votes
4 votes
3 answers
3
GO Classes asked Jun 14, 2022
646 views
The number of ways of selecting at least one Indian and at least one American for a debate from a group comprising $3$ Indians and $4$ Americans and no one else?