A371564 Number of binary strings of length n which have more 01 than 00 substrings.

0, 0, 1, 3, 6, 13, 28, 56, 113, 231, 464, 930, 1875, 3766, 7547, 15151, 30398, 60917, 122116, 244786, 490435, 982544, 1968413, 3942649, 7896116, 15813268, 31665423, 63403245, 126945244, 254152625, 508798604, 1018538560, 2038870881, 4081149015, 8168806568

Offset: 0

Author

Robert P. P. McKone, Mar 27 2024

Keywords

• nonn

Examples

			a(4) = 6: 0101, 0110, 0111, 1010, 1011, 1101.
a(5) = 13: 0010, 0100, 0101, 0101, 0110, 0111, 0111, 1010, 1011, 1011, 1101, 1101, 1110.
		

Crossrefs

Cf. A163493 (equal 00 and 01), A371358 (more 00 than 01), A090129 (equal 01 and 10), A182027 (equal 00 and 11), A370048 (one more 00 than 01).

Cf. A000079(n-2) (more 01 than 10, for n>=2).

Programs

Maple

b:= proc(n, l, t) option remember; `if`(n+t<1, 0, `if`(n=0, 1,
      add(b(n-1, i, t-`if`(l=0, (-1)^i, 0)), i=0..1)))
    end:
a:= n-> b(n, 2, 0):
seq(a(n), n=0..34);  # Alois P. Heinz, Mar 27 2024

Mathematica

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

Formula

a(n) = 2^n - A163493(n) - A371358(n).

a(n) = (1 - 8*(n-4)*a(n-5) + 4*(3*n-10)*a(n-4) + 2*(8-3*n)*a(n-3) + (5*n-12)*a(n-2) + (7-4*n)*a(n-1))/(1-n) for n>=5.

For n >= 2, a(n) = 2*a(n-1) - A163493(n) + A163493(n-1) + A163493(n-2) + A370048(n-2). - Max Alekseyev, May 01 2024

G.f.: ((1-3*x+2*x^2)^(-1) - (1-2*x+x^2-4*x^3+4*x^4)^(-1/2)) * x / 2. - Max Alekseyev, Apr 30 2024