# How many 15 digit binary sequences are there with no exactly two adjacent 0's ?

I want to count  the number of 15 digit serieses that have no exactly 2 adjacent zeros.
example for an allowed series( to be counted):
010101010101011
or
111111111111111
or
000000000000000
exampled for an allowed ones(not to be counted):
001111111111111
or
111111111111100
or
111010100011001
their number should be 1597
Only need to know how to calculate this?
LVL 10
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Senior DeveloperCommented:
Commented:
If you disallow exactly 2 consecutive 0's
10747

if you disallow 2 or more consecutive 0's
1597
https://oeis.org/A000045
Author Commented:
ste5an I didn't really get the connection, if you could explain!
ozo :
F(n+2) = number of binary sequences of length n that have no consecutive 0's.
F(15+2)=f(17)=0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597=1597 if you disregard the first 0.
now why is this true, can this be explained! you see I do have the answer already but the way we got it is what I need.
Can you please explain? A bonus would be explaining also how they are related to Fibonacci?
Commented:
for n>=2
binary sequences of length n that have no consecutive 0's
= binary sequences of length n starting with 1 that have no consecutive 0's +  binary sequences of length n starting with 0 that have no consecutive 0's
= binary sequences of length n starting with 1 that have no consecutive 0's +  binary sequences of length n starting with 01 that have no consecutive 0's
= binary sequences of length n-1 that have no consecutive 0's + binary sequences of length n-2 that have no consecutive 0's
Which is the Fibonacci recurrence
Author Commented:
consider n=4 with 3 zeros:
all cases is: 2^4=16
not allowed:
1000
0001
which leaves 14 cases.
F(4+3)=F(7)
0 1 1 2 3 5 8 13
F(7)=13 ??
Besides even if it is true ,why?

Example:
if I want to know number of 4 digits sequences that have exactly 2 zeros but consecutive I would do the following:
All 4 digit sequences that have 2 zeros is : 2 of 4 = 6
number of sequences that have consecutive zeros is three, 0011, 1001,0011 --->  6-3=3
How could such a calculation (straight forward) be done to either prove the Fibonacci theory or such give the answer to the original question.
I really need to understand this.
Commented:
If you disallow 3 consecutive zeros, you would get the tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=1, a(1)=2, a(2)=4.
for the same reason that no 2 consecutive zeros gives you F(n+2) where F(n) = F(n-1) + F(n-2) with F(0+2)=1, F(1+2)=2

If you want n digit sequences that have exactly 2 zeros but consecutive, that would be the same as n-1 digit sequences that have exactly 1 zero, which would be C(n-1,1) = n-1

If you disallow exactly 3 consecutive zero's, but allow 4 or more consecutive zero's, that would be  a(n) = 2*a(n-1) - a(n-4) + a(n-5)

But if you are asking about different sequences, and there seem to be at least four different kinds of sequences that you have talked about so far,
then perhaps it would be better to ask them as separate questions.
"If you have follow-up or related questions, post a new question for each of them."

Or if there's a general class of sequences that you are actually interested in, of which the ones you mentioned are specific instances, then please define the general class.
Author Commented:
Sorry for the confusion I was just trying to get things straight (unsuccessfully it seems), anyhow:
If I want  to count these series of numbers
000000000000000
000000000000001
000000000000010
000000000000101             ----> here a jump over 100
000000000000110
so on
I get  10747 of these as you said (I first thought I would get 1597) anyway my question was and remains how?
Now if you happen to know the answer then I would very much appreciate it if you shared your knowledge with me.
On the other hand if you do not know the answer to my query then I would be thankful just the same for what I learned from you(which is this weird connection to the Fibo series). So if there is nothing else you can help me with on this issue I will gladly close the question granting you full points and go on in my research some other place.

And again sorry for any confusion I may have caused.
Commented:
The number of binary sequences of length n, with no subsequence of exactly 2 0's (but allowing subsequences of more than 2 0's) is a(n+3), where  a(n) = Sum{a(k): k=0,1,2,...,n-4,n-2,n-1}; (skipping a(n-3)); with a(0)=0, a(1)=0, a(2)=1, a(3)=1
https://oeis.org/A049856

Specifically, the sequences of length N would be:
1{sequences of length N-1} -> a(n-1) where n=N+3
01{sequences of length N-2} -> a(n-2)
0001{sequences of length N-4} -> a(n-4)
00001{sequences of length N-5} -> a(n-5)
...
000...0001{sequences of length 2} -> a(5)
000...00001{sequences of length 1} -> a(4)
000...000001{sequences of length 0} -> a(3)
000...000000{sequences of length 0} -> a(3)=a(2)

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:
Thanks
Commented:
wonderful site ozo
Thanks
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.