Sequences of 0s and 1s

As Vicky Ye described, after the first 0 there can be one or 2 1's and then there has to be another 0. Now, the sequence basically starts over with a new length of 17 or 16.

This means we can define a sequence $\{ a_n \}_{n \in \mathbb N}$ for the number of sequences with length $n$ recursively as $a_n = a_{n-2} + a_{n-3}$ .

The starting values are $a_3 = 1$ , $a_4 = 1$ and $a_5 = 1$ , which complete our recursive definition

$a_n = \begin{cases} 1 & \text{for } n=3,4,5 \\ a_{n-2}+a_{n-3} & \text{for } n \geq 6 \end{cases}$

These numbers are called Padovan numbers and the 19th term is 65 .

<?php
//begin with 0
$arr = array(0);
do{
$newarr = array();
foreach($arr as $a){
//contain no 2 consecutive 0's
if(substr($a,-1)!='0'){
$newarr[] = $a.'0';
}
//contain no 3 consecutive 1's, end with 0
if(strlen($a)<18 && substr($a,-2)!='11'){
$newarr[] = $a.'1';
}
}
$arr = $newarr;
//length 19
}while(strlen($arr[0])<19);
//print answer
echo count($arr);
//print all matching strings
echo '<pre>'.print_r($arr,true).'</pre>';
?>

After any 0, the next 0 in the sequence must appear exactly 2 or 3 positions down the sequence. In this case, start at position 1 and end at position 19, move a total of 18 positions down the sequence. Then, add a series of 2s and 3s to get 18. There are a number of ways to do this:

Case 1: there are nine 2s - only 1 way to arrange them.

Case 2: two 3s and six 2s - there are 8C2 = 28 ways to arrange them.

Case 3: four 3s and three 2s - there are 7C3 = 35 ways to arrange them.

Case 4: six 3s - there is only 1 way to arrange them.

Summing the four cases gives 1 + 28 + 35 + 1= $\boxed{65}$