A371358 - OEIS

%I #37 May 02 2024 09:21:35

%S 0,0,1,2,4,10,21,42,89,184,371,758,1546,3122,6315,12782,25780,51962,

%T 104759,210934,424404,853806,1716759,3450158,6932169,13924260,

%U 27959805,56130762,112662414,226080318,453595341,909925794,1825052601,3660020992,7339006091

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

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

%F 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

%F For n >= 2, a(n) = 2*a(n-1) + A163493(n-1) - A163493(n-2) - A370048(n-2). - _Max Alekseyev_, Apr 30 2024

%F 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

%F 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

%e a(4) = 4: 0000, 0001, 1000, 1100.

%e a(5) = 10: 00000, 00001, 00010, 00011, 00100, 01000, 10000, 10001, 11000, 11100.

%p b:= proc(n, l, t) option remember; `if`(n+t<1, 0, `if`(n=0, 1,

%p       add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))

%p     end:

%p a:= n-> b(n, 2, 0):

%p seq(a(n), n=0..34);  # _Alois P. Heinz_, Mar 20 2024

%t tup[n_] := Tuples[{0, 1}, n];

%t cou[lst_List] := Count[lst, {0, 0}] > Count[lst, {0, 1}];

%t par[lst_List] := Partition[lst, 2, 1];

%t a[n_] := Map[cou, Map[par, tup[n]]] // Boole // Total;

%t Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

%o (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

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

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

%K nonn

%O 0,4

%A _Robert P. P. McKone_, Mar 19 2024