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,5

Links

Table of n, a(n) for n=0..39.

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

Prog

(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

Crossrefs

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

Sequence in context: A095358 A084481 A006553 * A054273 A127567 A360420

Adjacent sequences: A370045 A370046 A370047 * A370049 A370050 A370051

Keyword

nonn

Author

Max Alekseyev, Apr 30 2024

Status

approved