cp's OEIS Frontend

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

%I A371358 #42 Jan 23 2025 08:10:29
%S A371358 0,0,1,2,4,10,21,42,89,184,371,758,1546,3122,6315,12782,25780,51962,
%T A371358 104759,210934,424404,853806,1716759,3450158,6932169,13924260,
%U A371358 27959805,56130762,112662414,226080318,453595341,909925794,1825052601,3660020992,7339006091
%N A371358 Number of binary strings of length n which have more 00 than 01 substrings.
%H A371358 Robert P. P. McKone, <a href="/A371358/b371358.txt">Table of n, a(n) for n = 0..1698</a>
%F A371358 a(n) = 2^n - A163493(n) - A371564(n).
%F A371358 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 A371358 For n >= 2, a(n) = 2*a(n-1) + A163493(n-1) - A163493(n-2) - A370048(n-2). - _Max Alekseyev_, Apr 30 2024
%F A371358 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 A371358 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 A371358 a(4) = 4: 0000, 0001, 1000, 1100.
%e A371358 a(5) = 10: 00000, 00001, 00010, 00011, 00100, 01000, 10000, 10001, 11000, 11100.
%p A371358 b:= proc(n, l, t) option remember; `if`(n+t<1, 0, `if`(n=0, 1,
%p A371358       add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))
%p A371358     end:
%p A371358 a:= n-> b(n, 2, 0):
%p A371358 seq(a(n), n=0..34);  # _Alois P. Heinz_, Mar 20 2024
%t A371358 tup[n_] := Tuples[{0, 1}, n];
%t A371358 cou[lst_List] := Count[lst, {0, 0}] > Count[lst, {0, 1}];
%t A371358 par[lst_List] := Partition[lst, 2, 1];
%t A371358 a[n_] := Map[cou, Map[par, tup[n]]] // Boole // Total;
%t A371358 Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]
%o A371358 (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 A371358 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 A371358 Cf. A000079(n-2) (more 01 than 10, for n>=2).
%K A371358 nonn
%O A371358 0,4
%A A371358 _Robert P. P. McKone_, Mar 19 2024