cp's OEIS Frontend

A370048 Number of binary strings of length n in which the number of substrings 00 is one more than that of substrings 01.

%I A370048 #16 May 02 2024 10:51:03
%S A370048 0,0,1,1,2,6,10,18,40,76,141,285,558,1066,2097,4121,8000,15660,30763,
%T A370048 60171,117918,231690,454816,893208,1756688,3455580,6799195,13388587,
%U A370048 26375466,51974798,102470402,202108730,398756664,787025260,1553900235,3068937675,6062944710,11981429394,23683822694,46828287038
%N A370048 Number of binary strings of length n in which the number of substrings 00 is one more than that of substrings 01.
%F A370048 For n >= 2, a(n) = Sum_{m=0..floor((n-1)/3)} binomial(2*m,m+1) * binomial(n-1-2*m,m) + binomial(2*m+1,m) * binomial(n-2-2*m,m).
%F A370048 For n >= 4, a(n) = ( (n-2)*(2*n-1)*(n^2-n-4)*a(n-1) - (n^2-5*n+2)*(n^2+n-4)*a(n-2) + 2*(n-3)*n^2*(2*n-3)*a(n-3) - 4*(n-3)*(n-1)^2*n*a(n-4) ) / (n-2)^2 / (n-1) / (n+2).
%F A370048 a(n) = 2*A371358(n+1) - A371358(n+2) + A163493(n+1) - A163493(n).
%F A370048 G.f. ((1-x^2-2*x^3)*(1-2*x+x^2-4*x^3+4*x^4)^(-1/2) - 1 - x)/x^2/2, which can be expressed in terms of g.f. C(x) = (1-sqrt(1-4*x))/x/2 for Catalan number (A000108) as x*((x+1)*C(x^3/(1-x))-1)/(1-x-2*x^3*C(x^3/(1-x))).
%o A370048 (PARI) { a370048(n) = (n > 1) * sum(m=0,(n-1)\3, binomial(2*m,m+1) * binomial(n-1-2*m,m) + binomial(2*m+1,m) * binomial(n-2-2*m,m) ); }
%o A370048 (Python)
%o A370048 from math import comb
%o A370048 def A370048(n): return 0 if n<2 else 1+sum((x:=comb((k:=m<<1),m+1)*comb(n-1-k,m))+x*(k+1)*(n-1-3*m)//(m*(n-1-k)) for m in range(1,(n+2)//3)) # _Chai Wah Wu_, May 01 2024
%Y A370048 Cf. A000079, A090129, A163493, A182027, A371358, A371564.
%K A370048 nonn
%O A370048 0,5
%A A370048 _Max Alekseyev_, Apr 30 2024