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

0, 0, 1, 2, 4, 10, 21, 42, 89, 184, 371, 758, 1546, 3122, 6315, 12782, 25780, 51962, 104759, 210934, 424404, 853806, 1716759, 3450158, 6932169, 13924260, 27959805, 56130762, 112662414, 226080318, 453595341, 909925794, 1825052601, 3660020992, 7339006091

Offset

0,4

Links

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

Formula

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

a(n) = ((4*n^2-15*n+7)*a(n-1) -(5*n^2-22*n+14)*a(n-2) +2*(3*n^2-14*n+10)*a(n-3) -4*(3*n^2-16*n+18)*a(n-4) +8*(n-2)*(n-4)*a(n-5)) / (n*(n-3)) for n>=5. - Alois P. Heinz, Mar 20 2024

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

a(n) = 2^(n-1) - (1/2) * Sum_{k=0..floor(n/3)} binomial(2*k,k) * (2*binomial(n-2*k,n-3*k) - binomial(n-2*k-1,n-3*k)). - Max Alekseyev, May 01 2024

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

Example

a(4) = 4: 0000, 0001, 1000, 1100.
a(5) = 10: 00000, 00001, 00010, 00011, 00100, 01000, 10000, 10001, 11000, 11100.

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 20 2024

Mathematica

tup[n_] := Tuples[{0, 1}, n];
cou[lst_List] := Count[lst, {0, 0}] > Count[lst, {0, 1}];
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}]}]

Prog

(PARI) { a371358(n) = 2^(n-1) - sum(k=0, n\3, binomial(2*k, k) * (2*binomial(n-2*k, n-3*k) - binomial(n-2*k-1, n-3*k))) / 2; } \\ Max Alekseyev, May 01 2024

Crossrefs

Cf. A163493 (equal 00 and 01), A371564 (more 01 than 00), 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: A215533 A128461 A011956 * A018003 A328692 A255711

Adjacent sequences: A371355 A371356 A371357 * A371359 A371360 A371361

Keyword

nonn

Author

Robert P. P. McKone, Mar 19 2024

Status

approved