The Gateway to Computer Science Excellence
0 votes
Find a recurrence relation for the number of bit strings of length n that contain the string 01.
in Combinatory by | 93 views
I couldn't understand that solution

2 Answers

+2 votes

Two types of equation are needed to get a confirmed answer

Though taking  $01$ means, we have got those string which have some substring with $01.$

but actually that will give a huge number of strings

So, at first we try, the string that donot have substring $01.$

Say string can be $1XXX...XXXX$ or $XXX....XXXX0$, that means start with $1$ and end with $0.$

What is recurrence relation for it?

Here ans. will be $a_{n}=a_{n-1}+1$

Now take some example and check

$a_{2}=a_{1}+1=3$ because $a_{1}=2$ either $0$ or $1.$

$a_{3}=a_{2}+1=4$ and those are $000,100,110,111$

Now, take it's converse how many string that not containing $a_{n}$

Say it is $P_{n}$

then $P_{n}=2^{n}-a_{n}$

Now derive it with proper answer



Now check $P_{n}=2^{n-1}+{\color{red}{2^{n-1}-a_{n-1}} }-1$

then $P_{n}=2^{n-1}+P_{n-1}-1$

So ans will be $P_{n}=P_{n-1}+2^{n-1}-1$

Hope it is clear now.

edited by
+1 vote
Suppose A(n) denotes the number of strings that have 01 as substring

then first symbol in string of length n may be 0 or 1.

If it is 1 then number of strings possible now is due to first symbol being 1 becomes A(n-1).

If it is 0 then two cases may arise based on the second symbol in string.

case 1: if second symbol is 0 then number of strings possible now is due to first symbol being 0 and second also being 0  becomes A(n-2).

case 2 : If second symbol is 1 then desired substring has already occurs . so number of string possible due to this case is 2^(n-2)

so , required recurrence relation is

A(n) = A(n-1) + A(n-2) + 2^(n-2).

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,314 questions
60,435 answers
95,251 users