A371682 Number of binary strings of length n with more 001 than 000 substrings.

0, 0, 0, 1, 3, 8, 18, 41, 89, 191, 400, 833, 1717, 3523, 7184, 14604, 29588, 59822, 120695, 243166, 489271, 983530, 1975416, 3965078, 7954340, 15950301, 31972219, 64069007, 128355352, 257093509, 514864480, 1030937876, 2064045150, 4132012413, 8271156673

Offset: 0

Author

Robert P. P. McKone, Apr 03 2024

Keywords

• nonn

Examples

			a(5) = 8: 00100, 00101, 00110, 00111, 01001, 10010, 10011, 11001.
a(6) = 18: 001001, 001010, 001011, 001100, 001101, 001110, 001111, 010010, 010011, 011001, 100100, 100101, 100110, 100111, 101001, 110010, 110011, 111001.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3322

Crossrefs

Cf. A164137 (equal 000 and 001), A371662 (more 000 than 001).

Programs

Mathematica

tup[n_] := Tuples[{0, 1}, n];
cou[lst_List] := Count[lst, {0, 0, 1}] > Count[lst, {0, 0, 0}];
par[lst_List] := Partition[lst, 3, 1];
a[n_] := a[n] = Map[cou, Map[par, tup[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 23}], {n, Table[a[m], {m, 0, n - 1}]}]

Formula

a(n) = 2^n - A164137(n) - A371662(n).

Extensions

a(26)-a(34) from Alois P. Heinz, Apr 03 2024