Permutation and combinations

Question

Number of binary strings of length 10 with 3 consecutive 0's or 1's is ?

Answer 1

Step i)

No of 3 consecutive 0's it means remaining 7 positions occupy either 0 or 1.

it can be done

4 0's + 3 1's  =$\frac{7!}{3!*4!}$

3 0's + 4 1's =$\frac{7!}{3!*4!}$

5 0's + 2 1's=$\frac{7!}{5!*2!}$

2 0's + 5 1's=$\frac{7!}{5!*2!}$

6 0's+ 1 '1s(2)=2*$\frac{7!}{6!*1!}$

7 0's=1 way and 7 1's =1 way.

so total of N(0)=70+42+14+2=128.

ii)No of 3 consecutive 1's N(1)=128 (same as for 3 0's)

iii)No of 3 consecutive 0's and 3 consecutive 1's. $N(0\cap 1)$

it means remaining 4 place can occupy either 0 or 1's.

it can be done in  

2 0's +2 1's=$\frac{4!}{2!*2!}$

3 0's+1 1's=$\frac{4!}{3!*1!}$

1 0's +3 1's=$\frac{4!}{3!*1!}$

4 0's =1 way and 4 1's=1 way.

$N(0\cap 1)$=16.

N(0 U 1)=N(0)+N(1)-$N(0\cap 1)$

=128+128-16

N(0 U 1)=240

Comments

But solution given says: $2*\binom {10} 3 = 240$ ?

---

i dont know why it is.

this procedure gives correct result for similar type of problems.

---

Is $0111100000$ string counted in your result?

---

@santhoshdevulapally 

No of bit strings with 3consecutive zeroes of length 10 are 520.

Check this arjun sir answered similar question but of length 8.

upto T(8) sir has done ,do T(9) and T(10),,,you will get 520

This is not matching with your answer.

https://gateoverflow.in/13127/counting

---

i use this method .u chek once with this method

https://gateoverflow.in/18523/combination

---

Where you considered "consecutive"?

---

@Arjun sir

consider first 3 bits for consecutive and calculate remaining 7 bits for other binary no's.

Answer 2

Let $a_{n}$ be the number of bit strings containing three consecutive zeroes.

Then if first bit is 1 we can choose 3 zeroes in $a_{n-1}$ ways .

or if it is 01 we can choose 3 zeroes in  $a_{n-2}$ ways.

or if it is 001 then we can choose 3 zeroes in  $a_{n-3}$ ways.

and we have exactly one set of 3 zeroes with 3 digits so $2^{n-3}$

$a_{n} = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n - 3}$

$a_{0}=a_{1}=a_{2}=0,a_{3}=1$

$a_{4} = a_{3} + a_{2} + a_{1} + 2^1$ = 3

$a_{5} = a_{4} + a_{3} + a_{2} + 2^{ 2 }$ = 8

$a_{6}=20 , a_{7} = 47, a_{8}=107,a_{9}=238, a_{10}=520 $

Similarly for 3 consecutive 1's we get 520 ways.

Now we find intersection of both 000 and 111. Remaining 4 spaces can be filled in $2^4 = 16$ ways.

000 can occur in a string of length 10 in eight ways - from positions 1 to 8. Lets consider them separately and assume 000 comes first (to make the cases exhaustive but still mutually exclusive).

1. 000 _ _ _ _ _ _ _ - 5 places for 111 to come - 5*16 possible strings as remaining 4 places can be filled in 16 ways
2. 1 000 _ _ _ _ _ _ - 4 places for 111 to come - 4*8 possible strings as remaining 3 places can be filled in 8 ways (1 is added before 000 as 0 coming in first position is counted in part 1)
3. _ 1 000 _ _ _ _ _ - 3 places for 111 to come - 3*8 possible strings
4. _ _ 1 000 _ _ _ _ - 2 places for 111 to come - 2*8 - 2 possible strings (excluding 111 at beginning as this would be counted later)
5. _ _ _ 1 000  _ _ _ - 1 places for 111 to come - 8 - 2 possible (excluding 1111000 and 01111000 as these would be counted later)

So, totally $80+32+24+14+6 = 156$ possible strings and by symmetry we should have $160$ strings for the case where 111 comes before 000. Thus, we should subtract $2*156=312$ from our earlier count of 1040, which gives $1040 - 312 = 728.$

But we are not yet done, there might be strings with "000" or "111" repeated and those we have subtracted twice. Lets consider "000" being repeated.

000 000 _ _ _ _ - not happening in our count

000 1 000 111 - happens
000 1111 000 - happens
0000111000 - happens
 

Similarly 111 0 111 000, 111 0000 111 and 1111000111 also happens. So, we must add 2*3=6 to our answer which gives

$$728+6=734$$

Comments

0000111000 is considered in 1 and 1111000111 is considered similarly for the case where 111 comes before 000 (not shown as a case in the answer).

But these are recounted in case 5 and must be added which I have done now.

---

But the below  are already covered in case 1 ?? then why you are adding those to final answer ??

000 1 000 111 - happens
000 1111 000 - happens
0000111000 - happens

That means we have removed these above valid ones from the total ,but this should be present so finally we are adding to the answer .

is it correct ??

---

No. these are covered in case 1  (for 000 before 111) and also case 4 and 5 (for 111 before 000). Since we subtracted twice, we have to add once.

Answer 3

The negation of statement :

Contains 3 consecutive 0's or 3 consecutive 1's

is:

Contains <= 2    consecutive 0's and     <=2     consecutive 1's

Now,

Lets compute the strings for the negation.

We can have the strings starting 0 and next bit is 1 or starting with 00 and next bit is 1   & vice-versa.

So, lets have 2 recurrances viz. one starting with 0 and other starting with 1.

T(n)

= strings starting with 0 and contain <=2 consecutive 0's and <=2 consecutive 1's

= F(n-1)  +  F(n-2)

Similarly,

F(n)

= strings starting with 1 and contain <=2 consecutive 1's and <=2 consecutive 0's

= T(n-1) + T(n-2)

Now, always we have T(n) = F(n)

-----------------------------------------------------------------

T(1) = viz. the string '0'

F(1) = viz. the string '1'

T(2) = viz. the strings 01 and 00

F(2) = viz. the strings 10 and 11

T(3) = viz.  the strings 001, 011 and 010

F(3) = viz. the strings 110.100 and 101

Now, compute the values using the recurrance relations.

So, T(4) = F(4) = 5

T(5) = F(5) = 8

Similarly, T(10) = F(10) = 89

So, total strings that have 3 consecutive 0's or 3 consecutive 1's

= 2¹⁰ - [ T(10) + F(10) ]

= 1024 - 178

= 856

Comments

How did you get T(10) and F(10) directly?? Give the formula plz.

---

@Rahul. I just calculated one-by-one sequentially.