Question

How many 10 bit binary strings are there none of which contains the pattern '110'.

Answer 1

the subtraction part:

Answer 2

Hmm...

Answer 3

let's count all the strings which have one 110:
you realize that there are (2^7)*7 of them,right?

Answer 4

Yeah, right

Answer 5

So there must be a total of 2^10-(2^7)*7 strings which does not contain '110'. I think i have got it.

Answer 6

NO NO NO

Answer 7

that's what i was trying to say. If you only discount the strings which have one 110, you'll have left out on strings that contain 2 or 3 110s. Think about it.

Answer 8

Oh yes. You are right. I did not consider that condition.

Answer 9

I guess no.

Answer 10

ok np i'll explain

Answer 11

Thank You man. You are very helpful. :D

Answer 12

Okay yes, I got it.It should be 2^4 *4

Answer 13

??

Answer 14

Aww thanks :)
so, you have 2 110s. the configurations possible are:
(strings where there's no gap between the 110s)
110110____
_110110___
__110110__
___110110_
____110110
(strings where there's one gap between the 110s)
110_110___
_110_110__
__110_110_
___110_110
(strings where there's two gaps between the 110s)
110__110__
_110__110_
__110__110
(strings where there's three gaps between the 110s)
110___110_
_110___110.

That makes 14 configurations.
With each of these configurations, you can make 2^4 numbers.
So, the total number of strings with 2 110s are 14(2^4).
Do you get it?

Answer 15

disregard that (2^4)*4 reply. that's wrong.

Answer 16

Thank You for your help.!

Answer 17

It's still not done though :\

Answer 18

=/ @thenewguy: You do realize that I explained it to you.

Answer 19

Sorry I was wrong btw

Answer 20

you weren't *wrong*. Just.....incomplete. I realized it after you went offline yesterday.

Answer 21

I am silly at combinatorics :|

Answer 22

Actually i am sorry that i couldn't just come up online. There was some problem with my internet connection, so I had to go back offline.
I am really thankful to both of you for your help. Can u guys please just tell me what the final answer should be.?
Thank You!

Answer 23

@ParthKohli: Yes, offcourse. I am really thankful for your help. :)

Answer 24

Did we get this answer? Such a stupid Q imo... More of a math problem than comp sci...