OFFSET
0,4
COMMENTS
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