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

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.