Number of binary strings of length n that contain the substring 1000.

Terms

a(0) =0a(1) =0a(2) =0a(3) =0a(4) =1a(5) =4a(6) =12a(7) =32a(8) =79a(9) =186a(10) =424a(11) =944a(12) =2065a(13) =4456a(14) =9512a(15) =20128a(16) =42287a(17) =88310a(18) =183492a(19) =379624a(20) =782497a(21) =1607756a(22) =3294164a(23) =6732992a(24) =13732063a(25) =27953522a(26) =56807184a(27) =115269984a(28) =233585121a(29) =472771152