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.

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.

Links

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

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

Cf. A063171, A370883, A370942.

Keyword

nonn,hard,more

Author

Paolo Xausa, Mar 06 2024

Status

approved