Math Is Fun Forum

White_Owl

Member

Registered: 2010-03-03

Posts: 106

three zeros in a row

The problem is: How many bit strings of length n contains three zeros in a row?
Just by brute force listing of strings I got the numbers 1, 3, 8, 20, 47, 107, 238, 520, 1121 for n=3...11.
Now I'd like to make recursive and closed-form functions to calculate those numbers, but no luck for two days...

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: three zeros in a row

I think it's easier to list all the length-n strings that don't contain three zeroes in a row.

There are three types of these:
- Type 1: those that end with 1
- Type 2: those that end with 10 (and the string 0)
- Type 3: those that end with 100 (and the string 00)

You can get relations out of these quite nicely.

Starting with length-1 strings, we have 0 and 1.
That is one Type 1 string, one Type 2 string and no Type 3 strings.
We can write this as (1,1,0).

The length-2 strings are 00, 01, 10, 11.
The number of types can be summarised as (2,1,1).

The length-3 strings are 001, 010, 011, 100, 101, 110, 111.
This summarises as (4,2,1).

You can get the triple for a length-n string by using the triple for the length-(n-1) string.

For every length(n-1) string, you can get a Type 1 length-n string by adding a 1 to the end.
For every Type 1 length(n-1) string, you can get a Type 2 length-n string by adding a 0.
And similarly, you get a Type 3 length-n by adding to a Type 2 length(n-1).

Therefore, if the triple for one length of string is (a,b,c), then the triple for the next length of string will be (a+b+c, a, b).

Going back to your question, you can find the number of strings that do contain 000 by finding the number that don't, and taking this away from 2^n.

Hopefully I've explained that well enough, but here's a table to show what I mean.

Length | Type 1s | Type 2s | Type 3s | Total | Strings containing 000
--------------------------------------------------------------------------
   1   |    1    |    1    |    0    |   2   |   0
   2   |    2    |    1    |    1    |   4   |   0
   3   |    4    |    2    |    1    |   7   |   1
   4   |    7    |    4    |    2    |   13  |   3
   5   |    13   |    7    |    4    |   24  |   8
   6   |    24   |    13   |    7    |   44  |   20
   7   |    44   |    24   |    13   |   81  |   47
   8   |    81   |    44   |    24   |   149 |   107
   9   |    149  |    81   |    44   |   274 |   238
  ...

---

Why did the vector cross the road?
It wanted to be normal.

White_Owl

Member

Registered: 2010-03-03

Posts: 106

Re: three zeros in a row

Thank you.
Somehow I always overlook the approach by cases

So the recursive form should be something like this:

which can be somewhat simplified into:

hmmm.... interesting...

And now I'll embark on the quest to convert this into closed form. Wish me luck... and brain.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: three zeros in a row

http://mathworld.wolfram.com/LinearRecu … ation.html

Last edited by JaneFairfax (2010-04-04 08:55:26)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: three zeros in a row

That's an amazing result Jane, one which I had never heard.  Thanks!

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

soroban

Member

Registered: 2007-03-09

Posts: 452

Re: three zeros in a row

.

. .

. .

. .

.