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

0, 0, 1, 1, 2, 6, 10, 18, 40, 76, 141, 285, 558, 1066, 2097, 4121, 8000, 15660, 30763, 60171, 117918, 231690, 454816, 893208, 1756688, 3455580, 6799195, 13388587, 26375466, 51974798, 102470402, 202108730, 398756664, 787025260, 1553900235, 3068937675, 6062944710, 11981429394, 23683822694, 46828287038

Offset: 0

Author

Max Alekseyev, Apr 30 2024

Keywords

• nonn

Crossrefs

Cf. A000079, A090129, A163493, A182027, A371358, A371564.

Programs

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) ); }

Python

from math import comb
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

Formula

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

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

a(n) = 2*A371358(n+1) - A371358(n+2) + A163493(n+1) - A163493(n).

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