login
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.
1
0, 0, 1, 4, 11, 28, 66, 152, 339, 748, 1622, 3496, 7454, 15832, 33380, 70192, 146819, 306508, 637326, 1323272, 2738922, 5662600, 11677916, 24061264
OFFSET
0,4
COMMENTS
a(n) counts the nonempty s_i substrings (as described in A370883) among all strings of parentheses of length n.
See A370942 and A370883 for more information.
FORMULA
a(0) = 0; for n >= 1, a(n) = a(n-1) + Sum_{k=2^(n-1)+1..2^n-1} A370942(n,k).
EXAMPLE
a(3) = 4 because the eight strings of parentheses of length 3 contain, in total, 4 properly nested substrings:
.
properly
string nested
substrings
------------------
))) none
))( none
)() ()
)(( none
()) ()
()( ()
(() ()
((( none
MATHEMATICA
countS[s_] := StringCount[s, RegularExpression["(1(?R)*+0)++"]];
Accumulate[Array[Total[countS[IntegerString[Range[2^(#-1), 2^#-2], 2, #]]] &, 20, 0]]
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Paolo Xausa, Mar 06 2024
STATUS
approved