Test by Bikram | Mathematics | Test 2 | Question: 9

Question

The total number of bit strings (that contain only $0$'s and $1$'s) of length $6$ that do NOT contain consecutive zeros are _______.

Answer 1

Yes there is recurrence relation for this a(n) = a(n-1) + a(n-2). where a(1) = 2 and a(2) = 3. But in case you don't know this or you forget this. You can approach the question in this way.

Case 1: No. of bit string consisting No 0's of length 6.
1 1 1 1 1 1                                     is 1.
Case 2. No. of bit string consisting 1 0's.
1 1 1 1 1 0.                                    is 6! / (5! * 1!) = 6.
Case 3. No . of bit string consisting 2 0's such that they should not be together.
               For this we first place all the 1's with alternative blank.
                _ 1 _ 1 _ 1 _ 1 _ .    Now among this 5 blank we need to pick 2 and put zero in that place. So $\binom{5}{2}$ ways.
               This will insure that the 2 0's should not be consecutive.
case 4. No . of bit string consisting 3 0's such that No two zero is consecutive.
              Similar approach first place 1.
              _ 1 _ 1 _ 1 _ . Among these 4 blank we need to select 3 blank and place zero at that place. So $\binom{4}{3}$ ways.

case 5. No of bit string consisting 4 0's such that no two zero is consecutive.
                _ 1 _ 1 _ . We are left with 3 blank and we have 4 zeros. So this can't be possible. There is no such string.

Total = 1 + 6 + $\binom{5}{2}$ + $\binom{4}{3}$.  = 21.

Comments

That recurrence relation was $2016$ gate QS. :) . Anyway other methods also imp.

Answer 2

Recurrence relation is a(n) = a(n-1) + a(n-2) : base cases : a1 = 2 and a2 = 3 and draw tree and calculate for a(6).

Comments

@bikram sir, Solving via RR for above question, I didn't find it obvious at first instance. How you come with this approach?

---

@bhuv

see the approach here https://gateoverflow.in/39636/gate-2016-1-2

Answer 3

Right answer is 21.

Answer 4

Let's call bit strings that don't contain two consecutive 0's "such bit strings".

Such bit strings of length 0 = 1. // $\epsilon$

Such bit strings of length 1 = 2 // 0 and 1

Such bit strings of length 2 = 3 // 01, 10 and 11.

Such bit strings of length 3 = 5 //010, 011, 101, 110, 111

Such bit strings of length 4 = 8 // 0101, 0110, 0111, 1010, 1011, 1101, 1110, 1111

 

We observe that at length k, "such bit strings" = sum of the previous two cases.

So, Such bit strings of length 5 = 8 + 5 = 13

Such bit strings of length 6 = 13 + 8 = 21. (Answer)

---

This is given by a(n) = a(n-1) + a(n-2).
This is actually the Fibonacci sequence.

---

The number of bit strings that do NOT contain two consecutive 1's is also the same.