login
A371358
Number of binary strings of length n which have more 00 than 01 substrings.
5
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
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
KEYWORD
nonn
AUTHOR
Robert P. P. McKone, Mar 19 2024
STATUS
approved