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,4

Links

Table of n, a(n) for n=0..34.

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

Example

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.

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}]}]

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).

Sequence in context: A032253 A125777 A103788 * A182137 A106461 A348124

Adjacent sequences: A371561 A371562 A371563 * A371565 A371566 A371567

Keyword

nonn

Author

Robert P. P. McKone, Mar 27 2024

Status

approved