cp's OEIS Frontend

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

%I A370943 #19 Mar 12 2024 22:56:14
%S A370943 0,0,1,4,11,28,66,152,339,748,1622,3496,7454,15832,33380,70192,146819,
%T A370943 306508,637326,1323272,2738922,5662600,11677916,24061264
%N A370943 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 A370943 a(n) counts the nonempty s_i substrings (as described in A370883) among all strings of parentheses of length n.
%C A370943 See A370942 and A370883 for more information.
%F A370943 a(0) = 0; for n >= 1, a(n) = a(n-1) + Sum_{k=2^(n-1)+1..2^n-1} A370942(n,k).
%e A370943 a(3) = 4 because the eight strings of parentheses of length 3 contain, in total, 4 properly nested substrings:
%e A370943 .
%e A370943            properly
%e A370943   string    nested
%e A370943           substrings
%e A370943   ------------------
%e A370943    )))      none
%e A370943    ))(      none
%e A370943    )()       ()
%e A370943    )((      none
%e A370943    ())       ()
%e A370943    ()(       ()
%e A370943    (()       ()
%e A370943    (((      none
%t A370943 countS[s_] := StringCount[s, RegularExpression["(1(?R)*+0)++"]];
%t A370943 Accumulate[Array[Total[countS[IntegerString[Range[2^(#-1), 2^#-2], 2, #]]] &, 20, 0]]
%Y A370943 Cf. A063171, A370883, A370942.
%K A370943 nonn,hard,more
%O A370943 0,4
%A A370943 _Paolo Xausa_, Mar 06 2024