A370943 - OEIS

%I #19 Mar 12 2024 22:56:14

%S 0,0,1,4,11,28,66,152,339,748,1622,3496,7454,15832,33380,70192,146819,

%T 306508,637326,1323272,2738922,5662600,11677916,24061264

%N Row sums of A370942: a(n) is the total number of nonempty, longest nonoverlapping properly nested substrings among all strings of parentheses of length n.

%C a(n) counts the nonempty s_i substrings (as described in A370883) among all strings of parentheses of length n.

%C See A370942 and A370883 for more information.

%F a(0) = 0; for n >= 1, a(n) = a(n-1) + Sum_{k=2^(n-1)+1..2^n-1} A370942(n,k).

%e a(3) = 4 because the eight strings of parentheses of length 3 contain, in total, 4 properly nested substrings:

%e .

%e            properly

%e   string    nested

%e           substrings

%e   ------------------

%e    )))      none

%e    ))(      none

%e    )()       ()

%e    )((      none

%e    ())       ()

%e    ()(       ()

%e    (()       ()

%e    (((      none

%t countS[s_] := StringCount[s, RegularExpression["(1(?R)*+0)++"]];

%t Accumulate[Array[Total[countS[IntegerString[Range[2^(#-1), 2^#-2], 2, #]]] &, 20, 0]]

%Y Cf. A063171, A370883, A370942.

%K nonn,hard,more

%O 0,4

%A _Paolo Xausa_, Mar 06 2024