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

Also strings can have 000 and 111 which are seperated. That case is not considered here.

---

@arjun sir

can you provide a simple solution, this is really dificult to understand from the first reccurence relation.

---

Where is the question taken from?

---

Made easy test series and their solution was ridiculously wrong. 2*10C3=240.

---

Even question is like that for an objective exam. There is no easy way to solve this other than exhustive counting - which is not good for an objective exam. But the recurrence part of the problem is important as that have been asked many times in GATE and clearly given in Kenneth Rosen which is from where questions are made (not copied) for GATE.

---

Reccurence reations are really tough plz provde some link or pdf to understand them if possible.

---

You can google to get Kenneth Rosen pdf.

---

Sir where you have covered the case :0000111000 and 1111000111 ??

in case 1 and case 5 ??

---

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.